Quantum Merlin-Arthur proof systems for synthesizing quantum states
- URL: http://arxiv.org/abs/2303.01877v3
- Date: Tue, 27 Jun 2023 12:27:18 GMT
- Title: Quantum Merlin-Arthur proof systems for synthesizing quantum states
- Authors: Hugo Delavenne, Fran\c{c}ois Le Gall, Yupan Liu, and Masayuki Miyamoto
- Abstract summary: We investigate a state synthesizing counterpart of the class NP-synthesizing.
We establish that the family of UQMA witnesses, considered as one of the most natural candidates, is in stateQMA.
We demonstrate that stateQCMA achieves perfect completeness.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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 a 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,
is in stateQMA. Additionally, we demonstrate that stateQCMA achieves perfect
completeness.
Related papers
- What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures [0.7892577704654171]
There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up.
On the one hand, the class of quantum states that is of interest for quantum computing should be complex.
On the other hand, such quantum states should be reachable on a practical quantum computer.
arXiv Detail & Related papers (2024-03-25T15:47:35Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - State-Averaged Orbital-Optimized VQE: A quantum algorithm for the
democratic description of ground and excited electronic states [0.0]
The SA-OO-VQE package aims to answer both problems with its hybrid quantum-classical conception based on a typical Variational Quantum Eigensolver approach.
The SA-OO-VQE has the ability to treat degenerate (or quasi-degenerate) states on the same footing, thus avoiding known numerical optimization problems around avoided crossings or conical intersections.
arXiv Detail & Related papers (2024-01-22T12:16:37Z) - Quantum simulation of excited states from parallel contracted quantum
eigensolvers [5.915403570478968]
We show that a ground-state contracted quantum eigensolver can be generalized to compute any number of quantum eigenstates simultaneously.
We introduce two excited-state CQEs that perform the excited-state calculation while inheriting many of the remarkable features of the original ground-state version of the algorithm.
arXiv Detail & Related papers (2023-11-08T23:52:31Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - stateQIP = statePSPACE [0.15229257192293197]
We study the relation between two such state classes:SDPPSPACE, and stateQIP.
Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE.
We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
arXiv Detail & Related papers (2023-01-18T19:00:17Z) - Quantum Davidson Algorithm for Excited States [42.666709382892265]
We introduce the quantum Krylov subspace (QKS) method to address both ground and excited states.
By using the residues of eigenstates to expand the Krylov subspace, we formulate a compact subspace that aligns closely with the exact solutions.
Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems.
arXiv Detail & Related papers (2022-04-22T15:03:03Z) - Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
We study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations.
We define models of interactive proofs for quantum states and unitaries.
We obtain analogous results in the setting with multiple entangled provers as well.
arXiv Detail & Related papers (2021-08-16T15:59:33Z) - On exploring practical potentials of quantum auto-encoder with
advantages [92.19792304214303]
Quantum auto-encoder (QAE) is a powerful tool to relieve the curse of dimensionality encountered in quantum physics.
We prove that QAE can be used to efficiently calculate the eigenvalues and prepare the corresponding eigenvectors of a high-dimensional quantum state.
We devise three effective QAE-based learning protocols to solve the low-rank state fidelity estimation, the quantum Gibbs state preparation, and the quantum metrology tasks.
arXiv Detail & Related papers (2021-06-29T14:01:40Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.