arXiv:2206.09230

A Simple Proof of PreciseQMA = PSPACE

Yulong Li

Published Jun 18, 2022• 0 citations

Abstract

We give an alternative proof of PreciseQMA = PSPACE, first proved by Fefferman and Lin (Innov. Theor. Comp. Sci. 2018), where PreciseQMA is the class Quantum Merlin-Arthur with inverse exponential completeness-soundness gap. We adapt the proof of Quantum Cook-Levin Theorem to prove the inclusion PSPACE in PreciseQMA.

DOI: 10.48550/arxiv.2206.09230

Related papers

Quantum Merlin Arthur with Exponentially Small Gap

Bill Fefferman, Cedric Yen-Yu Lin

We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians.

arXiv:1601.01975Jan 8, 201612 citations

On QMA protocols with two short quantum proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

This paper gives a QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarithmic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{n\polylog{n}})$. This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

arXiv:1108.4306Quantum Information and ComputationJul 1, 201225 citations

Quantum Merlin-Arthur and Proofs Without Relative Phase

Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha

arXiv:2306.13247Leibniz international proceedings in informaticsJun 23, 20233 citations

On QMA Protocols with Two Short Quantum Proofs (New Trends in Algorithms and Theory of Computation)

François Le Gall, Shota Nakagawa, Harumichi Nishimura

Jun 1, 20121 citation

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

quant-pharXiv:2609.13032Sep 14, 20260 citations

A Complete Characterization of Unitary Quantum Space

Bill Fefferman, Cedric Yen-Yu Lin

arXiv:1604.01384Leibniz international proceedings in informaticsApr 5, 201614 citations

arXiv:2206.09230

A Simple Proof of PreciseQMA = PSPACE

Yulong Li

Published Jun 18, 2022• 0 citations

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.2206.09230

Related papers

Quantum Merlin Arthur with Exponentially Small Gap

Bill Fefferman, Cedric Yen-Yu Lin

arXiv:1601.01975Jan 8, 201612 citations

On QMA protocols with two short quantum proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

arXiv:1108.4306Quantum Information and ComputationJul 1, 201225 citations

Quantum Merlin-Arthur and Proofs Without Relative Phase

Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha

We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [arXiv:1410.2882]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some *other* constant gap is equal to QMA. One interpretation is that Merlin's ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) $\subseteq$ NEXP.We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [arXiv:1410.2882]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some *other* constant gap is equal to QMA. One interpretation is that Merlin's ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) $\subseteq$ NEXP.

arXiv:2306.13247Leibniz international proceedings in informaticsJun 23, 20233 citations

On QMA Protocols with Two Short Quantum Proofs (New Trends in Algorithms and Theory of Computation)

François Le Gall, Shota Nakagawa, Harumichi Nishimura

This paper gives $a$ .QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{npoly\log(n)})$ .This improves the best completeness/soundness gaps known for NP-complete problems in this setting.This paper gives $a$ .QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{npoly\log(n)})$ .This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

Jun 1, 20121 citation

QMA has perfect completeness

Sabee Grewal, Dorian Rudolph

We prove $\mathsf{QMA} = \mathsf{QMA_1}$ , i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$ . As a consequence, quantum $3$ -SAT is $\mathsf{QMA}$ -complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$ .We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.

quant-pharXiv:2609.13032Sep 14, 20260 citations

A Complete Characterization of Unitary Quantum Space

Bill Fefferman, Cedric Yen-Yu Lin

Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded $2^{k(n)}\times 2^{k(n)}$ matrix is complete for the class of problems solvable by quantum circuits acting on $\mathcal{O}(k(n))$ qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian $2^{k(n)}\times 2^{k(n)}$ matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded $2^{k(n)}\times 2^{k(n)}$ matrix is complete for the class of problems solvable by quantum circuits acting on $\mathcal{O}(k(n))$ qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian $2^{k(n)}\times 2^{k(n)}$ matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.

arXiv:1604.01384Leibniz international proceedings in informaticsApr 5, 201614 citations

\subseteq

NEXP.

This paper gives

a

.QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarith- mic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is

\Omega(\frac{1}{npoly\log(n)})

.This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

We prove

\mathsf{QMA} = \mathsf{QMA_1}

, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and

X

gates, yielding a universal gate set for

\mathsf{QMA_1}

. As a consequence, quantum

3

-SAT is

\mathsf{QMA}

-complete. The construction relativizes to classical oracles, so known classical-oracle separations of

\mathsf{QMA}

from

\mathsf{QCMA}

extend to

\mathsf{QMA_1}

2^{k(n)}\times 2^{k(n)}

matrix is complete for the class of problems solvable by quantum circuits acting on

\mathcal{O}(k(n))

qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian

2^{k(n)}\times 2^{k(n)}

matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma [STOC '13] by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that PreciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.