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:2410.11827

Are uncloneable proof and advice states strictly necessary?

Chatterjee, Rohit, Srijita Kundu, Supartha Podder

Published Oct 15, 2024• 0 citations
arXivHTMLPDF

Abstract

Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by $k$ separate polynomial-time verifiers, for arbitrary polynomial $k$. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.

DOI
10.48550/arxiv.2410.11827

Related papers

Separating ClonableQMA and QCMA Relative to a Classical Oracle

Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung +1 more

Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.

cs.CCCross-listedarXiv:2610.06740•Oct 6, 2026•0 citations

Separating Quantum and Classical Advice with Good Codes

John Bostanci, Andrew Huang, Vinod Vaikuntanathan

We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof ($\mathsf{QMA}$) and the class of languages that can be verified with a classical proof ($\mathsf{QCMA}$). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice ($\mathsf{BQP}/\mathsf{qpoly}$) and the class of languages that can be decided with classical advice ($\mathsf{BQP}/\mathsf{poly}$), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.

quant-pharXiv:2602.09385•Feb 11, 2026•0 citations

Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

Xingjian Li, Liu, Qipeng, Angelos Pelecanos +1 more

It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly $\neq$ BQP/poly or QMA $\neq$ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly $\neq$ BQP/poly and QMA $\neq$ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.

arXiv:2303.04298•Leibniz international proceedings in informatics•Mar 8, 2023•2 citations

No Size-Preserving Amplification with Quantum Advice

Shih-Han Hung, Han-Hsuan Lin

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$.

quant-pharXiv:2610.03377•Oct 5, 2026•0 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•3 citations

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter +1 more

Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

quant-pharXiv:2609.38704•Oct 1, 2026•0 citations
Yes, we show that they are. We initiate the study of languages that necessarily need uncloneable quantum proofs and advice. We define strictly uncloneable versions of the classes QMA, BQP/qpoly and FEQP/qpoly (which is the class of relational problems solvable exactly with polynomial-sized quantum advice). Strictly uncloneable QMA is defined to be the class of languages in QMA that only have uncloneable proofs, i.e., given any family of candidate proof states, a polynomial-time cloning algorithm cannot act on it to produce states that are jointly usable by kkk separate polynomial-time verifiers, for arbitrary polynomial kkk. This is a stronger notion of uncloneable proofs and advice than those considered in previous works, which only required the existence of a single family of proof or advice states that are uncloneable. We show that in the quantum oracle model, there exist languages in strictly uncloneable QMA and strictly uncloneable BQP/qpoly. The language in strictly uncloneable QMA also gives a quantum oracle separation between QMA and the class cloneableQMA introduced by Nehoran and Zhandry (2024). We also show without using any oracles that the language, used by Aaronson, Buhrman and Kretschmer (2024) to separate FEQP/qpoly and FBQP/poly, is in strictly uncloneable FEQP/qpoly.
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.
We show an unconditional classical oracle separation between the class of languages that can be verified using a quantum proof (QMA\mathsf{QMA}QMA) and the class of languages that can be verified with a classical proof (QCMA\mathsf{QCMA}QCMA). Compared to the recent work of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC 2026), our proof is conceptually and technically simpler, and readily extends to other oracle separations. In particular, our techniques yield the first unconditional classical oracle separation between the class of languages that can be decided with quantum advice (BQP/qpoly\mathsf{BQP}/\mathsf{qpoly}BQP/qpoly) and the class of languages that can be decided with classical advice (BQP/poly\mathsf{BQP}/\mathsf{poly}BQP/poly), improving on the quantum oracle separation of Aaronson and Kuperberg (CCC 2007) and the classically-accessible classical oracle separation of Li, Liu, Pelecanos and Yamakawa (ITCS 2024). Our oracles are based on the code intersection problem introduced by Yamakawa and Zhandry (FOCS 2022), combined with codes that have extremely good list-recovery properties.
It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠\neq= BQP/poly or QMA ≠\neq= QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠\neq= BQP/poly and QMA ≠\neq= QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.
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.
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.
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes PostBQP\mathsf{PostBQP}PostBQP and PreciseBQP\mathsf{PreciseBQP}PreciseBQP, the exponentially precise variant of BQP\mathsf{BQP}BQP. Both classes equal PP\mathsf{PP}PP in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.