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:2510.04992 · Lecture notes in computer science

Less is More: On Copy Complexity in Quantum Cryptography

Prabhanjan Ananth, Eli Goldin

Published Jan 1, 2026• 4 citations
arXivHTMLPDF
DOI
10.1007/978-3-032-35409-9_5

Related papers

Multi-copy Security in Quantum Cryptography and More

Alper Çakan, Vipul Goyal, Fuyuki Kitagawa +2 more

arXiv:2510.12626•Lecture notes in computer science•Jan 1, 2026•3 citations

A Less Known Side of Quantum Cryptography

Naya Nagy, Marius Nagy, Selim G. Akl

Emergence, complexity and computation•Nov 4, 2016•2 citations

Optimal cloning of two known nonorthogonal quantum states

Wen‐Hai Zhang, Long-Bao Yu, Zhuo‐Liang Cao +1 more

Two known nonorthogonal quantum states can be cloned either deterministically or probabilistically. In this paper, we investigate quantum cloning by combining these two extreme cases, i.e., a trade-off between the copy fidelity and the success probability. For a special set of two known nonorthogonal quantum states, we start with an explicit unitary transformation and derive the copy fidelity as a function of the success probability. The result shows that the higher is the copy fidelity, the less is the success probability. This quantum cloning may have important applications in quantum cryptography.

Physical Review A•Aug 22, 2012•20 citations

A Meta-complexity Characterization of Quantum Cryptography

Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray +1 more

arXiv:2410.04984•Lecture notes in computer science•Jan 1, 2025•9 citations

A Meta-complexity Characterization of Minimal Quantum Cryptography

Bruno Pasqualotto Cavalar, Boyang Chen, Andrea Coladangelo +4 more

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.

arXiv:2510.07859•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•6 citations

A Strong Direct Product Theorem for Quantum Query Complexity

Troy Lee, Jérémie Roland

We show that quantum query complexity satisfies a strong direct product theorem. This means that computing $k$ copies of a function with less than $k$ times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in $k$. For a boolean function $f$ we also show an XOR lemma -- computing the parity of $k$ copies of $f$ with less than $k$ times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.

arXiv:1104.4468•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2012•22 citations
Two known nonorthogonal quantum states can be cloned either deterministically or probabilistically. In this paper, we investigate quantum cloning by combining these two extreme cases, i.e., a trade-off between the copy fidelity and the success probability. For a special set of two known nonorthogonal quantum states, we start with an explicit unitary transformation and derive the copy fidelity as a function of the success probability. The result shows that the higher is the copy fidelity, the less is the success probability. This quantum cloning may have important applications in quantum cryptography.
We show that quantum query complexity satisfies a strong direct product theorem. This means that computing kkk copies of a function with less than kkk times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in kkk. For a boolean function fff we also show an XOR lemma -- computing the parity of kkk copies of fff with less than kkk times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, characterizes bounded-error quantum query complexity. In particular, we show that the multiplicative adversary bound is always at least as large as the additive adversary bound, which is known to characterize bounded-error quantum query complexity.