Pith. sign in

REVIEW 2 major objections 5 minor 39 references

How to Verify that a Small Device is Quantum, Unconditionally

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper constructs proofs of quantumness whose security holds unconditionally as long as the malicious prover's memory is bounded, with one protocol requiring just n+2 qubits for the honest prover.

desk verdict Novel bounded-storage proof-of-quantumness constructions, but Theorem 1 rests on a misreading of Raz's time-space tradeoff; Protocol 2 is the salvageable half. read the letter →

arxiv 2505.23978 v1 pith:ZAIP7RQ7 submitted 2025-05-29 quant-ph cs.CC

Giulio Malavolta , Tamer Mour This is my paper
classification quant-phcs.CC MSC 81P6868Q1294A60 PACS 03.67.-a03.67.Lx
keywords proofofquantumnessboundedstoragemodelclawgenerationinteractivehashingparitylearningmemorylowerboundquantumverificationunconditionalsoundness
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 proposes two proofs of quantumness (PoQ) in which a classical verifier checks that a quantum device performed a computation infeasible for any classical machine, with soundness that does not rely on computational assumptions. Instead, security holds unconditionally against any classical adversary whose persistent memory is bounded below a stated threshold, while the honest prover needs only a small quantum memory (n+2 qubits in the first protocol, polylog qubits in the second). The first protocol is a simple parity-based construction whose soundness follows from Raz's memory lower bound for learning parities, giving a quadratic gap between honest and adversarial memory. The second protocol, built from interactive hashing in the bounded-storage model, achieves an exponential gap and also yields claw generation with quantum soundness. If correct, these are the first PoQ protocols whose security is not conditional on computational conjectures, and they provide a path toward classically verifying quantum computation in the bounded-memory setting.

What carries the argument

The load-bearing mechanism is claw generation: an interactive protocol at the end of which the honest prover holds a superposition (|x0> + |x1>)/sqrt(2) of two values that the verifier knows but any memory-bounded adversary cannot recover both of. For Protocol 1, the claw-free function is the linear map x -> Ax with A = (V, Vs); the verifier streams rows of A one at a time and uses a random linear combination of rows to compute inner products without storing the whole matrix, while soundness reduces to Raz's memory lower bound for parity learning. For Protocol 2, the claw is produced through coherent interactive hashing over a streamed random bitstring, combined with a stitching operation that turns many "1-bit claws" into a single hard claw; soundness follows from the interactive-hashing security and an incompressibility argument against memory-bounded adversaries.

What would settle it

To refute Protocol 1's soundness, exhibit a classical algorithm that uses just over $n^{2}$/20 bits of memory and finds s from the parity samples with probability significantly better than O($2^{{-alpha n}}$), or find a constant-factor violation of Raz's lower bound. For Protocol 2, a classical or quantum adversary that stores more than m bits and can still output both claw values with non-negligible probability would falsify the claimed claw-finding hardness; concretely, one could attempt to compress the streamed random bits so that the two indices and their values are recoverable from m-bit storage.

Watch

Extended reading notes

Core claim

The central claim is that a classical verifier can reliably distinguish a quantum prover from any classical prover, provided the classical prover's memory is strictly bounded, with no other restriction on its runtime. For Protocol 1, an honest quantum prover using n+2 qubits makes the verifier accept with probability $cos^{2}$(pi/8), while any classical attacker using fewer than $n^{2}$/20 memory bits succeeds with probability at most 3/4 + O($2^{{-n}}$); thus there is a constant completeness-soundness gap. Protocol 2 amplifies the gap to exponential (soundness 3/4 + 2^{-$\Omega$($\lambda$)}) while the honest parties use only polylog memory, assuming the attacker stores less than m bits. The paper also proves quantum soundness for the claw-generation protocol underlying Protocol 2, showing that a quantum attacker with bounded memory cannot output both preimages of the generated claw, and sketches how this yields classical verification of BQP computations that is unconditionally secure in the bounded-storage model.

Load-bearing premise

The security statements collapse if the adversary can store information outside the declared memory cap, or if the memory cap is even slightly larger than $n^{2}$/20 in Protocol 1; the proofs assume the adversary's persistent state is strictly bounded and that Raz's parity-learning lower bound holds as stated.

Editorial extensions

If this is right

  • If the protocols are sound as claimed, they supply PoQ schemes whose security does not depend on unproven computational conjectures, only on a memory bound for the adversary.
  • The first protocol can be implemented with one-qubit Hadamard and CNOT gates plus a single non-Clifford gate, making it potentially feasible on near-term small quantum devices.
  • The second protocol demonstrates that the gap between honest and adversarial memory can be made exponential, with honest parties using only polylogarithmic memory.
  • Quantum soundness of the claw-generation protocol offers a route to classically verifying arbitrary BQP computations in the bounded-storage model, without computational assumptions.
  • The completeness and soundness gaps are constant (or tunable via repetition), so the protocols can be repeated to amplify confidence while preserving the memory-based security guarantee.

Reading between the lines

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

  • The security guarantee is conditional on the adversary's memory being genuinely capped, including the inability to offload information to external storage outside the model; a device that can write to a large classical disk would break the soundness threshold.
  • Protocol 1's reliance on Raz's bound suggests that memory-hardness, not just time complexity, can be a practical resource for quantum advantage; a natural testable extension is to benchmark quantum devices against classical solvers with tightly capped memory in the parity-learning task.
  • The protocols could inspire a new class of verifiable quantum experiments where the verifier does not need to trust any computational hardness assumption, analogous to how the bounded-storage model was used for unconditionally secure cryptography.
  • The exponential-gap protocol indicates that even a tiny honest memory (polylog qubits) can certify quantumness against adversaries with much larger but still bounded memory, which may be relevant for device certification with minimal hardware requirements.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. This paper proposes two proofs of quantumness (PoQ) in the bounded-storage model, where soundness is claimed unconditionally against adversaries whose memory is bounded but whose runtime is unrestricted. Protocol 1 (Section 3) is a CHSH-type protocol built on the linear function x↦Ax with A=(V,Vs); the verifier streams the rows of A one at a time and the prover coherently evaluates them. The paper claims completeness cos^2(π/8) and soundness 3/4+ε against any classical prover with less than n^2/20 bits of memory, based on Lemma 5, attributed to Raz. Protocol 2 (Section 4) uses interactive hashing and a stitching amplification to achieve an exponential gap, with classical soundness against m-bit-memory provers and quantum soundness against m-qubit provers; an appendix sketches how the quantum soundness leads to classical verification of BQP. The paper is clearly written and the high-level template is appealing, but the soundness proof of Protocol 1 rests on a misreading of the cited memory lower bound.

Significance. If the results are established, this would be a notable conceptual advance: PoQ protocols whose soundness does not rely on computational conjectures, only on a memory bound on the prover, with a very simple honest prover for Protocol 1 and an exponential gap for Protocol 2. The coherent implementation of interactive hashing and the stitching argument are elegant, and the quantum-soundness lemma (Lemma 29) together with the BQP-verification appendix indicate a promising route to classical verification of quantum computations in the bounded-storage model. The main caveat is the unsupported time-free parity-learning lower bound; this is fixable in principle but is currently load-bearing for the paper's central claim.

major comments (2)
  1. [Section 3, Lemma 5 and Theorem 15] Lemma 5 is attributed to [Raz18] as a time-free memory lower bound for parity learning, but the published result is a time-space tradeoff: for memory S < n^2/20, the required time is 2^{Ω(n)}, and the theorem does not bound the success probability of an adversary with small memory when runtime is unrestricted. Since Section 2.1 explicitly allows the adversary's runtime to be unbounded, and the reduction in Lemma 17 constructs a parity learner whose runtime is inherited from P* and may therefore be unbounded, the soundness of Protocol 1 (Theorem 15) is not established by the cited theorem. The authors should either prove a genuine one-pass streaming memory lower bound for parity learning with the claimed constant, cite a correct source for such a bound, or change the adversary model to include a runtime restriction (which would weaken the advertised 'unconditional' claim). As written, this is a load-bearing gap.
  2. [Section 4.4, Claim 27] The set B^j_ω is defined in terms of W_post, which includes the interactive-hashing transcript and therefore depends on the indices v^j_0, v^j_1 that are outputs of that transcript, whereas Definition 21's (α,β)-security is stated for a fixed set B chosen before the protocol. The proof invokes Theorem 22 on this data-dependent set with the sentence 'Thus, by Theorem 22', but the applicability is not immediate. The authors should either explicitly prove that the interactive-hashing transcript is conditionally independent of U^j given W_pre^j, so that conditioning on W_post does not alter the relevant entropies, or provide a direct argument for adaptive sets. This step is needed for the classical soundness of Protocol 2 and deserves a complete justification.
minor comments (5)
  1. [Section 4.3, complexity calculation] The text says an attempt of the 1-bit claw generation succeeds with probability 1/k^2, but for a uniformly random 2-to-1 hash the probability that a fixed distinct pair {v_0,v_1} is the preimage pair is 1/(k-1), not 1/k^2. The stated O(λk^3) runtime is therefore conservative, but the calculation should be corrected.
  2. [Lemma 24, correctness statement] Lemma 24 states that the residual state is the claw state 'with probability 1', but the protocol may abort in Step 1.3 and restart; the statement should condition on the protocol not aborting.
  3. [Throughout] There are several typos and inconsistencies, including 'paramter' in Protocol 1, 'execution execution' in Theorem 2, 'apriori' in Section 1.2, and the abstract's 'Raz's memory lower bound for matrix inversion' versus the 'learning parities' terminology used in Section 3.
  4. [Section 2.1] The definition of memory-bounded algorithms should state explicitly whether the memory bound counts the transcript/input and how it applies to quantum registers; this matters for comparing the honest prover's n+2 qubits with an adversary's m qubits or bits.
  5. [Appendix A] The BQP-verification appendix is a proof sketch; the paper should clearly mark which reductions are fully formal and which require additional work, particularly the memory-preservation claims and the transition from inverse-polynomial to negligible claw-finding soundness.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the central soundness reductions are external (Raz, Goldreich-Levin, DHRS04, DQW23, BBK22); the only self-citation ([BKM+24]) is background in the BQP-verification appendix and is not load-bearing.

full rationale

Protocol 1's completeness is the standard CHSH calculation: cos^2(pi/8) is fixed by measuring the post-claw qubit in the +/-pi/8 bases, not fitted from the prover's acceptance data. Soundness (Lemma 17) reduces any 3/4+epsilon winning prover to a parity predictor via Goldreich-Levin, and the hard step is exactly Lemma 5, quoted from Raz. That is an external imported bound, not an input redefined as a prediction. Protocol 2 similarly inherits its PoQ outline from [BGK+23] and its interactive hashing from [DHRS04]; the classical and quantum claw-finding analyses use [DQW23] and [BBK22] as external lemmas. The paper's self-citation [BKM+24] (Malavolta is a coauthor) appears only in the appendix line 'It is shown in [NZ23, BK24, BKM+24]' and the subsequent reduction is explicitly attributed to [BK24] and described as a proof sketch; the core Theorems 1-3 do not load on it. The main caveat is not circularity: Lemma 5 is stated as a time-free space bound, whereas Raz's published result is a time-space tradeoff; if the time-free reading is unsupported, Theorem 1's soundness is not established, but that is an accuracy/support problem about an external theorem, not a self-referential reduction. The appendix also flags that it is a proof sketch (Section A.1) and that Lemma 29 needs amplification (Section A.2), so the paper itself discloses the incomplete parts.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claims rest on cited theorems from prior work (Raz's parity memory lower bound, Goldreich-Levin, interactive hashing security, and the BBK22 plug-in lemma) plus the domain assumption of a memory-bounded adversary. No ad hoc axioms are introduced; the paper's own new lemmas (coherent interactive hashing, stitching) are proved in the text.

free parameters (3)
  • m (Protocol 1) = 2n
    Number of rows of A; chosen as 2n so that A is 2-to-1 with overwhelming probability (Prop. 4). This is a design choice, not a fitted constant, but it sets the protocol's parameters.
  • k (Protocol 2 stream length) = Theta(lambda (m+Omega(lambda)) log k)
    Chosen to satisfy k/log k > lambda(m+Omega(lambda)) in Lemma 24, balancing the bad-event probability and the interactive-hashing soundness; determines the memory gap and the honest runtime.
  • t (bad-event slack) = k/(lambda log k) - m
    Defined in Lemma 25 as the entropy deficit that triggers a bad event; used in Claims 26 and 27.
assumptions (5)
  • standard math Raz's memory lower bound for parity learning (Lemma 5)
    Imported from [Raz18]; the core hardness assumption in Protocol 1's soundness proof, used in Lemma 17 to conclude any successful classical prover can learn the secret s.
  • standard math Goldreich-Levin hard-core predicate extractor (Lemma 6)
    Used in Lemmas 17 and 20 to convert a predictor for r^T t or (r0||r1)^T(x0||x1) into an algorithm outputting the secret, with O(n log n) memory overhead.
  • standard math Stateless interactive hashing (Theorem 22)
    Imported from [DHRS04]; provides the (alpha,beta)-security used in Claims 27 and 30 for Protocol 2's claw generation.
  • standard math BBK22 Plug-In Lemma (Lemma 14)
    Imported from [BBK22]; used in Lemma 29 to bound quantum memory-bounded adversaries' information about the stream.
  • domain assumption Memory-bounded adversary model
    The protocols' soundness is defined and proven only against adversaries whose persistent storage is bounded at every round; this is the physical assumption that replaces computational hardness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How to Verify that a Small Device is Quantum, Unconditionally." pith.science (2026). https://pith.science/paper/ZAIP7RQ7

@misc{pith2026250523978,
  author       = {Pith},
  title        = {Pith review of: How to Verify that a Small Device is Quantum, Unconditionally},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZAIP7RQ7}},
  note         = {Machine review of arXiv:2505.23978}
}
read the original abstract

A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this work, we propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover, but otherwise no restrictions on its runtime. In this model, we propose two protocols: 1. A simple protocol with a quadratic gap between the memory required by the honest parties and the memory bound of the adversary. The soundness of this protocol relies on Raz's (classical) memory lower bound for matrix inversion (Raz, FOCS 2016). 2. A protocol that achieves an exponential gap, building on techniques from the literature on the bounded storage model (Dodis et al., Eurocrypt 2023). Both protocols are also efficiently verifiable. Despite having worse asymptotics, our first protocol is conceptually simple and relies only on arithmetic modulo 2, which can be implemented with one-qubit Hadamard and CNOT gates, plus a single one-qubit non-Clifford gate.

Figures

Figures reproduced from arXiv: 2505.23978 by the authors.

Figure 1
Figure 1. The quantum circuit executed by the prover in a run of the protocol with [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 33 canonical work pages

  1. [1]

    Quantum supremacy using a programmable superconducting processor

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature , 574(7779):505--510, 2019

    2019

  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]

    Candidate trapdoor claw-free functions from group actions with applications to quantum protocols

    Navid Alamati, Giulio Malavolta, and Ahmadreza Rahimi. Candidate trapdoor claw-free functions from group actions with applications to quantum protocols. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022: 20th Theory of Cryptography Conference, Part I , volume 13747 of Lecture Notes in Computer Science , pages 266--293, Chicago, IL, USA, November 7...

    work page 2022

  4. [4]

    Barrington

    David A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in nc1. Journal of Computer and System Sciences , 38(1):150--164, 1989

    work page 1989

  5. [5]

    Constructive post-quantum reductions

    Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai. Constructive post-quantum reductions. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III , volume 13509 of Lecture Notes in Computer Scien...

    work page 2022

  6. [6]

    Vazirani, and Thomas Vidick

    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Mikkel Thorup, editor, 59th Annual Symposium on Foundations of Computer Science , pages 320--331, Paris, France, October 7--9, 2018. IEEE Computer Society Press

    2018

  7. [7]

    A cryptographic test of quantumness and certifiable randomness from a single quantum device

    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. J. ACM , 68(5), August 2021

    work page 2021

  8. [8]

    Kahanamoku - Meyer, Eitan Porat, and Thomas Vidick

    Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku - Meyer, Eitan Porat, and Thomas Vidick. Simple tests of quantumness also certify qubits. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings...

    work page 2023

Show all 39 references
  1. [9]

    On the power of oblivious state preparation

    James Bartusek and Dakshita Khurana. On the power of oblivious state preparation. CoRR , abs/2411.04234, 2024

    2024 arXiv

  2. [10]

    Compiled nonlocal games from any trapdoor claw-free function

    Kaniuar Bacho, Alexander Kulpe, Giulio Malavolta, Simon Schmidt, and Michael Walter. Compiled nonlocal games from any trapdoor claw-free function. Cryptology ePrint Archive, Paper 2024/1829, 2024

    2024

  3. [11]

    The rank of sparse random matrices over finite fields

    Johannes Bl\" o mer, Richard Karp, and Emo Welzl. The rank of sparse random matrices over finite fields. Random Struct. Algorithms , 10(4):407–419, July 1997

    1997

  4. [12]

    Cachin, C

    C. Cachin, C. Crepeau, and J. Marcil. Oblivious transfer with a memory-bounded receiver. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) , pages 493--502, 1998

    1998

  5. [13]

    Christian Cachin and Ueli M. Maurer. Unconditional security against memory-bounded adversaries. In Burton S. Kaliski Jr., editor, Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedin...

    1997

  6. [14]

    Constant-round oblivious transfer in the bounded storage model

    Yan Zong Ding, Danny Harnik, Alon Rosen, and Ronen Shaltiel. Constant-round oblivious transfer in the bounded storage model. In Moni Naor, editor, Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings ,...

    2004

  7. [15]

    Oblivious transfer in the bounded storage model

    Yan Zong Ding. Oblivious transfer in the bounded storage model. In Joe Kilian, editor, Advances in Cryptology --- CRYPTO 2001 , pages 155--170, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg

    2001

  8. [16]

    Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. CoRR , abs/cs/0602007, 2006

    2006 arXiv

  9. [17]

    Speak much, remember little: Cryptography in the bounded storage model, revisited

    Yevgeniy Dodis, Willy Quach, and Daniel Wichs. Speak much, remember little: Cryptography in the bounded storage model, revisited. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applica...

    2023

  10. [18]

    Goldreich and L

    O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , STOC '89, page 25–32, New York, NY, USA, 1989. Association for Computing Machinery

    1989

  11. [19]

    Simple schemes in the bounded storage model

    Jiaxin Guan and Mark Zhandry. Simple schemes in the bounded storage model. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology -- EUROCRYPT 2019, Part III , volume 11478 of Lecture Notes in Computer Science , pages 500--524, Darmstadt, Germany, May 19--23, 2019....

    2019

  12. [20]

    Classically verifiable quantum advantage from a computational bell test

    Gregory Kahanamoku - Meyer, Soonwon Choi, Umesh Vazirani, and Norman Yao. Classically verifiable quantum advantage from a computational bell test. Nature Physics , 18:1--7, 08 2022

    2022

  13. [21]

    Quantum advantage from any non-local game

    Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Barna Saha and Rocco A. Servedio, editors, 55th Annual ACM Symposium on Theory of Computing , pages 1617--1628, Orlando, FL, USA, June 20--23, 2023. ACM Press

    2023

  14. [22]

    Quantum advantage from any non-local game

    Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 1...

    2023

  15. [23]

    Classically verifiable quantum advantage from a computational bell test

    Gregory D Kahanamoku-Meyer, Soonwon Choi, Umesh V Vazirani, and Norman Y Yao. Classically verifiable quantum advantage from a computational bell test. Nature Physics , 18(8):918--924, 2022

    2022

  16. [24]

    quantum supremacy

    Yong Liu, Xin Liu, Fang Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, et al. Closing the" quantum supremacy" gap: achieving real-time simulation of a random quantum circuit using a new sunway supercomputer. In Proceedings of the ...

    2021

  17. [25]

    Experimental implementation of an efficient test of quantumness

    Laura Lewis, Daiwei Zhu, Alexandru Gheorghiu, Crystal Noel, Or Katz, Bahaa Harraz, Qingfeng Wang, Andrew Risinger, Lei Feng, Debopriyo Biswas, et al. Experimental implementation of an efficient test of quantumness. Physical Review A , 109(1):012610, 2024

    2024

  18. [26]

    Classical homomorphic encryption for quantum circuits

    Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 332--338, 2018

    2018

  19. [27]

    Classical verification of quantum computations

    Urmila Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 259--267. IEEE, 2018

    2018

  20. [28]

    Ueli M. Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher. J. Cryptol. , 5(1):53--66, 1992

    1992

  21. [29]

    Cryptographic characterization of quantum advantage

    Tomoyuki Morimae, Yuki Shirakawa, and Takashi Yamakawa. Cryptographic characterization of quantum advantage. Cryptology ePrint Archive, Paper 2024/1536, 2024

    2024

  22. [30]

    Proofs of quantumness from trapdoor permutations

    Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA , volume 251 of LIPIcs , pages...

    2023

  23. [31]

    Perfect zero-knowledge arguments for NP can be based on general complexity assumptions (extended abstract)

    Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung. Perfect zero-knowledge arguments for NP can be based on general complexity assumptions (extended abstract). In Ernest F. Brickell, editor, Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptol...

    1992

  24. [32]

    Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification

    Anand Natarajan and Tina Zhang. Bounding the quantum value of compiled nonlocal games: From CHSH to BQP verification. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 1342--1348. IEEE , 2023

    2023

  25. [33]

    Randomized distributed edge coloring via an extension of the chernoff--hoeffding bounds

    Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the chernoff--hoeffding bounds. SIAM Journal on Computing , 26(2):350--368, 1997

    1997

  26. [34]

    Fast learning requires good memory: A time-space lower bound for parity learning

    Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. J. ACM , 66(1), December 2018

    2018

  27. [35]

    Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124--134, Santa Fe, NM, USA, November 20--22, 1994. IEEE Computer Society Press

    1994

  28. [36]

    Bounds for entropy and divergence for distributions over a two-element set

    Flemming Topsøe. Bounds for entropy and divergence for distributions over a two-element set. JIPAM. Journal of Inequalities in Pure & Applied Mathematics [electronic only] , 2(2):Paper No. 25, 13 p.--Paper No. 25, 13 p., 2001

    2001

  29. [37]

    Salil P. Vadhan. Constructing locally computable extractors and cryptosystems in the bounded-storage model. Journal of Cryptology , 17(1):43--77, January 2004

    2004

  30. [38]

    , " * write output.state after.block = add.period write

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...

  31. [39]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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