Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03377

No Size-Preserving Amplification with Quantum Advice

Shih-Han Hung, Han-Hsuan Lin

quant-phcs.CCSubmitted Oct 2, 2026• Announced Oct 5, 2026• 0 citations• Revised Oct 30, 2026 (v2)
v1 · Oct 2, 2026v2 · Oct 30, 2026
arXivHTMLPDF

Abstract

Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)=ω(1)$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.

AI Summary

Marriott–Watrous amplification reduces QMA verification error without enlarging the witness. This paper asks whether computation with quantum advice admits an analogous guarantee when the advice length is fixed, even if both the algorithm and advice encoding may be redesigned. For every polynomially bounded $m(n)=\omega(1)$ and error bound $\varepsilon(n)<1/2$ with inverse-polynomial bias, it establishes $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m\subsetneq\mathsf{BQP}_{\varepsilon+\delta}/\mathsf{q}m$ for a positive gap $\delta=O(\min\{(\log m/m)^{1/4},\sqrt{\log m/m}/(1/2-\varepsilon)\})$. For constant $0<\varepsilon<1/2$, the gap is $O_\varepsilon(\sqrt{\log m/m})$, and the larger error remains below $1/2$ eventually. The separating language already has a deterministic polynomial-time algorithm supplied with randomized classical advice of the same length; the lower bound allows mixed quantum advice and arbitrary computation time. The proof combines Nayak’s quantum random-access-code bound, $m\geq(1-H(\varepsilon))k$, with diagonalization over uniform quantum decoders. The upper bound constructs efficiently decodable classical random access codes using systematic Toeplitz linear codes, a second-moment distance estimate, and shared random masks and cyclic shifts across blocks. Sharing the randomization amortizes its description cost; balancing block redundancy and header size gives normalized overhead $O(\sqrt{\log k/k})$. Encoding may be computationally expensive because advice preparation is unrestricted. The result concerns fixed advice budgets, not amplification within $\mathsf{BQP}/\mathsf{qpoly}$, where extra copies are allowed. The optimal separation gap remains open, including whether arbitrarily small improvements can require longer advice or some nonzero error reduction is always possible at fixed size.

Some signs of AI-generated textAI use disclosed
Beyond assistance with writing and presentation, AI contributed to the technical development of the paper.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Quantum Arthur–Merlin games

Chris Marriott, John Watrous

This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that $$ {\text{QMA}} \subseteq {\text{PP}}. $$ Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.

arXiv:cs/0506068•Computational Complexity•Jun 1, 2005•306 citations

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).

arXiv:quant-ph/0402095•Theory of Computing•Jan 1, 2005•157 citations

Limitations of quantum advice and one-way communication

Scott Aaronson

Abstract: Although a quantum state requires exponentially many classical bits to de-scribe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state ” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Un-derlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP 6 ⊂ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quan-tum one-way communication complexity. Using this method, we obtain optimal quantum

Conference on Computational Complexity•Jun 21, 2004•16 citations

Limitations of quantum advice and one-way communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.

IEEE Conference on Computational Complexity (CCC)•Nov 12, 2004•34 citations

Quantum Information and the PCP Theorem

Ran Raz

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$ by a single quantum state $|Ψ>$ of size O(n) qubits, such that: for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$, the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved from $|Ψ>$ by a one-round Arthur-Merlin interactive protocol of size polynomial in $n$. This shows how to go around Holevo-Nayak's Theorem, using Arthur-Merlin proofs. We use the new representation to prove the following results: 1) Interactive proofs with quantum advice: We show that the class $QIP/qpoly$ contains ALL languages. That is, for any language $L$ (even non-recursive), the membership $x \in L$ (for $x$ of length $n$) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state $|Ψ_{L,n} >$ (depending only on $L$ and $n$). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. 2) PCP with only one query: We show that the membership $x \in SAT$ (for $x$ of length $n$) can be proved by a logarithmic-size quantum state $|Ψ>$, together with a polynomial-size classical proof consisting of blocks of length $polylog(n)$ bits each, such that after measuring the state $|Ψ>$ the verifier only needs to read {\bf one} block of the classical proof. While the first result is a straight forward consequence of the new representation, the second requires an additional machinery of quantum low-degree-test that may be interesting in its own right.

arXiv:quant-ph/0504075•Apr 10, 2005•6 citations

Uncloneable Quantum Advice

Anne Broadbent, Martti Karvonen, Sébastien Lord

The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.

arXiv:2309.05155•IACR Communications in Cryptology•Oct 7, 2024•8 citations
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length m(n)=ω(1)m(n)=ω(1)m(n)=ω(1) and every error bound ε(n)\varepsilon(n)ε(n) that stays below 1/21/21/2 by at least an inverse polynomial, there is a positive function δδδ with δ(n)=O(min⁡{(log⁡m/m)1/4, log⁡m/m /(1/2−ε(n))})δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)δ(n)=O(min{(logm/m)1/4, logm/m​/(1/2−ε(n))}) such that BQPε/qm⊊BQPε+δ/qm\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}mBQPε​/qm⊊BQPε+δ​/qm; for constant ε\varepsilonε the gap is O(log⁡m/m)O(\sqrt{\log m/m})O(logm/m​). Here, BQPε/qm\mathsf{BQP}_\varepsilon/\mathsf{q}mBQPε​/qm is the class of languages recognizable with error at most ε(n)\varepsilon(n)ε(n) by a polynomial-time quantum algorithm with an m(n)m(n)m(n)-qubit advice state that only depends on the input length nnn. We show this by proving a stronger separation Pε+δ/rm⊄BQPε/qm\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} mPε+δ​/rm⊂BQPε​/qm, where Pε/rm\mathsf{P}_{\varepsilon}/\mathsf{r}mPε​/rm is the class of languages recognizable with error at most ε(n)\varepsilon(n)ε(n) by a deterministic polynomial-time algorithm with an m(n)m(n)m(n)-bit advice string sampled from a distribution that depends only on nnn.
Marriott–Watrous amplification reduces QMA verification error without enlarging the witness. This paper asks whether computation with quantum advice admits an analogous guarantee when the advice length is fixed, even if both the algorithm and advice encoding may be redesigned.
For every polynomially bounded m(n)=ω(1)m(n)=\omega(1)m(n)=ω(1) and error bound ε(n)<1/2\varepsilon(n)<1/2ε(n)<1/2 with inverse-polynomial bias, it establishes BQPε/qm⊊BQPε+δ/qm\mathsf{BQP}_{\varepsilon}/\mathsf{q}m\subsetneq\mathsf{BQP}_{\varepsilon+\delta}/\mathsf{q}mBQPε​/qm⊊BQPε+δ​/qm for a positive gap δ=O(min⁡{(log⁡m/m)1/4,log⁡m/m/(1/2−ε)})\delta=O(\min\{(\log m/m)^{1/4},\sqrt{\log m/m}/(1/2-\varepsilon)\})δ=O(min{(logm/m)1/4,logm/m​/(1/2−ε)}). For constant 0<ε<1/20<\varepsilon<1/20<ε<1/2, the gap is Oε(log⁡m/m)O_\varepsilon(\sqrt{\log m/m})Oε​(logm/m​), and the larger error remains below 1/21/21/2 eventually. The separating language already has a deterministic polynomial-time algorithm supplied with randomized classical advice of the same length; the lower bound allows mixed quantum advice and arbitrary computation time.
The proof combines Nayak’s quantum random-access-code bound, m≥(1−H(ε))km\geq(1-H(\varepsilon))km≥(1−H(ε))k, with diagonalization over uniform quantum decoders. The upper bound constructs efficiently decodable classical random access codes using systematic Toeplitz linear codes, a second-moment distance estimate, and shared random masks and cyclic shifts across blocks. Sharing the randomization amortizes its description cost; balancing block redundancy and header size gives normalized overhead O(log⁡k/k)O(\sqrt{\log k/k})O(logk/k​). Encoding may be computationally expensive because advice preparation is unrestricted.
The result concerns fixed advice budgets, not amplification within BQP/qpoly\mathsf{BQP}/\mathsf{qpoly}BQP/qpoly, where extra copies are allowed. The optimal separation gap remains open, including whether arbitrarily small improvements can require longer advice or some nonzero error reduction is always possible at fixed size.
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA⊆PP. {\text{QMA}} \subseteq {\text{PP}}. QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}BQP/qpoly⊆PP/poly, where BQP/qpoly\mathsf{BQP/qpoly}BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊄BQP/qpoly\mathsf{NP}\not \subset \mathsf{BQP/qpoly}NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).
Abstract: Although a quantum state requires exponentially many classical bits to de-scribe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state ” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Un-derlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP 6 ⊂ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quan-tum one-way communication complexity. Using this method, we obtain optimal quantum
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly /spl sube/ PP/poly, where BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state " that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP /spl nsub/ BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols.
We show how to encode 2n2^n2n (classical) bits a1,...,a2na_1,...,a_{2^n}a1​,...,a2n​ by a single quantum state ∣Ψ>|Ψ>∣Ψ> of size O(n) qubits, such that: for any constant kkk and any i1,...,ik∈{1,...,2n}i_1,...,i_k \in \{1,...,2^n\}i1​,...,ik​∈{1,...,2n}, the values of the bits ai1,...,aika_{i_1},...,a_{i_k}ai1​​,...,aik​​ can be retrieved from ∣Ψ>|Ψ>∣Ψ> by a one-round Arthur-Merlin interactive protocol of size polynomial in nnn. This shows how to go around Holevo-Nayak's Theorem, using Arthur-Merlin proofs. We use the new representation to prove the following results: 1) Interactive proofs with quantum advice: We show that the class QIP/qpolyQIP/qpolyQIP/qpoly contains ALL languages. That is, for any language LLL (even non-recursive), the membership x∈Lx \in Lx∈L (for xxx of length nnn) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state ∣ΨL,n>|Ψ_{L,n} >∣ΨL,n​> (depending only on LLL and nnn). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. 2) PCP with only one query: We show that the membership x∈SATx \in SATx∈SAT (for xxx of length nnn) can be proved by a logarithmic-size quantum state ∣Ψ>|Ψ>∣Ψ>, together with a polynomial-size classical proof consisting of blocks of length polylog(n)polylog(n)polylog(n) bits each, such that after measuring the state ∣Ψ>|Ψ>∣Ψ> the verifier only needs to read {\bf one} block of the classical proof. While the first result is a straight forward consequence of the new representation, the second requires an additional machinery of quantum low-degree-test that may be interesting in its own right.
The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.