On polynomially many queries to NP or QMA oracles
summary
Shows that any problem solvable by graphs of bounded separator number or bounded depth is decidable by a deterministic machine in n^{O(s)} time using O(s log n) C-queries, so constant s (or d) collapses C_deg_s to P^{C}_{log}; polylogarithmic separator number gives quasi-polynomial time with one extra log in queries. Key tools are a novel graph transformation and total-solution-weight function (enforce correct query strings), binary search over a maximized acceptance weight with logarithmically many QMA queries, and a generalized lifting lemma mapping such query graphs to APX-SIM via circuit-to-Hamiltonian.
AI-written summary · about
chapters (8)
- 0:00Start
- 5:18New Results for Query Graphs
- 9:11Quantum Computation
- 19:15Admissable weighting function
- 22:56Inconsistency problem
- 24:14Total solution weight function
- 29:31Constructing the APX-SIM instance
- 31:25Open Problems
related talks
34mTime-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
20mUnitary property testing lower bounds by polynomials
44mQuantum Meets Minimum Circuit Size Problem
37m(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
46mSymmetries, Graph Properties, and Quantum Speedups
17mBounds on the QAC0 Complexity of Approximating Parity
01h 10mQuantum Advantage with Shallow Clifford Circuits
58mTwo classical oracle separations between QMA and QCMA