Quantum Merlin-Arthur proof systems for synthesizing quantum states

Abstract

Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class NP, referred to as stateQMA, which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier. Our main result consists of error reduction of this class and its variants with an exponentially small gap or bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits (stateBQP) and space-uniform polynomial-space quantum circuits (statePSPACE). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA. Additionally, we demonstrate that stateQCMA achieves perfect completeness.

33 pages, 2 figures. v2: minor changes. v3: add a new result - UQMA witness family is in stateQMA. v4: published version (with minor changes)

References in corpus (20)

• Hamiltonian Simulation by Qubitization
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum Copy-Protection and Quantum Money
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Preparing ground states of quantum many-body systems on a quantum computer
• Efficient Verification of Pure Quantum States in the Adversarial Scenario
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Clique Homology is QMA1-hard
• Quantum search-to-decision reductions and the state synthesis problem
• Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
• Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
• Space-Efficient Error Reduction for Unitary Quantum Computations