Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ( $\mathsf{PostBQP=PostBPP}$ ), (ii) any one of several quantum sampling experiments ( $\mathsf{BosonSampling}$ , $\mathsf{IQP}$ , $\mathsf{DQC1}$ ) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ( $\mathsf{FBQP\neq FBPP}$ ) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$ .This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

arXiv:2410.20935Leibniz international proceedings in informaticsOct 28, 20240 citations

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

quant-pharXiv:2610.37635Oct 28, 20260 citations

Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

Sevag Gharibian, Miklós Sántha, Jamie Sikora +2 more

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $\rm{QCPH}$ , uses classical proofs, and the second, $\rm{QPH}$ , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $\rm{Q\Sigma_3}$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $\rm{QMA(2)}$ , the variant of Quantum Merlin-Arthur ( $\rm{QMA}$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $\rm{QCPH = QPH}$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in ${\rm P}^{{\rm pp}^{{\rm pp}}}$ ). Second, because $\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$ , $\rm{QMA(2)}$ is strictly contained in NEXP unless $\rm{QMA(2)}=\rm{Q\Sigma_3}$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{QPH}$$ , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{QCPH = QPH}$$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in $${\rm P}^{{\rm pp}^{{\rm pp}}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

arXiv:1805.11139Computational ComplexitySep 20, 202211 citations

Oracle Separations for the Quantum-Classical Polynomial Hierarchy

Avantika Agarwal, Shalev Ben-David

We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any $d$ , if we apply a random restriction to a function $f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$ , the restricted function becomes exponentially close (in terms of $d$ ) to a depth- $d$ decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any $d$, if we apply a random restriction to a function $f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$, the restricted function becomes exponentially close (in terms of $d$) to a depth-$d$ decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.

arXiv:2410.19062Leibniz international proceedings in informaticsOct 24, 20240 citations

The Power of the Lorentz Quantum Computer

Qi Zhang, Biao Wu

We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.We analyze the power of the recently proposed Lorentz quantum computer (LQC), a theoretical model leveraging hyperbolic bits (hybits) governed by complex Lorentz transformations. We define the complexity class BLQP (bounded-error Lorentz quantum polynomial-time) and demonstrate its equivalence to the complexity class P♯P (the class of problems solvable by a deterministic polynomial-time Turing machine with access to a ♯P oracle). LQC algorithms are shown to solve NP-hard problems, such as the maximum independent set (MIS), in polynomial time, thereby placing NP and co-NP within BLQP. Furthermore, we establish that LQC can efficiently simulate quantum computing with postselection (PostBQP), while the reverse is not possible, highlighting LQC's unique "super-postselection" capability. By proving BLQP =P♯P, we situate the entire polynomial hierarchy (PH) within BLQP and reveal profound connections between computational complexity and physical frameworks like Lorentz quantum mechanics. These results underscore LQC's theoretical superiority over conventional quantum computing models and its potential to redefine boundaries in complexity theory.

EntropyFeb 28, 20262 citations

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$ -HardnessFounding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness

Dakshita Khurana, Kabir Tomer

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P^{\#P}}$ -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$ . We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P^{\#P}}$ -- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that $\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}$. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.

arXiv:2409.15248Sep 23, 20241 citation

\mathsf{PostBQP=PostBPP}

), (ii) any one of several quantum sampling experiments (

\mathsf{BosonSampling}

\mathsf{IQP}

\mathsf{DQC1}

) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot (

\mathsf{FBQP\neq FBPP}

) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to

\mathsf{ZPP^{NP}}

2^{\mathrm{poly}(n)}

changes its output with probability above

2^{-Ω(n)}

when the answer of a random instance is flipped by changing a single leaf.

\rm{QCPH}

, uses classical proofs, and the second,

\rm{QPH}

, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level,

\rm{Q\Sigma_3}

, into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for

\rm{QMA(2)}

, the variant of Quantum Merlin-Arthur (

\rm{QMA}

) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if

\rm{QCPH = QPH}

(i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in

{\rm P}^{{\rm pp}^{{\rm pp}}}

). Second, because

\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}

\rm{QMA(2)}

is strictly contained in NEXP unless

\rm{QMA(2)}=\rm{Q\Sigma_3}

(i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

d

, if we apply a random restriction to a function

f

with quantum query complexity

\mathrm{Q}(f)\le n^{1/3}

, the restricted function becomes exponentially close (in terms of

d

) to a depth-

d

decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.

Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from

\mathsf{\#P}

-Hardness

\mathsf{P^{\#P}}

-- such as approximating the permanents of complex Gaussian matrices, or approximating the output probabilities of random quantum circuits. Indeed, we show that as long as any one of the conjectures underlying sampling-based quantum advantage (e.g., BosonSampling, Random Circuit Sampling, IQP, etc.) is true, quantum cryptography can be based on the extremely mild assumption that

\mathsf{P^{\#P}} \not\subseteq \mathsf{(io)BQP/qpoly}

. We prove that the following hardness assumptions are equivalent. (1) The hardness of approximating the probability assigned to a randomly chosen string in the support of certain efficiently sampleable distributions (upto inverse polynomial multiplicative error).(2) The existence of one-way puzzles, where a quantum sampler outputs a pair of classical strings -- a puzzle and its key -- and where the hardness lies in finding the key corresponding to a random puzzle. These are known to imply quantum bit commitments [Khurana and Tomer, STOC'24]. (3) The existence of state puzzles, or one-way state synthesis, where it is hard to synthesize a secret quantum state given a public classical identifier. These capture the hardness of search problems with quantum inputs (secrets) and classical outputs (challenges). These are the first constructions of quantum cryptographic primitives (one-way puzzles, quantum bit commitments, state puzzles) from concrete, well-founded mathematical assumptions that do not imply the existence of classical cryptography.