Unitary property testing lower bounds by polynomials
summary
A method shows any T-query tester that accesses an unknown unitary U and U^{-1} has acceptance probability given by a degree ≤2T multivariable polynomial, and exploiting unitary symmetries reduces it to a symmetric polynomial in eigenvalues. This yields a recurrence time lower bound of Ω(min{t/ε, √d}) (matching an upper bound O(t√d)), and an entanglement entropy exponential lower bound of 2^{Ω(a/4)} queries. The paper introduces the generalized polynomial method and proposes an entangled-subspace problem with a QMA(2) protocol and a QCMA lower bound, conjecturing a QMA vs QMA(2) separation.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:36Quantum query complexity
- 2:10The polynomial method
- 3:37Classical strings
- 4:40Examples
- 7:34Oracle separations
- 10:11Recurrence time
- 12:57Entanglement entropy
- 14:55Quantum groups
- 18:15Entangled Subspace Problem
- 19:23Conclusion
related talks
20mThe Quantum Supremacy Tsirelson Inequality
01h 02mProduct Mixing, Quantum Separation, and Comfortable Juntas
48mThe Quantum Games PCP: Results and Confessions
58mLimitations for Quantum PCPs
01h 03mGround Energy estimation of Quantum Impurity model is in BQP
01h 07mTwo Tensor Optimization Problems From Quantum Information
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
23mA feasible and unitary programming language with quantum control