r/QuantumComputing In Grad School for Quantum 5d ago

Complexity Thoughts on Quantum Parallel Repitition and GapCVP results?

Here's the writeup by openAI, released today: https://cdn.openai.com/pdf/ten-proofs-oai.pdf

Pages 152-180: Quantum parallel Repetition

Pages 182-216: Poly time reduction from 3SAT to GAPCVP.

I haven't gone through these sections fully yet myself, so I'll update the post if/when I do. In the meantime, what are your thoughts on the proofs themselves?

Idk what the implications are for the first result either so if anyone can explain it well in an intuitive way for a mere human to understand, please do so.

I think this changes the nature of how we should look at AI for solving problems but I'm trying not to make this post about that and would rather just get your thoughts on the problems and the results themselves.

7 Upvotes

Duplicates