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:2302.01858 · Leibniz international proceedings in informatics

A Computational Separation Between Quantum No-Cloning and No-Telegraphing

Barak Nehoran, Mark Zhandry

Published Feb 3, 2023• 17 citations
arXivHTMLPDF

Abstract

Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on telegraphing, or sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is telegraphable if and only if it is clonable. Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and quantum oracles relative to which these states are efficiently clonable but not efficiently telegraphable. Given that the opposite scenario is impossible (states that can be telegraphed can always trivially be cloned), this gives the most complete quantum oracle separation possible between these two important no-go properties. We additionally study the complexity class clonableQMA, a subset of QMA whose witnesses are efficiently clonable. As a consequence of our main result, we give a quantum oracle separation between clonableQMA and the class QCMA, whose witnesses are restricted to classical strings. We also propose a candidate oracle-free promise problem separating these classes. We finally demonstrate an application of clonable-but-not-telegraphable states to cryptography, by showing how such states can be used to protect against key exfiltration.

DOI
10.4230/lipics.itcs.2024.82

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

Quantum Copy-Protection and Quantum Money

Scott Aaronson

Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f? This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs. Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption).

arXiv:1110.5353•IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•219 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

Quantum versus Classical Proofs and Advice

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA.We prove three results about this question.First, we give a "quantum oracle separation" between QMA and QCMA.More concretely, we show that any quantum algorithm needs Ω 2 n m+1 queries to find an n-qubit "marked state" |ψ , even if given an m-bit classical description of |ψ together with a quantum black box that recognizes |ψ .Second, we give an explicit QCMA protocol that nearly achieves this lower bound.Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful.In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups.Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem.Even with no assumptions, our protocol makes only polynomially many queries to the group oracle.We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2007•53 citations

Quantum Secret Sharing and Error Correction vs No-Cloning

Steven Chien, Ishani Mukherjee, Mark Zhandry

Secret sharing is ubiquitous throughout cryptography. All possible access structures are classically feasible, and in the case of threshold access structures, the protocols are even very efficient. However, when moving to the quantum setting, the no-cloning theorem shows that many access structures are impossible. In fact, no-cloning exactly characterizes feasibility: for thresholds, quantum secret sharing is possible if and only if the threshold $t$ is strictly more than $n/2$. In this work, we propose a variant of quantum secret sharing (QSS) where two or more identical copies of the input state are provided, but the output is only required to recover one copy. This notion circumvents the simple one-copy no-cloning obstruction, though the natural $k$-copy generalization still gives much milder obstructions. For thresholds using $k$ copies, no-cloning implies that QSS is impossible whenever $t\leq n/(k+1)$. It is tempting to hypothesize that no-cloning continues to exactly characterize the many-copy case. However, we show that this is not the case. We give positive results showing that multiple copies allow for going slightly beyond the single-copy obstruction: for thresholds, we construct QSS whenever $t>(n-k+1)/2$. On the other hand, we give a novel obstruction we call the Clique Path obstruction, which applies to arbitrary access structures. For thresholds, it shows that QSS is impossible whenever $t\leq (n-1)/k$. Our upper and lower bounds exactly match for $k=2$. Both our results leverage connections to the $k$-colorability of certain graphs derived from the access structure. We leave closing the gap for $k\geq 3$ copies as a fascinating direction for future work. Secret sharing is closely related to error correction, which can also be considered in the many-copy setting. Our results imply similar obstructions for quantum error correction for erasure channels.

quant-pharXiv:2610.00441•Oct 1, 2026•0 citations

Models and Methods for Developing Countermeasures Against Information Theft, Destruction, and Modification: The No-Cloning Theorem

Mikhail Pavlov

Abstract In modern quantum information science, the no-cloning theorem constitutes a fundamental principle stating that it is impossible to create an exact copy of an arbitrary unknown quantum state. This intrinsic limitation forms the basis of quantum security mechanisms and gives rise to unique phenomena such as quantum teleportation and superdense coding, which enable the transmission of quantum information without physically transferring the quantum state itself. Within the broader framework of quantum computation, algorithms such as Grover's algorithm provide quadratic speedup for unstructured search problems, though they do not always achieve optimal query complexity for certain classes of tasks. In such scenarios, quantum random walks offer an alternative paradigm capable of further reducing query complexity and enhancing search efficiency. This study examines the theoretical foundations and practical implications of the no-cloning theorem, quantum teleportation, superdense coding, and quantum random walks in the context of information security. Special attention is given to their role in designing countermeasure systems against information theft, destruction, and modification. Practical demonstrations are conducted using Qiskit on IBM quantum hardware, highlighting the applied significance and future potential of these quantum security mechanisms.

•Mar 4, 2026•0 citations
Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation theorem (the prohibition on telegraphing, or sending quantum states over classical channels without pre-shared entanglement). They are known to be equivalent, in the sense that a collection of quantum states is telegraphable if and only if it is clonable. Our main result suggests that this is not the case when computational efficiency is considered. We give a collection of quantum states and quantum oracles relative to which these states are efficiently clonable but not efficiently telegraphable. Given that the opposite scenario is impossible (states that can be telegraphed can always trivially be cloned), this gives the most complete quantum oracle separation possible between these two important no-go properties. We additionally study the complexity class clonableQMA, a subset of QMA whose witnesses are efficiently clonable. As a consequence of our main result, we give a quantum oracle separation between clonableQMA and the class QCMA, whose witnesses are restricted to classical strings. We also propose a candidate oracle-free promise problem separating these classes. We finally demonstrate an application of clonable-but-not-telegraphable states to cryptography, by showing how such states can be used to protect against key exfiltration.
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.
Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f? This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs. Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption).
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.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA = QCMA.We prove three results about this question.First, we give a "quantum oracle separation" between QMA and QCMA.More concretely, we show that any quantum algorithm needs Ω 2 n m+1 queries to find an n-qubit "marked state" |ψ , even if given an m-bit classical description of |ψ together with a quantum black box that recognizes |ψ .Second, we give an explicit QCMA protocol that nearly achieves this lower bound.Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful.In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups.Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem.Even with no assumptions, our protocol makes only polynomially many queries to the group oracle.We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
Secret sharing is ubiquitous throughout cryptography. All possible access structures are classically feasible, and in the case of threshold access structures, the protocols are even very efficient. However, when moving to the quantum setting, the no-cloning theorem shows that many access structures are impossible. In fact, no-cloning exactly characterizes feasibility: for thresholds, quantum secret sharing is possible if and only if the threshold ttt is strictly more than n/2n/2n/2. In this work, we propose a variant of quantum secret sharing (QSS) where two or more identical copies of the input state are provided, but the output is only required to recover one copy. This notion circumvents the simple one-copy no-cloning obstruction, though the natural kkk-copy generalization still gives much milder obstructions. For thresholds using kkk copies, no-cloning implies that QSS is impossible whenever t≤n/(k+1)t\leq n/(k+1)t≤n/(k+1). It is tempting to hypothesize that no-cloning continues to exactly characterize the many-copy case. However, we show that this is not the case. We give positive results showing that multiple copies allow for going slightly beyond the single-copy obstruction: for thresholds, we construct QSS whenever t>(n−k+1)/2t>(n-k+1)/2t>(n−k+1)/2. On the other hand, we give a novel obstruction we call the Clique Path obstruction, which applies to arbitrary access structures. For thresholds, it shows that QSS is impossible whenever t≤(n−1)/kt\leq (n-1)/kt≤(n−1)/k. Our upper and lower bounds exactly match for k=2k=2k=2. Both our results leverage connections to the kkk-colorability of certain graphs derived from the access structure. We leave closing the gap for k≥3k\geq 3k≥3 copies as a fascinating direction for future work. Secret sharing is closely related to error correction, which can also be considered in the many-copy setting. Our results imply similar obstructions for quantum error correction for erasure channels.
Abstract In modern quantum information science, the no-cloning theorem constitutes a fundamental principle stating that it is impossible to create an exact copy of an arbitrary unknown quantum state. This intrinsic limitation forms the basis of quantum security mechanisms and gives rise to unique phenomena such as quantum teleportation and superdense coding, which enable the transmission of quantum information without physically transferring the quantum state itself. Within the broader framework of quantum computation, algorithms such as Grover's algorithm provide quadratic speedup for unstructured search problems, though they do not always achieve optimal query complexity for certain classes of tasks. In such scenarios, quantum random walks offer an alternative paradigm capable of further reducing query complexity and enhancing search efficiency. This study examines the theoretical foundations and practical implications of the no-cloning theorem, quantum teleportation, superdense coding, and quantum random walks in the context of information security. Special attention is given to their role in designing countermeasure systems against information theft, destruction, and modification. Practical demonstrations are conducted using Qiskit on IBM quantum hardware, highlighting the applied significance and future potential of these quantum security mechanisms.