Pith. sign in

REVIEW 3 major objections 4 minor 81 references

The Hardness of Learning Quantum Circuits and its Cryptographic Applications

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that if it is computationally hard to learn or clone the output state of a random quantum circuit, then that hardness alone yields secure quantum cryptography—one-way state generators, digital signatures, bit commitments…

desk verdict A promising, genuinely useful paper whose main theorems survive a proof repair in Claim 4.9, but whose appendix and one side argument need real work before it is fully rigorous. read the letter →

arxiv 2504.15343 v1 pith:775L3CMT submitted 2025-04-21 quant-ph cs.CR

Bill Fefferman , Soumik Ghosh , Makrand Sinha , Henry Yuen This is my paper · ORCID
classification quant-phcs.CR MSC 68Q1281P68
keywords quantumcryptographyone-waystategeneratorsbitcommitmentsrandomcircuitscomputationalno-learningassumptionno-cloningclassicalshadowsNISQ-friendly
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that two concrete, average-case hardness assumptions about random quantum circuits can serve as the foundation for quantum cryptography. The Computational No-Learning Assumption says a polynomial-time adversary, given copies of $|C\rangle = C|0^n\rangle$ for a random circuit $C$, cannot output a circuit $D$ whose state approximates $|C\rangle$; the Computational No-Cloning Assumption says it cannot produce an extra approximate copy. The paper proves that the first assumption yields a cryptographically secure one-way state generator, and the second yields a quantum bit commitment with statistical hiding and computational binding, both amplifiable to negligible error. It gives black-box evidence for both assumptions and constructs noise-tolerant versions suitable for near-term quantum devices. A sympathetic reader would care because these are concrete instantiations of quantum cryptography whose security may hold without one-way functions.

What carries the argument

The load-bearing objects are the random circuit ensemble $\mathcal{C}_n$—$n$-qubit 1D brickwork circuits of depth $d = \log^2 n$ with a gate set that includes the Clifford group—and their output states $|C\rangle = C|0^n\rangle$. The No-Learning Conjecture (1.1) posits that no QPT algorithm can turn $\mathrm{poly}(n)$ copies of $|C\rangle$ into a circuit $D \in \mathcal{C}_n$ with $|\langle C|D\rangle|^2 \ge \varepsilon$ with probability larger than $\delta$; the No-Cloning Conjecture (1.2) posits that no QPT algorithm can turn $k$ copies into a $(k+1)$-copy state with fidelity at least $\varepsilon$ with probability larger than $\delta$. The proofs run on three pieces of machinery: the classical shadows protocol of Huang–Kueng–Preskill, which supplies the inefficient learner used as an upper bound and as a coherent sub-routine in the hiding proof; parallel repetition plus the computational Chernoff bound, which amplifies weak security; and Werner's optimal-cloning bound, which is the base case of the black-box lower bound. For the NISQ-friendly variant, threshold repetition replaces full parallel repetition, with a computational Chernoff bound showing that inverting noticeably more than a $\gamma$ fraction of blocks is hard.

What would settle it

Compute or bound $\mathbb{E}_{C \gets \mathcal{C}_n}\big[C^{\otimes 2}|0\rangle\langle 0|^{\otimes 2}(C^\dagger)^{\otimes 2}\big]$ for the $n$-qubit 1D brickwork ensemble of depth $\log^2 n$ with the Clifford-containing gate set; if this differs from the projector onto the symmetric subspace of $(\mathbb{C}^2)^{\otimes 2}$, the ensemble is not an exact 1-design and Claim 4.9's correctness derivation fails as written.

Watch

Extended reading notes

Core claim

The central claim is that hardness of learning and cloning random-circuit output states is not merely a learning-theoretic curiosity but a usable cryptographic foundation. Theorems 4.5 and 4.12 (with Claims 4.9–4.11) state that, under the $\varepsilon$-No-Learning Assumption for any $\varepsilon \le 1 - 1/\mathrm{poly}(n)$, the random circuit OWSG—key is a circuit description $C$, output is $|C\rangle$—can be amplified by parallel repetition to a cryptographically secure OWSG; and under the $\delta$-No-Cloning Assumption, the superposition-over-circuits commitment (Protocol 4.8) satisfies correctness, $4\varepsilon$-statistical hiding, and $(2-\delta)\delta$-computational binding, which a further amplification chain makes negligible in both parameters. The paper also proves Theorem 1.5: in a state-preparation-oracle model, any $T$-query algorithm given $k$ copies of a Haar-random target state has cloning fidelity at most $2^{-n/4}(2T + k + 1)$, exponentially small unless both $T$ and $k$ are exponential. All of these results are conditional on the two conjectures, and the conjectures themselves are what the paper offers as its new foundational assumptions.

Load-bearing premise

The commitment's correctness rests on the claim that the uniform distribution over the fixed-depth 1D brickwork circuit ensemble is an exact 1-design, justified only by invariance under a final random Pauli layer; if that ensemble is not a 1-design, the negligible-overlap bound between commitments to 0 and 1 is unsupported.

Editorial extensions

If this is right

  • If $\varepsilon$-No-Learning holds for any $\varepsilon \le 1 - 1/\mathrm{poly}(n)$, then a cryptographically secure one-way state generator exists, and cryptographic tasks known to follow from OWSGs—including quantum digital signatures and commitments via existing reductions—can be instantiated concretely from random circuits.
  • If $\delta$-No-Cloning holds, Protocol 4.8 is a quantum bit commitment with negligible hiding and binding error after the amplification chain of Lemma 4.14, giving a direct route from a native quantum hardness assumption to commitments.
  • The black-box lower bound (Theorem 1.5) means that in the oracle model, cloning a Haar-random state from $k$ copies requires $2^{\Omega(n)}$ queries or copies, so shadow-tomography-style attacks cannot be efficient in that model.
  • Under an inverse-polynomial-fidelity noise model, the threshold-repeated OWSG and the digital signature scheme of Protocol 5.8 remain correct on noisy hardware while remaining secure against noiseless polynomial-time adversaries.
  • Because No-Cloning implies a weak No-Learning assumption (Corollary 1.3), the two conjectures form a hierarchy: the stronger cloning assumption buys the simpler commitment construction, while the weaker learning assumption already buys OWSGs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the exact 1-design claim in Claim 4.9 turns out to fail for fixed-depth brickwork circuits, the commitment's correctness proof needs a replacement; an approximate 1-design or a modified ensemble with random Pauli layers could restore the argument, and this is directly testable.
  • The paper's black-box model with Haar-random states can be adapted to distinguish no-learning from no-cloning: a separation would require an oracle where cloning is easy but learning a classical description remains hard, extending the discussion near Corollary 1.3.
  • The threshold repetition technique suggests a more general recipe: any cryptographic primitive with a gap between honest noisy correctness and adversarial success probability can be amplified by a computational Chernoff bound, which might apply to other NISQ-friendly primitives beyond signatures.
  • The finite-size estimates in Section 5, such as a roughly 4,000-qubit public key for $n=20$ and depth $20$, should be re-derived for different noise models and circuit architectures before drawing conclusions about near-term feasibility; the paper itself flags this dependence on noise assumptions.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes two concrete average-case hardness assumptions about learning or cloning output states of random quantum circuits: the Computational No-Learning Assumption (Conjecture 1.1) and the Computational No-Cloning Assumption (Conjecture 1.2). Under these assumptions it constructs a one-way state generator from random circuits (Section 4.1), a quantum bit commitment scheme (Section 4.2), and, under an additional threshold direct-product-type bound, NISQ-friendly OWSGs and digital signature schemes (Section 5). It also proves a black-box lower bound for cloning in a state preparation oracle model (Section 3) and discusses evidence and relations to concurrent work.

Significance. If the paper's assumptions and proofs are made rigorous, the results would be a valuable step toward concrete quantum cryptographic primitives that do not rely on classical one-way functions. The commitment construction from the No-Cloning Assumption is direct and conceptually appealing, and the black-box lower bound in Section 3 is a clean contribution that gives real evidence for the proposed hardness assumptions. The NISQ-friendly framing is also timely. At the same time, the OWSG construction is essentially a restatement of the No-Learning Assumption, and the paper candidly notes this equivalence; the novelty lies in the commitment, signature, and NISQ-oriented consequences. Two load-bearing proof points currently need repair: the exact 1-design assertion used for commitment correctness and the quantum adaptation of the Impagliazzo-Kabanets threshold direct product theorem used for the NISQ-friendly constructions.

major comments (3)
  1. [Section 4.2, Claim 4.9] The correctness proof of the commitment scheme relies on the assertion that the uniform distribution over the fixed-depth brickwork ensemble C_n is an exact 1-design, justified by invariance under appending a layer of random Pauli operators. This justification is not valid as written: adding a Pauli layer changes the circuit depth, so the ensemble of depth-d circuits is not invariant under that operation, and merely having a gate set that 'includes' the Clifford group does not imply that uniform sampling from the gate set gives the exact twirling channel. This is load-bearing because the bound |<ψ0|ψ1>|^2 ≤ 2^{-n} is exactly what gives the correctness property of Protocol 4.8. The underlying claim may be salvageable by a different argument, for example by using the first brickwork layer of independently random two-qubit Clifford gates as an exact depolarizing channel, but the manuscript must supply a correct proof or modify the ensemble definition.
  2. [Appendix A, Lemma A.1 and Claims A.3/A.5] The computational Chernoff bound for OWSGs is not actually proved. The proof delegates the core technical work to [IK10] with the statements that the arguments go through 'essentially unchanged' or 'can be checked' in the quantum setting, but this is not demonstrated. The Impagliazzo-Kabanets threshold direct product theorem is formulated for classical randomized algorithms with a classical predicate, whereas here the verification procedure is a quantum measurement; conditioning on its acceptance can disturb the state and entangle the output with the verification register. A formal reduction is required because Corollary 5.5 and the NISQ-friendly digital signature scheme of Section 5.2 depend on this lemma. As written, the claimed security of the threshold repetition is unsupported.
  3. [Lemma 4.14, final sentence] The proof of the amplification lemma ends by claiming that after switching flavors once more the final commitment satisfies 'negl(n)-statistical hiding and negl(n)-statistical binding'. This contradicts the impossibility of statistically hiding and statistically binding quantum commitments [BCMS97], and it also contradicts the lemma statement, which promises statistical hiding and computational binding. The preceding steps appear to yield the correct conclusion if the last flavor switch is described as producing computational binding; the text should be corrected to avoid this internal inconsistency.
minor comments (4)
  1. [Throughout] The notation 'log2n' (for example in the definition of C_n and in Theorem 4.5) is ambiguous; it should be typeset as log^2 n so that the claimed polynomial parameter choices are clear.
  2. [Section 4.2, Claim 4.10] In the overlap computation after applying V†, the inner product with <0^r|⊗<C|^{⊗k} appears to be a typo: since V acts on k−1 copies of |C>, the factor should be <0^r|⊗<C|^{⊗(k−1)}. The final expression is correct with this replacement, but the displayed formula as written is dimensionally inconsistent.
  3. [Definition 4.7] The definition of correctness for a noninteractive quantum commitment is nonstandard: it is stated as orthogonality of |ψ0> and |ψ1> rather than as the success probability of an honest opening/verification procedure. Since later arguments cite standard parallel repetition and flavor-switching theorems, the authors should clarify how this definition connects to the standard correctness notion used in those theorems.
  4. [Corollary 1.3] The proof of Corollary 1.3 is only a sketch and refers to a calculation 'virtually identical' to Claim 4.10. Because the corollary is used to position the No-Cloning Assumption as stronger than No-Learning, a complete proof or an explicit pointer to a full proof would improve the paper.

Circularity Check

1 steps flagged · score 3.0 of 10

The random-circuit OWSG is the No-Learning assumption restated; the commitment and signature constructions are genuine reductions, so circularity is partial and localized.

  1. self definitional [Section 1.3.1 and Section 4.1 (Lemma 4.4, Protocol 4.3, versus Conjecture 1.1)]
    "The No-Learning Assumption (Conjecture 1.1) is essentially equivalent to the existence of a OWSG, namely the Random Circuit OWSG described below in Figure 1. ... for negligible ε ... the ε-No-Learning Assumption is easily seen to be equivalent to the security of the Random Circuit OWSG. When ε is larger, say even up to 1−1/poly(n), the equivalence still holds; this relies on hardness amplification techniques for OWSGs [MY22a, BQSY24]. ... Assuming ε-No-Learning (Conjecture 1.1), the random circuit OWSG has security error (2−ε)ε."

    Under Protocol 4.3, Gen(C)=|C>=C|0^n>, which is exactly the random state drawn in Conjecture 1.1, and Ver(C,|D>) accepts with probability |<C|D>|^2, exactly the overlap event quantified in the conjecture. In both games the adversary receives poly(n) copies of |C> and must output a description D∈C_n whose output state has large fidelity with |C>. Thus the OWSG security game is the No-Learning event under a different name. Theorem 4.5's existence claim is the assumption itself, not a consequence derived from independent structure. The paper admits this ('essentially equivalent'), so the step is a transparent definitional equivalence rather than a hidden circularity; it does not by itself taint the later commitment, signature, or black-box reductions.

full rationale

Most of the paper is a chain of reductions from the two conjectures. The OWSG section is the only place where a claimed construction is the assumption restated: the random-circuit OWSG's security game coincides with the No-Learning event. This is acknowledged by the authors and is more a definitional observation than a derivation. The commitment scheme (Protocol 4.8) is a genuine construction: hiding uses the classical-shadows learning procedure as a unitary map, binding reduces to No-Cloning via Jensen's inequality, and amplification uses published parallel-repetition and flavor-switching theorems ([BQSY24], [HMY23]); none of these are the conjectures restated. The black-box lower bound (Theorem 1.5) is independent evidence based on a hybrid argument and Werner's cloning bounds. One correctness proof, Claim 4.9, asserts 1-design invariance under appended Pauli layers; as written that invariance is not evident for fixed-depth brickwork ensembles, but this is a proof gap, not circularity, and the numeric claim is repairable by a first-layer depolarization argument. The self-citations in the amplification steps are to published theorems with proofs, so they are not load-bearing circularity. Overall, circularity is confined to the OWSG identification, warranting a moderate score rather than a high one.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The paper's cryptographic results are conditional on two new conjectures, the Computational No-Learning and No-Cloning Assumptions, which are not proven. The proofs further rely on cited theorems from the literature (classical shadows, Werner's optimal cloning, Impagliazzo-Kabanets threshold direct product, Morimae-Yamakawa parallel repetition, quantum flavor switching). There are no fitted data parameters, but the circuit depth d = log^2 n is a manually chosen construction parameter.

free parameters (1)
  • Circuit depth d = log^2 n = log^2 n
    Chosen by hand so that current learning algorithms become superpolynomial; all hardness conjectures and constructions are defined for this depth.
assumptions (7)
  • ad hoc to paper Computational No-Learning Assumption (Conjecture 1.1): no QPT algorithm can output a circuit D with |<C|D>|^2 >= ε from poly(n) copies of |C> with probability > δ.
    Central unproven postulate on which OWSG and signature constructions rest.
  • ad hoc to paper Computational No-Cloning Assumption (Conjecture 1.2): no QPT algorithm can produce a (k+1)-copy approximation from k copies of |C> with fidelity >= ε with probability > δ.
    Central unproven postulate for the commitment scheme.
  • ad hoc to paper Uniform distribution over C_n forms an exact 1-design.
    Asserted in Claim 4.9 without adequate proof; appending a random Pauli layer would change circuit depth, so the claim is doubtful for fixed-depth brickwork circuits.
  • domain assumption Noise model: noisy execution of circuits preserves fidelity at least 1/p(nd).
    Assumed for NISQ-friendliness in Corollary 5.5; the paper acknowledges it requires noise rate to decrease with system size.
  • standard math Classical shadows protocol [HKP20] can be implemented as a coherent unitary for the Uhlmann argument.
    Standard coherent simulation of a quantum algorithm; acceptable but not detailed.
  • standard math Optimal cloning bound of Werner [Wer98] for Haar random states.
    Used as base case in Theorem 1.5.
  • ad hoc to paper Threshold direct product theorem of Impagliazzo-Kabanets [IK10] extends to quantum verification.
    Stated to hold 'essentially unchanged' in Lemma A.1 but details are not provided; potential gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Hardness of Learning Quantum Circuits and its Cryptographic Applications." pith.science (2026). https://pith.science/paper/775L3CMT

@misc{pith2026250415343,
  author       = {Pith},
  title        = {Pith review of: The Hardness of Learning Quantum Circuits and its Cryptographic Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/775L3CMT}},
  note         = {Machine review of arXiv:2504.15343}
}
read the original abstract

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

Figures

Figures reproduced from arXiv: 2504.15343 by the authors.

Figure 1
Figure 1. Construction of one-way state generator from random circuits. [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Commitment scheme based on random circuits [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. A plot of public key size versus circuit depth. [PITH_FULL_IMAGE:figures/full_fig_p038_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

81 extracted references · 70 canonical work pages

  1. [1]

    The computational complexity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 333--342, 2011

    2011

  2. [2]

    Quantum error correction below the surface code threshold

    Rajeev Acharya, Laleh Aghababaie-Beni, Igor Aleiner, Trond I Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, et al. Quantum error correction below the surface code threshold. arXiv preprint arXiv:2408.13687 , 2024

    arXiv 2024

  3. [3]

    Quantum supremacy using a programmable superconducting processor

    Frank Arute, Kunal Arya, Ryan Babbush, and et al. Quantum supremacy using a programmable superconducting processor. Nature , 574:505--510, 2019

    work page 2019

  4. [4]

    Polynomial simulations of decohered quantum computers

    Dorit Aharonov and Michael Ben-Or . Polynomial simulations of decohered quantum computers. In Proceedings of 37th Conference on Foundations of Computer Science , page 46–55. IEEE Comput. Soc. Press, 1996

    work page 1996

  5. [5]

    Complexity-theoretic foundations of quantum supremacy experiments

    Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference ( CCC 2017) , pages 22:1--22:67. Schloss Dagstuhl--Leibniz-Zentrum f \" u r Informatik, 2017

    work page 2017

  6. [6]

    A polynomial-time classical algorithm for noisy random circuit sampling

    Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing ( STOC 2023) , pages 1307--1318. ACM, 2023

    work page 2023

  7. [7]

    Grilo, and Aarthi Sundaram

    Srinivasan Arunachalam, Alex B. Grilo, and Aarthi Sundaram. Quantum hardness of learning shallow classical circuits. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020) , pages 291--304, New York, NY, USA, 2020. ACM

    work page 2020

  8. [8]

    Certified randomness from quantum supremacy

    Scott Aaronson and Shih - Han Hung. Certified randomness from quantum supremacy. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 933--944. ACM , 2023

    work page 2023

Show all 81 references
  1. [9]

    A simple proof that T offoli and H adamard are quantum universal

    Dorit Aharonov. A simple proof that T offoli and H adamard are quantum universal. arXiv preprint quant-ph/0301040 , 2003

    2003 arXiv

  2. [10]

    Cryptography from pseudorandom quantum states

    Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2022 , volume 13508 of Lecture Notes in Computer Science , pages 208--236. Springer, 2022

    2022

  3. [11]

    Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani

    Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing , 26(5):1510--1523, 1997

    1997

  4. [12]

    On certified randomness from fourier sampling or random circuit sampling, 2024

    Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, and Avishay Tal. On certified randomness from fourier sampling or random circuit sampling, 2024

    2024

  5. [13]

    A brief review on the impossibility of quantum bit commitment

    Gilles Brassard, Claude Cr \'e peau, Dominic Mayers, and Louis Salvail. A brief review on the impossibility of quantum bit commitment. arXiv preprint quant-ph/9712023 , 1997

    1997 arXiv

  6. [14]

    Oracle separation between quantum commitments and quantum one-wayness

    John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. arXiv preprint arXiv:2410.03358 , 2024

    2024 arXiv

  7. [15]

    On the computational hardness needed for quantum cryptography

    Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) . Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  8. [16]

    Logical quantum processor based on reconfigurable atom arrays

    Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, et al. Logical quantum processor based on reconfigurable atom arrays. Nature , 626(7997):58--65, 2024

    2024

  9. [17]

    Unitary complexity and the U hlmann transformation problem

    John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary complexity and the U hlmann transformation problem. arXiv preprint arXiv:2306.13073 , 2023

    2023 arXiv

  10. [18]

    Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor, Advances in Cryptology — CRYPTO '93: 13th Annual International Cryptology Conference, Santa Barbara, California, USA, Augu...

    1993

  11. [19]

    On the complexity and verification of quantum random circuit sampling

    Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics , 15(2):159--163, 2019

    2019

  12. [20]

    Efficient quantum pseudorandomness from hamiltonian phase states, 2024

    John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba. Efficient quantum pseudorandomness from hamiltonian phase states, 2024

    2024

  13. [21]

    A new world in the depths of microcrypt: Separating OWSGs and quantum money from QEFID

    Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating OWSGs and quantum money from QEFID . Cryptology ePrint Archive, Paper 2024/1567, 2024

    2024

  14. [22]

    An efficient quantum parallel repetition theorem and applications

    John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen. An efficient quantum parallel repetition theorem and applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing ( STOC 2024) . ACM, 2024

    2024

  15. [23]

    A Cryptographic Perspective on the Verifiability of Quantum Advantage

    Nai-Hui Chia, Honghao Fu, Fang Song, and Penghui Yao. A Cryptographic Perspective on the Verifiability of Quantum Advantage . 10 2023

    2023

  16. [24]

    Cavalar, Eli Goldin, Matthew Gray, and Peter Hall

    Bruno P. Cavalar, Eli Goldin, Matthew Gray, and Peter Hall. A meta-complexity characterization of quantum cryptography, 2024

    2024

  17. [25]

    Learning algorithms from natural proofs

    Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Proceedings of the 31st Computational Complexity Conference (CCC 2016) , volume 50 of Leibniz International Proceedings in Informatics (LIPIcs) , page...

    2016

  18. [26]

    Quantum State Learning Implies Circuit Lower Bounds

    Nai-Hui Chia, Daniel Liang, and Fang Song. Quantum State Learning Implies Circuit Lower Bounds . 5 2024

    2024

  19. [27]

    Random quantum circuits transform local noise into global white noise

    Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brand \ a o. Random quantum circuits transform local noise into global white noise. Communications in Mathematical Physics , 405(3):78, 2024

    2024

  20. [28]

    From average case complexity to improper learning complexity, 2014

    Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity, 2014

    2014

  21. [29]

    Gorshkov, Bill Fefferman, and Michael J

    Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V. Gorshkov, Bill Fefferman, and Michael J. Gullans. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum , 3(4), December 2022

    2022

  22. [30]

    Effect of nonunital noise on random-circuit sampling

    Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. Effect of nonunital noise on random-circuit sampling. PRX Quantum , 5(3), July 2024

    2024

  23. [31]

    Anti-concentration for the unitary haar measure and applications to random quantum circuits, 2024

    Bill Fefferman, Soumik Ghosh, and Wei Zhan. Anti-concentration for the unitary haar measure and applications to random quantum circuits, 2024

    2024

  24. [32]

    Module- L attice-based K ey- E ncapsulation M echanism S tandard

    NIST FIPS203. Module- L attice-based K ey- E ncapsulation M echanism S tandard. Federal Information Processing Standards Publication , 2023

    2023

  25. [33]

    Foundations of C ryptography: V olume 2, B asic A pplications , volume 2

    Oded Goldreich. Foundations of C ryptography: V olume 2, B asic A pplications , volume 2. Cambridge U niversity P ress, 2001

    2001

  26. [34]

    Computational complexity of learning efficiently generatable pure states

    Taiga Hiroka and Min-Hsiu Hsieh. Computational complexity of learning efficiently generatable pure states. arXiv preprint arXiv:2410.04373 , 2024

    2024 arXiv

  27. [35]

    A pseudorandom generator from any one-way function

    Johan H stad, Russell Impagliazzo, Leonid A Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing , 28(4):1364--1396, 1999

    1999

  28. [36]

    Predicting many properties of a quantum system from very few measurements

    Hsin - Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020

    2020

  29. [37]

    Hsin - Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. Learning shallow quantum circuits. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing ( STOC 2023) , pages 1343--1351. ACM, 2023

    2023

  30. [38]

    Quantum cryptography and meta-complexity, 2024

    Taiga Hiroka and Tomoyuki Morimae. Quantum cryptography and meta-complexity, 2024

    2024

  31. [39]

    From the hardness of detecting superpositions to cryptography: Q uantum public key encryption and commitments

    Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. From the hardness of detecting superpositions to cryptography: Q uantum public key encryption and commitments. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 639--667. Sp...

    2023

  32. [40]

    Certifying almost all quantum states with few single-qubit measurements, 2024

    Hsin-Yuan Huang, John Preskill, and Mehdi Soleimanifar. Certifying almost all quantum states with few single-qubit measurements, 2024

    2024

  33. [41]

    Constructive P roofs of C oncentration B ounds

    Russell Impagliazzo and Valentine Kabanets. Constructive P roofs of C oncentration B ounds. Electron. Colloquium Comput. Complex. , TR10-072 , 2010

    2010

  34. [42]

    Impagliazzo and L.A

    R. Impagliazzo and L.A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science , pages 812--821 vol.2, 1990

    1990

  35. [43]

    A personal view of average-case complexity

    Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the 10th Annual Structure in Complexity Theory Conference , pages 134--147. IEEE Computer Society, 1995

    1995

  36. [44]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi - Kai Liu, Fang Song, John Watrous, and Henry Yuen. Pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2018 , volume 10993 of Lecture Notes in Computer Science , pages 126--152. Springer, 2018

    2018

  37. [45]

    Kim, and Daniel Ranard

    Hyun-Soo Kim, Isaac H. Kim, and Daniel Ranard. Learning state preparation circuits for quantum phases of matter, 2024

    2024

  38. [46]

    Quantum cryptography in algorithmica

    William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing ( STOC 2023) , pages 1589--1602. ACM, 2023

    2023

  39. [47]

    Quantum-computable one-way functions without one-way functions, 2024

    William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions, 2024

    2024

  40. [48]

    Quantum pseudorandomness and classical complexity

    William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography ( TQC 2021) , pages 2:1--2:20. Schloss Dagstuhl--Leibniz-Zentrum f \" u r Informatik, 2021

    2021

  41. [49]

    Klivans and Alexander A

    Adam R. Klivans and Alexander A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 553--562. IEEE, 2006

    2006

  42. [50]

    Commitments from quantum one-wayness

    Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 968--978, 2024

    2024

  43. [51]

    Founding Q uantum C ryptography on Q uantum A dvantage, or, T owards C ryptography from \#P - H ardness

    Dakshita Khurana and Kabir Tomer. Founding Q uantum C ryptography on Q uantum A dvantage, or, T owards C ryptography from \#P - H ardness. arXiv preprint arXiv:2409.15248 , 2024

    2024 arXiv

  44. [52]

    Cryptographic limitations on learning boolean formulae and finite automata

    Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM) , 41(1):67--95, 1994

    1994

  45. [53]

    Parallelization, amplification, and exponential time simulation of quantum interactive proof systems

    Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 608--617, 2000

    2000

  46. [54]

    Constructing digital signatures from a one-way function

    Leslie Lamport. Constructing digital signatures from a one-way function. Technical Report CSL-98, SRI International Computer Science Laboratory, 1979

    1979

  47. [55]

    Learning quantum states prepared by shallow circuits in polynomial time

    Zeph Landau and Yunchao Liu. Learning quantum states prepared by shallow circuits in polynomial time. arXiv preprint arXiv:2410.23618 , 2024

    2024 arXiv

  48. [56]

    Constant depth circuits, F ourier transform, and learnability

    Nati Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, F ourier transform, and learnability. Journal of the Association for Computing Machinery , 40(3):607--620, 1993

    1993

  49. [57]

    A one-query lower bound for unitary synthesis and breaking quantum cryptography

    Alex Lombardi, Fermi Ma, and John Wright. A one-query lower bound for unitary synthesis and breaking quantum cryptography. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, ...

    2024

  50. [58]

    On ideal lattices and learning with errors over rings

    Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, Advances in Cryptology -- EUROCRYPT 2010 , volume 6110 of Lecture Notes in Computer Science , pages 1--23. Springer, 2010

    2010

  51. [59]

    Noise-induced shallow circuits and absence of barren plateaus, 2024

    Antonio Anna Mele, Armando Angrisani, Soumik Ghosh, Sumeet Khatri, Jens Eisert, Daniel Stilck França, and Yihui Quek. Noise-induced shallow circuits and absence of barren plateaus, 2024

    2024

  52. [60]

    Cryptographic characterization of quantum advantage, 2024

    Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage, 2024

    2024

  53. [61]

    Morvan, B

    A. Morvan, B. Villalonga, X. Mi, et al. Phase transition in random circuit sampling. Nature , 616:70--76, 2023

    2023

  54. [62]

    One-wayness in quantum cryptography

    Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. arXiv preprint arXiv:2210.03394 , 2022

    2022 arXiv

  55. [63]

    Quantum commitments and signatures without one-way functions

    Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Annual International Cryptology Conference , pages 269--295. Springer, 2022

    2022

  56. [64]

    FIPS 204 : M odule- L attice- B ased D igital S ignature S tandard, 2024

    National Institute of Standards and Technology . FIPS 204 : M odule- L attice- B ased D igital S ignature S tandard, 2024

    2024

  57. [65]

    Hardness vs randomness

    Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences , 49(2):149--167, 1994

    1994

  58. [66]

    A computational separation between quantum no-cloning and no-telegraphing

    Barak Nehoran and Mark Zhandry. A computational separation between quantum no-cloning and no-telegraphing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2024

    2024

  59. [67]

    On classical simulation algorithms for noisy boson sampling, 2023

    Changhun Oh, Liang Jiang, and Bill Fefferman. On classical simulation algorithms for noisy boson sampling, 2023

    2023

  60. [68]

    Oliveira and Rahul Santhanam

    Igor C. Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness, 2016

    2016

  61. [69]

    The learning stabilizers with noise problem, 2024

    Alexander Poremba, Yihui Quek, and Peter Shor. The learning stabilizers with noise problem, 2024

    2024

  62. [70]

    Hard quantum extrapolations in quantum cryptography

    Luowen Qian, Justin Raizes, and Mark Zhandry. Hard quantum extrapolations in quantum cryptography. arXiv preprint arXiv:2409.16516 , 2024

    2024 arXiv

  63. [71]

    Ryan-Anderson, C

    C. Ryan-Anderson, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, E. Nielsen, D. Regaldo, S. Ryan, J. Sedlacek, R. T. Sutherland, E. Tirrito, C. Volin, T. Walker, K. White, J. Wootton, and K. Wright. Demonstration of logical qubits and repeated error correction with better-th...

    2023

  64. [72]

    On lattices, learning with errors, random linear codes, and cryptography, 2024

    Oded Regev. On lattices, learning with errors, random linear codes, and cryptography, 2024

    2024

  65. [73]

    Quantum computation with programmable neutral-atom arrays

    Mark Saffman et al. Quantum computation with programmable neutral-atom arrays. Nature Physics , 2023

    2023

  66. [74]

    A. Uhlmann. The ``transition probability'' in the state space of a * -algebra. Reports on Mathematical Physics , 9(2):273--279, 1976

    1976

  67. [75]

    Quantum advantage with gaussian boson sampling in photonic quantum computers

    Christian Weedbrook et al. Quantum advantage with gaussian boson sampling in photonic quantum computers. Nature Physics , 2022. Preprint

    2022

  68. [76]

    Optimal cloning of pure states

    Reinhard F Werner. Optimal cloning of pure states. Physical Review A , 58(3):1827, 1998

    1998

  69. [77]

    General properties of quantum bit commitments

    Jun Yan. General properties of quantum bit commitments. In International Conference on the Theory and Application of Cryptology and Information Security , pages 628--657. Springer, 2022

    2022

  70. [78]

    Quantum computational advantage via 62-qubit superconducting processor

    Qi Zhao, Hao Chen, Xiao Yuan, et al. Quantum computational advantage via 62-qubit superconducting processor. Physical Review Letters , 127(18):180501, 2021

    2021

  71. [79]

    Phase-programmable gaussian boson sampling using stimulated squeezed light

    Han - Sen Zhong, Yuan Li, et al. Phase-programmable gaussian boson sampling using stimulated squeezed light. Physical Review Letters , 127(18):180502, 2021

    2021

  72. [80]

    Learning quantum states and unitaries of bounded gate complexity

    Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C Caro. Learning quantum states and unitaries of bounded gate complexity. PRX Quantum , 5(4):040306, 2024

    2024

  73. [81]

    Quantum computational advantage using photons

    Han - Sen Zhong, Hui Wang, Yi - Han Deng, et al. Quantum computational advantage using photons. Science , 370(6523):1460--1463, 2020

    2020

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.