Qma=Pp: A Potential Path To Resolving Ph⊆Pp
Quantum Merlin-Arthur (QMA) proof systems are a model of quantum computation whereby a computationally unbounded prover Merlin sends a quantum state to the verifier Arthur, who checks the state by performing an efficient quantum computation. The class QMA captures the computational power of quantum proofs. In contrast, Probabilistic Polynomial-time (PP) defines the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. There is evidence to suggest QMA ⊆ PP, but proving equality has remained an open question with profound implications.
The Power of Quantum Merlin-Arthur Proof Systems
QMA proof systems harness the power of quantum effects like superposition and entanglement to provide concise proofs to verification problems. For example, it is possible for Merlin to send an entangled multi-qubit state that encodes a solution to a quantum satisfiability problem succinctly. Arthur’s quantum computer can then efficiently check if the state satisfies the problem’s constraints. This demonstrates QMA’s ability to verify solutions using quantum resources more powerful than classical proofs.
Key properties that give QMA systems their strength are state universality, efficient verification of quantum states, and close connection to quantum complexity classes like BQP. Universality means any quantum state can act as a valid QMA proof. Efficient verification ties the definition to computational complexity theory. The relationship with BQP connects QMA to well-studied quantum algorithms. These attributes suggest that QMA captures qualities essential to the power of quantum proofs.
Reducing the Gap with Multi-Prover QMA
A limitation of single-prover QMA systems is the ability for dishonest provers to deceive verifiers, limiting their reliability. Multi-prover QMA (QMMA) builds on the single-prover model by utilizing multiple non-communicating provers to strengthen soundness guarantees. This prevents provers from coordinating deceptive strategies.
A major result is that increasing the number of provers gives QMMA systems greater computational power. Specifically, perfect completeness and soundness in QMMA proof systems is achievable with only two provers, whereas single-prover QMA cannot accomplish this. This effectively bridges the gap between QMA and classical MA proof systems, bringing QMA closer to PP. The multi-prover technique demonstrates that distributing trust across multiple quantum provers significantly enhances verification capabilities.
Getting to PP – The Role of Postselection
Postselection is an operation that conditions on observing a particular outcome of a quantum measurement, enabling certain quantum paradoxes and computational power, albeit in an unphysical way. Nevertheless, postselection has shed light on the capabilities of quantum systems and proofs.
A seminal result known as the KL Theorem shows that BQP with postselection, or PostBQP, can solve any problem in PP with high probability. This intimates a strong equivalence between quantum computation with postselection and classical probabilistic computation. By applying postselection to QMA proof systems, denoted PostQMA, proof power can be boosted to the classical maximum in PP. The KL Theorem provides insight into how quantum proofs could equal classical probabilistic verification given unphysical selective measurement.
Potential Implications for the PH
The Polynomial Hierarchy (PH) is a hierarchy of complexity classes that generalizes P, NP, and beyond based on oracles and Turing machine recursion. A major open question is whether PH is strictly contained in PP, formally PH ⊆ PP. Since QMA likely sits within PH, proving QMA = PP could provide a pathway to resolving this question by collapsing PH to equal PP.
Some indications that PH collapses to a finite level come from results in quantum computation. For example, QMA with quantum proof and classical verification equals PSPACE, which collapses PH to a third level. By further showing QMA = PP, PH would reduce to PPP in the second level. This would confirm the suspected polynomial bound on the hierarchy.
Example QMA Verification Circuit
As an example, consider a quantum circuit that verifies satisfiability of a simple 3-variable formula (x∩y)∪z based on qubit state encoding. Merlin sends qubits representing truth values for x, y, z to Arthur. A verification circuit first computes (x∩y) using Toffoli then OR’s with z-qubit using CCNOT. Finally, measure guarantees (x∩y)∪z is satisfied unless all 0. This demonstrates in principle how QMA systems leverage quantum operations and measurements to efficiently check proofs.
Challenges and Open Problems
Despite progress, establishing QMA = PP remains a difficult open problem due to challenges in quality of quantum proofs and classical simulation of quantum systems. Multi-prover schemes must grapple with prover collusion vulnerabilities, limiting real-world security. Furthermore, efficient classical verification of arbitrary quantum proofs requires confident bounding of quantum proof power.
Path forward include simplified QMA proof schemes that admit efficient simulation, cryptographic methods to address multi-prover collusion, and proof techniques that provably limit quantum soundness gaps. More broadly, understanding relationships between quantum and classical proof systems may rely on resolving major complexity questions like BQP vs PH.
