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 Π and reject inputs that are ε -far from Π , 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(n2/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.
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 Π and reject inputs that are ε -far from Π , 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(n2/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.
Abstract Interactive proofs of proximity allow a sublinear-time verifier to check that a given input is close to the language, using a small amount of communication with a powerful (but untrusted) prover. In this work, we consider two natural minimally interactive variants of such proofs systems, in which the prover only sends a single message, referred to as the proof. The first variant, known as -proofs of Proximity (), is fully non-interactive, meaning that the proof is a function of the input only. The second variant, known as -proofs of Proximity (), allows the proof to additionally depend on the verifier's (entire) random string. The complexity of both s and s is the total number of bits that the verifier observes—namely, the sum of the proof length and query complexity. Our main result is an exponential separation between the power of s and s. Specifically, we exhibit an explicit and natural property Π Π that admits an with complexity O(logn) O ( log n ) , whereas any for Π Π has complexity Ω~(n1/4) Ω ~ ( n 1 / 4 ) , where n denotes the length of the input in bits. Our lower bound also yields an alternate proof, which is more general and arguably much simpler, for a recent result of Fischer et al. (ITCS, 2014). Also, Aaronson (Quantum Information & Computation 2012) has shown a Ω(n1/6) Ω ( n 1 / 6 ) lower bound for the same property Π Π . Lastly, we also consider the notion of oblivious proofs of proximity, in which the verifier's queries are oblivious to the proof. In this setting, we show that s can only be quadratically stronger than s. As an application of this result, we show an exponential separation between the power of public and private coin for oblivious interactive proofs of proximity.
We show that given an explicit description of a multiplayer game, with a classical verifier and a constant number of players, it is QMA-hard, under randomized reductions, to distinguish between the cases when the players have a strategy using entanglement that succeeds with probability 1 in the game, or when no such strategy succeeds with probability larger than 1/2. This proves the “games quantum PCP conjecture” of Fitzsimons and the second author (ITCS'15), albeit under randomized reductions. The core component in our reduction is a construction of a family of two-player games for testing n-qubit maximally entangled states. For any integer n ≥ 2, we give such a game in which questions from the verifier are O(log n) bits long, and answers are poly(loglogn) bits long. We show that for any constant ε ≥ 0, any strategy that succeeds with probability at least 1 - ε in the test must use a state that is within distance δ(ε) = O(εc) from a state that is locally equivalent to a maximally entangled state on n qubits, for some universal constant c > 0. The construction is based on the classical plane-vs-point test for multivariate low-degree polynomials of Raz and Safra (STOC'97). We extend the classical test to the quantum regime by executing independent copies of the test in the generalized Pauli X and Z bases over Fq, where q is a sufficiently large prime power, and combine the two through a test for the Pauli twisted commutation relations. Our main complexity-theoretic result is obtained by combining this family of games with techniques from the classical PCP literature. More specifically, we use constructions of PCPs of proximity introduced by Ben-Sasson et al. (CCC'05), and crucially rely on a linear property of such PCPs. Another consequence of our results is a deterministic reduction from the games quantum PCP conjecture to a suitable formulation of the constraint satisfaction quantum PCP conjecture.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs.
In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture.
We show the following two main constructions of qIOPs, both of which are unconditional:
- We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages.
- We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist.
As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.
The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols.
We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 1 and soundness bounded away from 1 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive.
Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.