Quantum Proofs of Proximity

Abstract

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject inputs that are $\epsilon$-far from $\Pi$, while only probing a minuscule portion of their input. We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016). Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. A consequence of this framework is a QMA algorithm to verify the Parity of an $n$-bit string with $O(n^{2/3})$ queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.

arXiv commentIn TQC 2021

References in corpus (24)

• Quantum Amplitude Amplification and Estimation
• Quantum random access memory
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Quantum State Discrimination
• Self-testing of quantum systems: a review
• Quantum certification and benchmarking
• A Quantum-Logic Gate between Distant Quantum-Network Modules
• Quantum communication complexity of symmetric predicates
• Sample-optimal tomography of quantum states
• Verification of quantum computation: An overview of existing approaches
• Self-testing quantum states and measurements in the prepare-and-measure scenario
• Quantum Algorithmic Measurement
• Self-testing entangled measurements in quantum networks
• Robust self-testing of many-qubit states
• A Survey of Quantum Property Testing
• Quantum tests for the linearity and permutation invariance of Boolean functions
• Quantum property testing for bounded-degree graphs
• Improved quantum test for linearity of a Boolean function
• New Results on Quantum Property Testing
• Entanglement is Necessary for Optimal Quantum Property Testing
• A Note on Oracle Separations for BQP
• Relaxed Locally Correctable Codes with Improved Parameters
• Vanishing-Error Approximate Degree and QMA Complexity

Cited by in corpus (1)

• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification