Protecting Quantum Computers against Untrusted Users

Alexander Schuckert; Joel Rajakumar; Michael J. Gullans; Shiv Akshar Yadavalli

REVIEW

Protecting Quantum Computers against Untrusted Users

Shiv Akshar Yadavalli, Joel Rajakumar, Alexander Schuckert, Michael J. Gullans

Quantum Physics · Submitted 5 Oct 2026 · 55 references

Pith's verdict: A genuinely new restricted model with honest conditional security; the attack-dichotomy gap is real but openly flagged, and the Theorem 8 proof bug is fixable.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2610.06812 (version 1)

Pith IDP3E24BUA, Pith's permanent record of this paper and its review

CitationAlexander Schuckert, Joel Rajakumar, Michael J. Gullans, Shiv Akshar Yadavalli. "Protecting Quantum Computers against Untrusted Users." arXiv:2610.06812 (2026). https://pith.science/paper/P3E24BUA

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper defines a new restricted model, 1/2BQP1: the server supplies a random computational-basis input, reveals it only after execution, and reads out one designated bit. The central claim is Conjecture 1, that no polynomial-time adaptive classical client can factor RSA moduli through this interface. The model genuinely sits between DQC1 and 1/2BQP, and the technical core is real work. Theorem 10 shows one-bit readout makes every single-call circuit A = N O_pi V classically simulable, via character-observable expansions and Van den Nest's sparse-operator results. Theorem 11 shows rational reconstruction in NC1 yields a complete factoring attack in BPP^Samp^DQC1, using borrowed-workspace Barrington programs and the Shor-Jordan reduction. Theorem 12 shows a DQC1/1/2BQP1 separation would imply P != NC1. The appendices are detailed and the proofs I checked hold up.

The paper is unusually honest about its limits. Security is explicitly conditional, and the authors state plainly that a security theorem would resolve a major open problem in circuit complexity [b86, b185]. The reader's two concerns both land, with different weights. The proof of Theorem 8 uses y xor x1 to simulate a DQC1 request; that step is invalid for general U, since the first-qubit output on |1 x_rest> is not the complement of the output on |0 x_rest>. The containment is still true by rejection sampling - keep replies with x1 = 0 and double the request count - so this is a fixable proof bug, not a threat to the result.

The bigger gap is the unproven attack dichotomy. Theorem 10 kills single-call normalizer-postprocessed circuits; Theorem 11 blocks only rational-reconstruction decoders in NC1. A multi-call attack with a lattice-reduction decoder of the Regev type falls between the two pillars, and no theorem rules it out. The paper names lattice reduction as a similar unknown and says a successful attack "will likely need to leave the single-call framework," so the authors are not hiding this. But the consequence is that Conjecture 1 is a well-motivated research program, not an established barrier; a deployment relying on this interface for harvest-now-decrypt-later mitigation would be betting on a heuristic.

Who gets value: complexity theorists interested in intermediate models, and the quantum-access-security crowd. The model is new, the proofs are mostly solid, and the honest limitations make the paper more useful, not less. I would send it to referees, expecting revisions that fix the Theorem 8 proof and sharpen the attack-dichotomy discussion.

What would settle it

Find a polynomial-size, logarithmic-depth Boolean circuit family for rational reconstruction, the function $\mathrm{RR}(N,t)$ returning the denominator of the unique fraction $c/d$ with $0 \le c < d < N$ and $|t - c/d| < 1/(2N^2)$; by Theorem 11 this immediately yields a factoring protocol in $BPP^{\mathrm{Samp}\,\mathrm{DQC1}} \subseteq BPP^{\mathrm{Samp}\ \frac{1}{2}\mathrm{BQP}_1}$, refuting Conjecture 1. Equivalently, by Barrington's theorem, exhibit a bounded-width reversible program that computes that denominator from read-only input bits. A separate, direct falsifier is any explicit factoring protocol through the $\frac{1}{2}$BQP$_1$ interface with polynomially many adaptive requests that lies outside the single-call family and does not put rational reconstruction in $\mathrm{NC}^1$.

Referee report

Significance

If the two supporting theorems are correct, the paper contributes a genuinely new and cleanly defined restricted model, 1/2BQP1, sits between DQC1 and 1/2BQP, and gives a rigorous explanation of why one-bit readout neutralizes the full-Fourier-sample advantage of standard factoring circuits. The proof of Theorem 10 (Appendix A) is detailed, uses standard tools (Van den Nest's computationally tractable states, a character expansion of the measured-bit observable, and a careful sampling argument for the exponentially many Fourier terms), and appears sound. Theorem 11 (Appendix C) is a substantial constructive argument (eigenphase threshold tests, NC^1-with-borrowed-workspace evaluation via Barrington programs, Shor–Jordan reduction to DQC1) that is worked out in impressive detail and is honestly conditional on RR ∈ NC^1. Theorem 12's guess-and-check DQC1 simulation is elegant. The paper is unusually candid about what is and is not established: it states plainly that no security theorem is expected without assumptions on attacker algorithms (Sec. VII), that the finite-size estimates are heuristic (Sec.

Major objections (2)

[Sec. III B, proof of Theorem 8 (Eq. (2))] The proof of the containment BPP^{SampDQC1} ⊆ BPP^{Samp 1/2BQP1} as written is invalid. The claim that 'ignoring x_1 should result in the maximally mixed state' does not imply that the output bit for runs with x_1 = 1 is the bitwise complement of the output for x_1 = 0; complementarity of the two conditional distributions holds only for special U. A concrete counterexample: take U to be a reversible circuit that computes AND into the first qubit, so the measured bit is y = x_1 ∧ x_2. Then for x_1 = 0 the output is deterministically 0, while for x_1 = 1 the output equals x_2 and is fair; the y ⊕ x_1 transformation yields a 3/4, 1/4 distribution instead of the DQC1 output (deterministic 0). The containment statement itself is nevertheless true, by a much simpler argument: after conditioning on the revealed x_1 = 0, the input is precisely |0⟩ ⊗ |x_2...x_n⟩ with uniform tails, which is exactly the DQC1 input, and the client can post-select on x_1 = 0 at polynomial cost. Since 'the containment ... is Theorem 8' is invoked in the closing line of the proof of Theorem 11 (Appendix C) and in Section IV B, the written proof needs to be replaced by this post-selection argument.
[Sec. II A (Conjecture 1), Sec. IV A–B] The evidence for Conjecture 1 does not partition the space of adaptive attacks, and this shapes the strength of the central claim. Theorem 10 bounds only circuits of the single-call form A = N O_π V with normalizer postprocessing, and Theorem 11 blocks only attacks built on logarithmic-depth rational reconstruction. A multi-call circuit with non-normalizer postprocessing (e.g., N_1 O_π N_2 O_π N_3), or a coherent decoder based on lattice reduction rather than continued fractions, falls between the two pillars; as the paper itself notes in Section IV B, Regev-type decoders use lattice reduction, and RR ∉ NC^1 carries no implication for shallow lattice reduction. The authors acknowledge in Section VII that no security theorem is expected 'without assumptions on the algorithms an attacker may use' and in Section IV A that a successful attack 'will likely need to leave the single-call framework,' so I am not reading this as a misstated theorem. My request is to make the underlying dichotomy an explicit assumption: state that the evidence treats attacks as either single-call normalizer-postprocessed circuits or coherent rational-reconstruction decoders, and either name that dichotomy as a working hypothesis supporting Conjecture 1 or narrow the conjecture's statement accordingly. As written, Sections IV A and IV B argue by plausibility that these are the only serious attack families, but the argument is not a classification and should not read like one. The authors acknowledge this: “We therefore do not expect a security theorem for 1 2 BQP1 without assumptions on the algorithms an attacker may use.”

Minor objections (4)

[Sec. VII] Typo: 'we do not expect an security theorem' should read 'a security theorem'; the same construction appears in Section II B ('a proof of the conjecture would separate P from NC 1').
[Sec. VI and Fig. 2] The finite-size estimates (10n–12n logical qubits for the coherent continued-fraction decoder, the 'yellow region' of Fig. 2) are explicitly heuristic and the paper says so; I would suggest labeling Fig. 2's boundaries as schematic, order-of-magnitude estimates rather than firm thresholds, since Section VI notes that optimizing the clean-qubit usage of continued fractions is 'not a previously studied problem.'
[Appendix A, Lemma 13] The Hoeffding-based sample bound of O(Λ^2 ε^{-2} log(1/ζ)) is stated without derivation of the constant; a one-line justification that each summand is bounded by Λ and the estimator is unbiased would help readers. This is presentation only; the lemma's logic is sound.
[Sec. V B] The sentence 'A separation would still require showing that estimating the weighted average over uniformly random x is hard for DQC1; the worst-case hardness of evaluating f alone does not establish this' correctly states the limitation, which the paper acknowledges. I would add a citation for the DQC1-hardness of correlation estimation that is cited elsewhere (Ref. [23]) in this paragraph, since the discussion of weighted traces would benefit from it.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper conjectures that a quantum server restricted to random inputs and a single output bit cannot help classical clients factor RSA moduli, and it proves that one-bit readout makes the quantum stages of all standard factoring…

The reading

A publicly accessible fault-tolerant quantum computer could run Shor's algorithm and break RSA, but the same hardware is wanted for simulation and discovery. This paper proposes a purely input–output interface that tries to remove the factoring capability without inspecting users' circuits: the server draws a uniformly random computational-basis input, applies whatever unitary the client specifies, measures one designated qubit, and reveals the input only after execution. The central conjecture is that a classical client making polynomially many adaptive requests through this $\frac{1}{2}$BQP$_1$ interface cannot efficiently factor RSA moduli, even though the model contains the one-clean-qubit model DQC1 and inherits its simulation applications such as infinite-temperature correlations and out-of-time-order correlators. The supporting results are Theorem 10, showing that one-bit readout makes the quantum stage of every standard factoring algorithm — Shor, Ekerå–Håstad, Kitaev, Regev — classically simulable, and Theorem 11, showing that the only known escape, a coherent logarithmic-depth rational-reconstruction decoder, would require placing a decades-open circuit problem in $\mathrm{NC}^1$. If the conjecture holds, public quantum access could be granted without granting cryptanalytic power, at the price of excluding computations that need polynomially many initialized qubits.

What carries the argument

The load-bearing object is the single-call circuit family $A = N O_\pi V$: a tractable preparation $V$ (uniform, Gaussian, or made of tiny explicit blocks), one call to an arithmetic-oracle permutation $O_\pi$ like modular exponentiation, and a normalizer circuit $N$, the generalization of Clifford circuits to product cyclic groups that contains every cyclic Fourier transform. Theorem 10 works by expanding the measured bit's observable into Fourier characters, $Z_1 = \sum_{\ell \text{ odd}} c_\ell D_{\chi_\ell}$ with coefficients $|c_\ell| \le 1/\min(\ell, M-\ell)$, and showing that each conjugated character $N^\dagger D_{\chi_\ell} N$ is an efficiently computable monomial unitary whose expectation on the tractable state $\phi_s = O_\pi V|s\rangle$ is classically estimable; sampling the character indices in dyadic bands keeps the summed weights polynomially bounded, so the entire one-bit distribution is classically sampleable. The second mechanism is the decoder attack: a Boolean continued-fraction decoder appended after the Fourier register makes the coefficient weight exponential and breaks the simulation, so the paper proves (Theorem 11) that a logarithmic-depth coherent rational-reconstruction decoder — evaluated on borrowed workspace via Barrington's theorem — would complete a factoring protocol in DQC1, tying security to the hard open problem of whether $\mathrm{RR}$ lies in $\mathrm{NC}^1$.

Extended reading notes

Core claim

The discovery, stated as Conjecture 1, is that FACTORING does not lie in $BPP^{\mathrm{Samp}\ \frac{1}{2}\mathrm{BQP}_1}$, where the superscript records polynomially many adaptive requests to the interface with randomized polynomial-time classical post-processing, and FACTORING asks for one specified bit of the smaller prime factor of an $n$-bit semiprime. As evidence, the paper proves two structural facts. Theorem 10 shows that for any single-call circuit $A = N O_\pi V$ — a computationally tractable preparation $V$, one call to an arithmetic permutation oracle $O_\pi$ such as modular exponentiation, and a normalizer postprocessor $N$ such as a Fourier transform — the first-qubit outcome on every basis input, and the complete transcript of $T$ adaptive requests, is classically sampleable to total variation error $\delta$ in polynomial time. Theorem 11 shows that the natural counterattack is closed off: if rational reconstruction were in $\mathrm{NC}^1$, then FACTORING would already be in $BPP^{\mathrm{Samp}\,\mathrm{DQC1}} \subseteq BPP^{\mathrm{Samp}\ \frac{1}{2}\mathrm{BQP}_1}$, and since rational reconstruction lies in P, a proof of the conjecture would separate P from $\mathrm{NC}^1$. The same two theorems frame a finite-size security regime and a candidate application that distinguishes $\frac{1}{2}$BQP$_1$ from DQC1 through weighted infinite-temperature traces.

Load-bearing premise

The security case assumes every successful factoring attempt through the $\frac{1}{2}$BQP$_1$ interface falls into one of two analyzed families — a single-oracle-call circuit of the form $A = N O_\pi V$, whose one-bit readout is proven classically simulable, or an attack requiring a logarithmic-depth coherent rational-reconstruction decoder, which is blocked only by the unproven belief that $\mathrm{RR} \notin \mathrm{NC}^1$ — and the paper does not prove that arbitrary adaptive multi-call protocols reduce to that dichotomy.

Editorial extensions

If this is right

A server could offer one-bit readout to every user without inspecting circuits, and the quantum stages of Shor, Ekerå–Håstad, Kitaev, and Regev factoring would provably be classically simulable under it, removing all known factoring routes at every system size.
All DQC1 simulation applications carry over — infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions — so the interface keeps genuine scientific utility.
No unconditional security proof should be expected: proving the conjecture would separate P from $\mathrm{NC}^1$, because rational reconstruction lies in P.
In the finite-size regime, a machine with roughly $10^4$ logical qubits and one-bit readout may be as secure against known factoring attacks as a machine with $10^3$ qubits returning full samples, because a coherent continued-fraction decoder needs about $10n$–$12n$ logical qubits.
Separating $\frac{1}{2}$BQP$_1$ from DQC1 hits the same P-versus-$\mathrm{NC}^1$ barrier, so any genuine separation must use weight functions outside $\mathrm{NC}^1$, such as the P-complete cellular-automaton prediction functions proposed in Section V B.

Reading between the lines

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

Editorial: the two analyzed attack families are not proven to exhaust the possibilities; a protocol using several oracle calls that is neither a single-call circuit nor a coherent rational-reconstruction decoder would escape both Theorem 10 and Theorem 11, so characterizing such multi-call protocols is the natural next target for the security case.
Editorial: progress on parallelizing the continued-fraction denominator is a concrete early-warning signal for the conjecture — any logarithmic-depth circuit family for rational reconstruction would, by Theorem 11, immediately yield a factoring protocol in DQC1 and refute the security claim.
Editorial: the finite-size argument suggests a measurable hardware benchmark: quantifying the actual logical-qubit gap between a modular-exponentiation stage and an optimized reversible Euclidean decoder would either validate or shrink the proposed no-randomization security regime.
Editorial: the weighted-trace spin-dynamics test is directly implementable, and scoring a classical model's predictions by $E[f(X)S_i]$ over random initial configurations gives an agreement rate whose hardness for DQC1, if established with P-complete weights, would be the first evidence that $\frac{1}{2}$BQP$_1$ exceeds the one-clean-qubit model.

Original abstract

Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-06: 1 request, 8,819 input tokens.

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.81 · human participants 0.02 · controlled comparison 0.13 · randomized assignment 0.04 · states quantitative result 0.23 · compares with prior results 0.91 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power. We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit. This interface permits arbitrary circuits and system sizes. We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli. The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions. We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics. We argue security in two steps. First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call. This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions. Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit. Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades. Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Publicly accessible fault-tolerant quantum computers must preserve scientific utility while limiting cryptanalytic power.	background 1.00	0.05	0.10	asserted 0.95
s1	We propose the restricted model of computation, 1/2BQP_1: a quantum server provides random computational-basis inputs, revealed only after execution, and one designated output bit.	contribution 0.80	0.83	0.11	asserted 0.96
s2	This interface permits arbitrary circuits and system sizes.	method 0.79	0.28	0.03	asserted 1.00
s3	We conjecture that a classical client making polynomially many adaptive requests cannot efficiently factor RSA moduli.	result 0.41	0.22	0.50	speculative 0.99
s4	The model subsumes the well-known one-clean-qubit model DQC1, retaining its applications to infinite-temperature multi-time correlations, out-of-time-order correlators, and suitably normalized partition functions.	contribution 0.44	0.20	0.04	asserted 1.00
s5	We propose a candidate for separating 1/2BQP_1 from DQC1 based on testing classical predictions of quantum spin dynamics.	contribution 0.88	0.72	0.06	hedged possibility 0.59
s6	We argue security in two steps.	method 0.81	0.59	0.04	asserted 0.78
s7	First, we show that one-bit readout makes the quantum stages of standard factoring algorithms classically simulable, even when their preparation and postprocessing are redesigned within a broad family around a single arithmetic-oracle call.	result 0.73	0.89	0.16	asserted 1.00
s8	This covers the quantum stages of Shor, Ekera-Hastad, Kitaev, and Regev factoring constructions.	result 0.72	0.46	0.06	asserted 0.99
s9	Second, we examine the workaround of coherently implementing rational reconstruction to release a factor bit.	contribution 0.51	0.46	0.05	asserted 0.60
s10	Random inputs obstruct this straightforward attack: known techniques accommodate logarithmic-depth classical circuits, but rational reconstruction has resisted such parallelization for decades.	interpretation 0.38	0.15	0.07	asserted 0.94
s11	Therefore, we show that security of our protocol is built on not only classical hardness for factoring, but also conjectured circuit lowerbounds for rational reconstruction.	interpretation 0.88	0.80	0.63	asserted 0.98

What kind of paper the classifier reports this is: theoretical result 0.78 · evidence from argument 0.87.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 2.** FIG. 2. Schematic progression of our proposed interfaces for public quantum access as hardware scales, for a fixed modulus size. Each stage

Figures reproduced from arXiv:2610.06812 by the authors.

References

Works cited (55)

[1]

J. Preskill, ACM Transactions on Quantum Computing6, 18:1 (2025), arXiv:2502.17368

View on Pith Pith review arXiv 2025
[2]

IBM, IBM sets the course to build world’s first large-scale, fault-tolerant quantum computer at new IBM quantum data center, IBM Newsroom (2025), june 10, 2025; technology roadmap announcement

View on Pith 2025
[3]

B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Chemical Reviews120, 12685 (2020), arXiv:2001.03685

View on Pith Pith review arXiv 2020
[4]

M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sciences114, 7555 (2017), arXiv:1605.03590

View on Pith Pith review arXiv 2017
[5]

R. Santagati, A. Aspuru-Guzik, R. Babbush, M. Degroote, L. Gonz ´alez, E. Kyoseva, N. Moll, M. Oppel, R. M. Parrish, N. C. Rubin, M. Streif, C. S. Tautermann, H. Weiss, N. Wiebe, and C. Utschig-Utschig, Nature Physics20, 549 (2024)

View on Pith 2024
[6]

P. W. Shor, SIAM Journal on Computing26, 1484 (1997), arXiv:quant-ph/9508027

View on Pith Pith review arXiv 1997
[7]

D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper,Transition to Post-Quantum Cryptography Standards, NIST Internal Report 8547 ipd (National Institute of Standards and Technology, 2024) initial Public Draft

View on Pith 2024
[8]

World Economic Forum,Global Cybersecurity Outlook 2025, Tech. Rep. (World Economic Forum, 2025) in collaboration with Accen- ture

View on Pith 2025
[9]

V . Sivak, A. Morvan, M. Broughton,et al., Nature655, 879 (2026)

View on Pith 2026
[10]

S. Dasu, M. DeCross, A. Y . Guo, A. Lavasani, J. Behrends, A. Benhemou, Y .-H. Chen, K. Mayer, C. N. Self, S. Simsek, B. Srivastava, M. S. Allman, J. Arkinstall, J. G. Bohnet, N. Q. Burdick, J. P. Campora, A. Chernoguzov, S. F. Cooper, R. D. Delaney, J. M. Dreiling, B. Estey, C. Figgatt, C. Foltz, J. P. Gaebler, A. Hall, C. A. Holliman, A. A. Husain, A. I...

View on Pith Pith review arXiv 2026
[11]

D. Bluvstein, A. A. Geim, S. H. Li, S. J. Evered, J. P. Bonilla Ataides, G. Baranes, A. Gu, T. Manovitz, M. Xu, M. Kalinowski, S. Majidy, C. Kokail, N. Maskara, E. C. Trapp, L. M. Stewart, S. Hollerith, H. Zhou, M. J. Gullans, S. F. Yelin, M. Greiner, V . Vuleti´c, M. Cain, and M. D. Lukin, Nature649, 39 (2026)

View on Pith 2026
[12]

C. Gidney and M. Eker ˚a, Quantum5, 433 (2021), arXiv:1905.09749

View on Pith Pith review arXiv 2021
[13]

C. Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (2025), arXiv:2505.15917 [quant-ph]

View on Pith Pith review arXiv 2025
[14]

H. Zhou, C. Duckering, C. Zhao, D. Bluvstein, M. Cain, A. Kubica, S.-T. Wang, and M. D. Lukin, inProceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA ’25)(ACM, 2025) pp. 1432–1448, arXiv:2505.15907

View on Pith arXiv 2025
[15]

M. Cain, Q. Xu, R. King, L. R. B. Picard, H. Levine, M. Endres, J. Preskill, H.-Y . Huang, and D. Bluvstein, Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits (2026), arXiv:2603.28627 [quant-ph]

View on Pith Pith review arXiv 2026
[16]

M. M.-Y . Huang and E.-C. Tang, Obfuscation of arbitrary quantum circuits (2026), arXiv:2601.08969 [quant-ph]

View on Pith Pith review arXiv 2026
[17]

E. Knill and R. Laflamme, Physical Review Letters81, 5672 (1998), arXiv:quant-ph/9802037

View on Pith Pith review arXiv 1998
[18]

D. Jacobs and S. Mehraban, The space just above one clean qubit (2024), arXiv:2410.08051 [quant-ph]

View on Pith Pith review arXiv 2024
[19]

S. Parker and M. B. Plenio, Physical Review Letters85, 3049 (2000), arXiv:quant-ph/0001066

View on Pith Pith review arXiv 2000
[20]

T. Heitmann, J. Richter, D. Schubert, and R. Steinigeweg, Zeitschrift f¨ur Naturforschung A75, 421 (2020)

View on Pith 2020
[21]

E. Rosenberg, T. I. Andersen, R. Samajdar,et al., Science384, 48 (2024)

View on Pith 2024
[22]

Y .-H. Shi, Z.-H. Sun, Y .-Y . Wang,et al., Nature Communications15, 7573 (2024)

View on Pith 2024
[23]

S. Roy Moulik and S. Strelchuk, DQC1-hardness of estimating correlation functions (2024), arXiv:2411.05208 [quant-ph]

View on Pith Pith review arXiv 2024
[24]

S. Aaronson, The equivalence of sampling and searching (2010), arXiv:1009.5104 [quant-ph]

View on Pith Pith review arXiv 2010
[25]

J. Bermejo-Vega and M. Van den Nest, Quantum Information and Computation14, 181 (2014), arXiv:1210.3637 [quant-ph]

View on Pith Pith review arXiv 2014
[26]

M. Van den Nest, Quantum Information and Computation11, 784 (2011), arXiv:0911.1624 [quant-ph]

View on Pith Pith review arXiv 2011
[27]

J. Bermejo-Vega, C. Y .-Y . Lin, and M. Van den Nest, The computational power of normalizer circuits over black-box groups (2014), arXiv:1409.4800 [quant-ph]

View on Pith Pith review arXiv 2014
[28]

D. Poulin, R. Blume-Kohout, R. Laflamme, and H. Ollivier, Physical Review Letters92, 177906 (2004), arXiv:quant-ph/0310038

View on Pith Pith review arXiv 2004
[29]

A. N. Chowdhury, R. D. Somma, and Y . Subas ¸ı, Physical Review A103, 032422 (2021), arXiv:1910.11842

View on Pith Pith review arXiv 2021
[30]

A. Scheie, N. E. Sherman, M. Dupont, S. E. Nagler, M. B. Stone, G. E. Granroth, J. E. Moore, and D. A. Tennant, Nature Physics17, 726 (2021)

View on Pith 2021
[31]

I. J. Lowe and R. E. Norberg, Physical Review107, 46 (1957)

View on Pith 1957
[32]

K. Seetharam, D. Biswas, C. Noel, A. Risinger, D. Zhu, O. Katz, S. Chattopadhyay, M. Cetina, C. Monroe, E. Demler, and D. Sels, Science Advances9, eadh2594 (2023)

View on Pith 2023
[33]

R. Kubo, Journal of the Physical Society of Japan12, 570 (1957)

View on Pith 1957
[34]

B. Bertini, F. Heidrich-Meisner, C. Karrasch, T. Prosen, R. Steinigeweg, and M.ˇZnidariˇc, Reviews of Modern Physics93, 025003 (2021)

View on Pith 2021
[35]

M. K. Joshi, F. Kranzl, A. Schuckert, I. Lovas, C. Maier, R. Blatt, M. Knap, and C. F. Roos, Science376, 720 (2022)

View on Pith 2022
[36]

I. ˇZuti´c, J. Fabian, and S. Das Sarma, Reviews of Modern Physics76, 323 (2004). 11

View on Pith 2004
[37]

T. Manovitz, S. H. Li, S. Ebadi, R. Samajdar, A. A. Geim, S. J. Evered, D. Bluvstein, H. Zhou, N. U. Koyluoglu, J. Feldmeier, P. E. Dolgirev, N. Maskara, M. Kalinowski, S. Sachdev, D. A. Huse, M. Greiner, V . Vuleti ´c, and M. D. Lukin, Nature638, 86 (2025), arXiv:2407.03249

View on Pith Pith review arXiv 2025
[38]

C. Moore, Journal of Statistical Physics88, 795 (1997), arXiv:cond-mat/9701118

View on Pith Pith review arXiv 1997
[39]

J. Proos and C. Zalka, Quantum Information and Computation3, 317 (2003), arXiv:quant-ph/0301141

View on Pith Pith review arXiv 2003
[40]

D. A. Barrington, Journal of Computer and System Sciences38, 150 (1989)

View on Pith 1989
[41]

S. Goldwasser, S. Micali, and C. Rackoff, SIAM Journal on Computing18, 186 (1989)

View on Pith 1989
[42]

O. Goldreich and E. Petrank, Computational Complexity8, 50 (1999)

View on Pith 1999
[43]

R. Canetti, inProceedings of the 42nd IEEE Symposium on Foundations of Computer Science(2001) pp. 136–145

View on Pith 2001
[44]

OECD,A quantum technologies policy primer, OECD Digital Economy Papers 371 (OECD Publishing, 2025)

View on Pith 2025
[45]

M. Eker ˚a and J. H˚astad, inPost-Quantum Cryptography, Lecture Notes in Computer Science, V ol. 10346 (Springer, 2017) pp. 347–363, arXiv:1702.00249

View on Pith Pith review arXiv 2017
[46]

A. Y . Kitaev, Quantum measurements and the Abelian stabilizer problem (1995), arXiv:quant-ph/9511026

View on Pith Pith review arXiv 1995
[47]

O. Regev, Journal of the ACM72, 10:1 (2025), arXiv:2308.06572 [quant-ph]

View on Pith Pith review arXiv 2025
[48]

S. Ragavan and V . Vaikuntanathan, inAdvances in Cryptology – CRYPTO 2024, Lecture Notes in Computer Science, V ol. 14925 (Springer, 2024) pp. 107–140, vERIFY volume/pages; consider renaming key to ragavan2024space, arXiv:2310.00899

View on Pith Pith review arXiv 2024
[49]

M. Eker ˚a and J. G ¨artner, inPost-Quantum Cryptography (PQCrypto 2024), Lecture Notes in Computer Science, V ol. 14771 (Springer,

View on Pith 2024
[50]

R. B. Griffiths and C.-S. Niu, Physical Review Letters76, 3228 (1996), arXiv:quant-ph/9511007

View on Pith Pith review arXiv 1996
[51]

F. Ablayev, C. Moore, and C. Pollett, Quantum and stochastic branching programs of bounded width (2004), version 2, arXiv:quant- ph/0201139

View on Pith 2004
[52]

C. Gidney, Factoring withn+ 2clean qubits andn−1dirty qubits (2017), arXiv:1706.07884 [quant-ph]

View on Pith Pith review arXiv 2017
[53]

R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Proceedings of the Royal Society of London A454, 339 (1998), arXiv:quant- ph/9708016

View on Pith 1998
[54]

P. W. Shor and S. P. Jordan, Quantum Information and Computation8, 681 (2008), arXiv:0707.2831 [quant-ph]. 12 Appendix Appendix A: Classical simulation of one-bit readout We prove Theorem 10 by expressing the measured bit’s expectation as an efficiently sampled average of classically estimable quantities. This avoids simulating the full output state ofA=N...

View on Pith Pith review arXiv 2008
[2024]

pp. 211–242, arXiv:2311.05545

View on Pith Pith review arXiv

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Reopening the one clean qubit case of a semi-grand challenge
quant-ph 2026-11 accept novelty 7.0 of 10

A fully separable one-clean-qubit circuit whose final unitary cannot be canonicalized shows that the published DQC1sep simulation proof has a false necessity claim, reopening Aaronson's question.
Secure Quantum Handshakes: Quantum Network Verification Via Simon's Algorithm
quant-ph 2026-10 conditional novelty 6.0 of 10

A quantum network verification protocol uses Simon's algorithm to distinguish genuine quantum devices from classical impersonators and low-fidelity quantum nodes.

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

J. Preskill, ACM Transactions on Quantum Computing6, 18:1 (2025), arXiv:2502.17368

View on Pith Pith review arXiv 2025

[2] [2]

IBM, IBM sets the course to build world’s first large-scale, fault-tolerant quantum computer at new IBM quantum data center, IBM Newsroom (2025), june 10, 2025; technology roadmap announcement

View on Pith 2025

[3] [3]

B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Chemical Reviews120, 12685 (2020), arXiv:2001.03685

View on Pith Pith review arXiv 2020

[4] [4]

M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Proceedings of the National Academy of Sciences114, 7555 (2017), arXiv:1605.03590

View on Pith Pith review arXiv 2017

[5] [5]

R. Santagati, A. Aspuru-Guzik, R. Babbush, M. Degroote, L. Gonz ´alez, E. Kyoseva, N. Moll, M. Oppel, R. M. Parrish, N. C. Rubin, M. Streif, C. S. Tautermann, H. Weiss, N. Wiebe, and C. Utschig-Utschig, Nature Physics20, 549 (2024)

View on Pith 2024

[6] [6]

P. W. Shor, SIAM Journal on Computing26, 1484 (1997), arXiv:quant-ph/9508027

View on Pith Pith review arXiv 1997

[7] [7]

D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper,Transition to Post-Quantum Cryptography Standards, NIST Internal Report 8547 ipd (National Institute of Standards and Technology, 2024) initial Public Draft

View on Pith 2024

[8] [8]

World Economic Forum,Global Cybersecurity Outlook 2025, Tech. Rep. (World Economic Forum, 2025) in collaboration with Accen- ture

View on Pith 2025

[9] [9]

V . Sivak, A. Morvan, M. Broughton,et al., Nature655, 879 (2026)

View on Pith 2026

[10] [10]

S. Dasu, M. DeCross, A. Y . Guo, A. Lavasani, J. Behrends, A. Benhemou, Y .-H. Chen, K. Mayer, C. N. Self, S. Simsek, B. Srivastava, M. S. Allman, J. Arkinstall, J. G. Bohnet, N. Q. Burdick, J. P. Campora, A. Chernoguzov, S. F. Cooper, R. D. Delaney, J. M. Dreiling, B. Estey, C. Figgatt, C. Foltz, J. P. Gaebler, A. Hall, C. A. Holliman, A. A. Husain, A. I...

View on Pith Pith review arXiv 2026

[11] [11]

D. Bluvstein, A. A. Geim, S. H. Li, S. J. Evered, J. P. Bonilla Ataides, G. Baranes, A. Gu, T. Manovitz, M. Xu, M. Kalinowski, S. Majidy, C. Kokail, N. Maskara, E. C. Trapp, L. M. Stewart, S. Hollerith, H. Zhou, M. J. Gullans, S. F. Yelin, M. Greiner, V . Vuleti´c, M. Cain, and M. D. Lukin, Nature649, 39 (2026)

View on Pith 2026

[12] [12]

C. Gidney and M. Eker ˚a, Quantum5, 433 (2021), arXiv:1905.09749

View on Pith Pith review arXiv 2021

[13] [13]

C. Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (2025), arXiv:2505.15917 [quant-ph]

View on Pith Pith review arXiv 2025

[14] [14]

H. Zhou, C. Duckering, C. Zhao, D. Bluvstein, M. Cain, A. Kubica, S.-T. Wang, and M. D. Lukin, inProceedings of the 52nd Annual International Symposium on Computer Architecture (ISCA ’25)(ACM, 2025) pp. 1432–1448, arXiv:2505.15907

View on Pith arXiv 2025

[15] [15]

M. Cain, Q. Xu, R. King, L. R. B. Picard, H. Levine, M. Endres, J. Preskill, H.-Y . Huang, and D. Bluvstein, Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits (2026), arXiv:2603.28627 [quant-ph]

View on Pith Pith review arXiv 2026

[16] [16]

M. M.-Y . Huang and E.-C. Tang, Obfuscation of arbitrary quantum circuits (2026), arXiv:2601.08969 [quant-ph]

View on Pith Pith review arXiv 2026

[17] [17]

E. Knill and R. Laflamme, Physical Review Letters81, 5672 (1998), arXiv:quant-ph/9802037

View on Pith Pith review arXiv 1998

[18] [18]

D. Jacobs and S. Mehraban, The space just above one clean qubit (2024), arXiv:2410.08051 [quant-ph]

View on Pith Pith review arXiv 2024

[19] [19]

S. Parker and M. B. Plenio, Physical Review Letters85, 3049 (2000), arXiv:quant-ph/0001066

View on Pith Pith review arXiv 2000

[20] [20]

T. Heitmann, J. Richter, D. Schubert, and R. Steinigeweg, Zeitschrift f¨ur Naturforschung A75, 421 (2020)

View on Pith 2020

[21] [21]

E. Rosenberg, T. I. Andersen, R. Samajdar,et al., Science384, 48 (2024)

View on Pith 2024

[22] [22]

Y .-H. Shi, Z.-H. Sun, Y .-Y . Wang,et al., Nature Communications15, 7573 (2024)

View on Pith 2024

[23] [23]

S. Roy Moulik and S. Strelchuk, DQC1-hardness of estimating correlation functions (2024), arXiv:2411.05208 [quant-ph]

View on Pith Pith review arXiv 2024

[24] [24]

S. Aaronson, The equivalence of sampling and searching (2010), arXiv:1009.5104 [quant-ph]

View on Pith Pith review arXiv 2010

[25] [25]

J. Bermejo-Vega and M. Van den Nest, Quantum Information and Computation14, 181 (2014), arXiv:1210.3637 [quant-ph]

View on Pith Pith review arXiv 2014

[26] [26]

M. Van den Nest, Quantum Information and Computation11, 784 (2011), arXiv:0911.1624 [quant-ph]

View on Pith Pith review arXiv 2011

[27] [27]

J. Bermejo-Vega, C. Y .-Y . Lin, and M. Van den Nest, The computational power of normalizer circuits over black-box groups (2014), arXiv:1409.4800 [quant-ph]

View on Pith Pith review arXiv 2014

[28] [28]

D. Poulin, R. Blume-Kohout, R. Laflamme, and H. Ollivier, Physical Review Letters92, 177906 (2004), arXiv:quant-ph/0310038

View on Pith Pith review arXiv 2004

[29] [29]

A. N. Chowdhury, R. D. Somma, and Y . Subas ¸ı, Physical Review A103, 032422 (2021), arXiv:1910.11842

View on Pith Pith review arXiv 2021

[30] [30]

A. Scheie, N. E. Sherman, M. Dupont, S. E. Nagler, M. B. Stone, G. E. Granroth, J. E. Moore, and D. A. Tennant, Nature Physics17, 726 (2021)

View on Pith 2021

[31] [31]

I. J. Lowe and R. E. Norberg, Physical Review107, 46 (1957)

View on Pith 1957

[32] [32]

K. Seetharam, D. Biswas, C. Noel, A. Risinger, D. Zhu, O. Katz, S. Chattopadhyay, M. Cetina, C. Monroe, E. Demler, and D. Sels, Science Advances9, eadh2594 (2023)

View on Pith 2023

[33] [33]

R. Kubo, Journal of the Physical Society of Japan12, 570 (1957)

View on Pith 1957

[34] [34]

B. Bertini, F. Heidrich-Meisner, C. Karrasch, T. Prosen, R. Steinigeweg, and M.ˇZnidariˇc, Reviews of Modern Physics93, 025003 (2021)

View on Pith 2021

[35] [35]

M. K. Joshi, F. Kranzl, A. Schuckert, I. Lovas, C. Maier, R. Blatt, M. Knap, and C. F. Roos, Science376, 720 (2022)

View on Pith 2022

[36] [36]

I. ˇZuti´c, J. Fabian, and S. Das Sarma, Reviews of Modern Physics76, 323 (2004). 11

View on Pith 2004

[37] [37]

T. Manovitz, S. H. Li, S. Ebadi, R. Samajdar, A. A. Geim, S. J. Evered, D. Bluvstein, H. Zhou, N. U. Koyluoglu, J. Feldmeier, P. E. Dolgirev, N. Maskara, M. Kalinowski, S. Sachdev, D. A. Huse, M. Greiner, V . Vuleti ´c, and M. D. Lukin, Nature638, 86 (2025), arXiv:2407.03249

View on Pith Pith review arXiv 2025

[38] [38]

C. Moore, Journal of Statistical Physics88, 795 (1997), arXiv:cond-mat/9701118

View on Pith Pith review arXiv 1997

[39] [39]

J. Proos and C. Zalka, Quantum Information and Computation3, 317 (2003), arXiv:quant-ph/0301141

View on Pith Pith review arXiv 2003

[40] [40]

D. A. Barrington, Journal of Computer and System Sciences38, 150 (1989)

View on Pith 1989

[41] [41]

S. Goldwasser, S. Micali, and C. Rackoff, SIAM Journal on Computing18, 186 (1989)

View on Pith 1989

[42] [42]

O. Goldreich and E. Petrank, Computational Complexity8, 50 (1999)

View on Pith 1999

[43] [43]

R. Canetti, inProceedings of the 42nd IEEE Symposium on Foundations of Computer Science(2001) pp. 136–145

View on Pith 2001

[44] [44]

OECD,A quantum technologies policy primer, OECD Digital Economy Papers 371 (OECD Publishing, 2025)

View on Pith 2025

[45] [45]

M. Eker ˚a and J. H˚astad, inPost-Quantum Cryptography, Lecture Notes in Computer Science, V ol. 10346 (Springer, 2017) pp. 347–363, arXiv:1702.00249

View on Pith Pith review arXiv 2017

[46] [46]

A. Y . Kitaev, Quantum measurements and the Abelian stabilizer problem (1995), arXiv:quant-ph/9511026

View on Pith Pith review arXiv 1995

[47] [47]

O. Regev, Journal of the ACM72, 10:1 (2025), arXiv:2308.06572 [quant-ph]

View on Pith Pith review arXiv 2025

[48] [48]

S. Ragavan and V . Vaikuntanathan, inAdvances in Cryptology – CRYPTO 2024, Lecture Notes in Computer Science, V ol. 14925 (Springer, 2024) pp. 107–140, vERIFY volume/pages; consider renaming key to ragavan2024space, arXiv:2310.00899

View on Pith Pith review arXiv 2024

[49] [49]

M. Eker ˚a and J. G ¨artner, inPost-Quantum Cryptography (PQCrypto 2024), Lecture Notes in Computer Science, V ol. 14771 (Springer,

View on Pith 2024

[50] [50]

R. B. Griffiths and C.-S. Niu, Physical Review Letters76, 3228 (1996), arXiv:quant-ph/9511007

View on Pith Pith review arXiv 1996

[51] [51]

F. Ablayev, C. Moore, and C. Pollett, Quantum and stochastic branching programs of bounded width (2004), version 2, arXiv:quant- ph/0201139

View on Pith 2004

[52] [52]

C. Gidney, Factoring withn+ 2clean qubits andn−1dirty qubits (2017), arXiv:1706.07884 [quant-ph]

View on Pith Pith review arXiv 2017

[53] [53]

R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Proceedings of the Royal Society of London A454, 339 (1998), arXiv:quant- ph/9708016

View on Pith 1998

[54] [54]

P. W. Shor and S. P. Jordan, Quantum Information and Computation8, 681 (2008), arXiv:0707.2831 [quant-ph]. 12 Appendix Appendix A: Classical simulation of one-bit readout We prove Theorem 10 by expressing the measured bit’s expectation as an efficiently sampled average of classically estimable quantities. This avoids simulating the full output state ofA=N...

View on Pith Pith review arXiv 2008

[55] [2024]

pp. 211–242, arXiv:2311.05545

View on Pith Pith review arXiv