Fast Cliffords When Your Quantum Memory Is Full

Ian Mertz; Marten Folkertsma; Sathyawageeswar Subramanian; Sergii Strelchuk

REVIEW

Fast Cliffords When Your Quantum Memory Is Full

Marten Folkertsma, Ian Mertz, Sergii Strelchuk, Sathyawageeswar Subramanian

Quantum Physics · Submitted 30 Sep 2026 · 13 references

Pith's verdict: The P-cycling cancellation is real and checkable; the one hinge is Lemma 9's two-sentence claim that Jiang's circuit restores the dirty register exactly.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 1, 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 ID2609.40144 (version 1)

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

CitationIan Mertz, Marten Folkertsma, Sathyawageeswar Subramanian, Sergii Strelchuk. "Fast Cliffords When Your Quantum Memory Is Full." arXiv:2609.40144 (2026). https://pith.science/paper/DOAO5YGU

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

This is a genuine result, not a repackaging. The central move — cycling the dirty register through three CNOT-conjugated copies with P^3=I and I+P+P^2=0 over F2, so the Bz contamination cancels — is explicit, and I verified the algebra in Lemma 10 on work basis states; it holds. Lemma 18's phase accumulation over the GF(2^t) cycle also checks out, including the divisibility condition 2^r | a·2^t separating the z=0 and z≠0 cases. Removing the clean output register via Urschel's six-factor decomposition is the right tool, and the extension to diagonal C_k elements through the CGK17 normal form plus Dickson's theorem is substantial, not a throwaway. The stated lower bounds match the upper bounds. The citation pattern is clean — AG04, CGK17, Jiang, Urschel, Barenco, Dickson are all real published results used as tools — and the paper is honest about scope: general circuits are left as a conjecture, the fan-out caveat is stated in Remark 4.1, and the global-phase convention is flagged.

The soft spot is exactly where the stress-test puts it, and I agree with its refinement: the singular-M extension in Lemma 9 is the lesser claim, since the blockwise proof via Jiang's Corollary 4.5 plausibly covers arbitrary blocks. The real hinge is exact restoration of the dirty register W. The published Jiang theorem only pins down that W returns to |0> for all x; it says nothing about z-dependence, so L'=I is not entailed by the citation alone. The paper's proof of Lemma 9 rests on two sentences — the (W,W) block is I_W because the circuit uncomputes by applying the inverse of what wrote into W, and the (I,W) block is 0 because I is used only as a control. That is the standard toggle/uncompute pattern, and if Jiang's depth-optimized schedule really does compute-then-exact-inverse, the claim follows. But it needs to be checked against Jiang et al. v3 directly, and a referee should ask the authors to make the work-register block structure explicit. I read this as a plausible reliance on a published construction, not an internal inconsistency; every other step I examined is self-consistent.

Who this is for: circuit synthesis, quantum catalysis, and shallow-circuit people. It deserves a serious referee — the construction is checkable and the claim is important if it holds. Send it out, with the specific request that the Lemma 9 restoration logic be spelled out against the Jiang construction.

Referee report

Significance

If the claims hold, the paper resolves a natural open question: the full Jiang et al. depth–workspace tradeoff for Clifford circuits can be achieved with no clean workspace at all, and the same catalytic mechanism extends to diagonal Clifford-hierarchy gates with provably matching lower bounds. The algebraic core is genuinely strong and I verified it sample-wise: Lemma 10's cancellation uses P^3 = I and I + P + P^2 = 0 over F_2 with M + M + M = M; Lemma 18's phase accumulation (Eq. (3)) is correct, including the divisibility condition 2^r | a·2^t for matching the z = 0 and z ≠ 0 cases; and Lemma 22's double-application trick (τ + L(u+x) + Lu = τ + Lx) correctly synthesizes affine work labels without a clean register. The constructions are explicit over finite gate sets, the proofs are constructive and largely self-checking, and the lower bounds are self-contained. The principal correctness risk is not the paper's own algebra but the faithfulness of its adaptation of Jiang et al.'s clean-ancilla circuit to a dirty work register, which is the hinge of Theorem 1.

Major objections (2)

[§4.2, Lemma 9] Lemma 9 is the hinge of Theorem 1, and its dirty-register block structure is not established. The paper itself notes that 'Jiang et al. do not specify the blocks acting on W, since their workspace starts in |0>'. The clean-ancilla condition (W returns to |0> for every x) pins down only the (I,W) block, M31 = 0; it says nothing about the (W,W) block M33 or the (W,O) block M32, both of which are invisible when the work register starts at z = 0. The proof's two sentences — 'uses I only as a control' (which does not by itself preclude controlled gates writing x-dependent values into W) and 'restores W by applying the inverse of the circuit that computed into it' — do not establish M33 = I_W, and the (W,O) = 0 entry asserted in the lemma's matrix is not argued at all. Lemma 10's three-copy product requires each copy C_{M,j} to act as (x,y,z) -> (x, y+Mx+BP^j z, z); if a depth-optimized Jiang schedule permutes or reuses work qubits so that M33 ≠ I, or lets the uncompute read O so that M32 ≠ 0, the three copies leave W in mutually incompatible states and the Bz cancellation does not fire, collapsing Theorem 1. Please verify the (W,W) = I and (W,O) = 0 blocks against arXiv:1907.05087v3, reproducing the relevant construction, or modify the construction so that these blocks are guaranteed explicitly.
[§4.2, singular-M extension] The claim that Lemma 4.2 of [JST+20], stated for an invertible off-diagonal block, 'also applies to arbitrary binary matrices' is supported only by the reference to their Corollary 4.5, which is not quoted. This matters because the factors A_1,...,A_6 in the Urschel factorization (Theorem 11) used by Theorem 12 are arbitrary binary matrices, so Lemma 10 must hold for singular M. Given that the W-blocks are admitted to be unspecified in the source, the authors should verify against the full version that Corollary 4.5 indeed permits singular blocks and that the blockwise construction nowhere invokes M^{-1} or invertibility of the off-diagonal block.

Minor objections (4)

[Corollary 8] In the text of Corollary 8, the lower-bound statement is attributed to 'Corollary 7', but the lower bound is stated as Theorem 7; please renumber to avoid the inconsistency.
[Lemma 14 proof] Typo: 'Remeber that k = log(1/epsilon) + 2' should read 'Remember'. Please also proofread the surrounding paragraphs for similar slips.
[Lemma 9, displayed matrix] The block labels in the displayed matrix of Lemma 9 (subscripts on the identity blocks such as 'I I', 'I O', 'I W') are typeset confusingly and make it hard to read which block acts on which register; please label the rows and columns explicitly as (I, O, W).
[Lemma 24] The counting argument for the workspace lower bound counts distinct diagonal unitaries up to global phase while circuits are counted as physical gate sequences; the comparison should state explicitly that counting is modulo global phase, as unitaries in (1) are defined up to a global phase.

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

The paper

The paper claims

Every n-qubit Clifford circuit has a catalytic implementation of depth O(n/(s log n)) using O(sn) dirty qubits and no clean workspace.

The reading

The paper asks whether the depth reduction that Clifford circuits get from clean ancilla qubits can be achieved when the workspace is dirty — qubits in arbitrary, possibly entangled states that must be restored exactly after the computation. It answers yes: every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(n/(s\log n))$ using $O(sn)$ catalytic qubits and no clean qubits, and tuning $s$ to $n/\log^2 n$ gives the full logarithmic depth with $O(n^2/\log^2 n)$ catalytic qubits. The same cancellation principle extends to diagonal gates in any fixed level $C_k$ of the Clifford hierarchy and to semi-Clifford unitaries, with a matching lower bound showing the diagonal construction is depth-optimal. The upshot is that idle, information-bearing qubits on a device can replace initialized workspace without losing the asymptotic depth–workspace tradeoff.

What carries the argument

The central device is the P-cycling cancellation: the $2\times 2$ binary matrix $P = \left[\begin{smallmatrix}0&1\\1&1\end{smallmatrix}\right]$, which satisfies $P^3 = I$ and $I + P + P^2 = 0$ over $\mathbb{F}_2$. Applied in parallel to pairs of catalytic qubits, conjugation by $P$ makes the three unknown workspace contributions of a Jiang-style parallel CNOT addition cancel, so the work register is exactly restored while the desired addition into the input is computed. The second load-bearing piece is Urschel's six-factor decomposition of a $2n\times 2n$ invertible binary matrix into block-unitriangular factors, which removes the clean output register; the Aaronson–Gottesman normal form then turns the CNOT construction into a full Clifford construction. For diagonal hierarchy gates, the corresponding device is a monomial-cycling construction that averages a phase over all nonzero work strings so the dependence on the initial work state cancels and only the input-dependent phase remains.

Extended reading notes

Core claim

On the paper's own terms, the discovery is that clean workspace is not required for the full depth–workspace tradeoff of Clifford circuits and their near relatives. The unknown content of the work register is cancelled algebraically rather than initialized away: three copies of a parallel CNOT addition circuit are conjugated by a binary linear map $P$ acting on pairs of work qubits, where $P^3 = I$ and $I + P + P^2 = 0$ over $\mathbb{F}_2$, so the spurious contributions $Bz$, $BPz$, $BP^2 z$ from the dirty register sum to zero while the register returns to its starting value. A six-factor block-unitriangular decomposition eliminates the clean output register, and the Clifford normal form lifts the result from CNOT circuits to all Clifford circuits, giving Theorem 1. For diagonal gates in level $C_k$, the same principle is applied to phase polynomials monomial by monomial, cycling the work register through all nonzero strings so the accumulated phase depends only on the input; a Dickson-based reduction of high-degree monomials keeps the workspace at $O(n^k/\log^2(n+1))$ for logarithmic depth. The paper also shows the diagonal construction is worst-case depth-optimal and that the approximate Toffoli with exponentially few $T$ gates can be run in optimal depth $O(\log n)$ using catalytic qubits.

Load-bearing premise

The entire construction hinges on Lemma 9, which extends Jiang et al.'s parallel-addition lemma from invertible off-diagonal blocks to arbitrary singular ones while asserting the dirty work register is restored exactly; if that extension fails, the P-cycling cancellation in Lemma 10 does not sum to zero and Theorem 1 collapses.

Editorial extensions

If this is right

Clean workspace is not required for the full depth–workspace tradeoff of Clifford circuits: dirty qubits match the asymptotic depth achievable with initialized ancillas, at the same space cost.
The tradeoff is tunable — depth $O(n/(s\log n))$ with $O(sn)$ catalytic qubits — and a cited lower bound shows no asymptotic improvement is possible, so the construction is optimal in the worst case.
The approximate Toffoli with exponentially few $T$ gates can be implemented in optimal depth $O(\log n)$ using $O(n\log(1/\epsilon))$ catalytic qubits and $O(\log(1/\epsilon))$ clean qubits.
Diagonal gates in any fixed level $C_k$ of the Clifford hierarchy admit logarithmic-depth catalytic implementations with $O(n^k/\log^2(n+1))$ catalytic qubits, which a counting lower bound shows is worst-case optimal; the same bounds carry to semi-Clifford unitaries given a Clifford–diagonal decomposition.
With native fan-out gates, the remaining $O(\log n)$ depth overhead disappears, giving depth $O(1)$ with wider catalytic registers in the stated parameter regimes.

Reading between the lines

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

The success of P-cycling suggests a general template for using dirty workspace: arrange the computation so the unknown work state enters linearly and cancels over a short group cycle; the Clifford and diagonal-hierarchy settings obey this template, and gates outside them would need an analogous algebraic cancellation to exist.
If the construction is correct, it lends concrete support to the paper's 'space collapse' conjecture for general unitaries, by exhibiting the first broad class where information-bearing memory is provably as good as clean memory for depth reduction.
A testable extension is whether the same three-copy cancellation works when $P$ is replaced by any element of order three in a larger matrix group satisfying $P^2 + P + I = 0$, which would port the construction to circuits over other finite groups.
The construction pushes the depth bottleneck onto fan-out-style data distribution, so hardware with native collective multi-target gates could realize the constant-depth improvement in the identified parameter regime.

Original abstract

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

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-01: 1 request, 3,865 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.30 · human participants 0.01 · controlled comparison 0.29 · randomized assignment 0.01 · states quantitative result 0.98 · 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.

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

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	Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state.	background 0.95	0.05	0.02	asserted 0.98
s1	In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation.	contribution 0.94	0.30	0.05	unclear 0.50
s2	We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available.	result 0.99	0.96	0.85	asserted 1.00
s3	We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.	result 0.75	0.94	0.13	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.94 · evidence from proof or derivation 1.00.

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

References

Works cited (13)

[1]

[AG04] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004.doi: 10.1103/PhysRevA.70.052328 . arXiv: quant-ph/0406196. [AM25] Aryan Agarwala and Ian Mertz. Bipartite matching is in catalytic logspace. InIEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society,

View on Pith Pith review arXiv 2004
[3]

[CM25] James Cook and Ian Mertz. Tree evaluation is in space O(log n · log log n).SIAM Journal on Computing (SICOMP), Special Section STOC 2024:130–160, 2025.doi: 10.1137/24M1690126. [CP26] James Cook and Edward Pyne. Efficient catalytic graph algorithms. InInnovations in Theoretical Computer Science Conference (ITCS), volume 362 ofLeibniz International P...

View on Pith Pith review arXiv 2024
[6]

[Gid15] Craig Gidney. Constructing large controlled nots. https://algassert.com/circuits/ 2015/06/05/Constructing-Large-Controlled-Nots.html,

View on Pith 2015
[11]

[KMS26] Michal Kouck´ y, Ian Mertz, and Sasha Sami. Understanding robust catalytic computing. Computing Research Repository (CoRR), abs/2605.09648, 2026.doi: 10.48550/ARXIV. 2605.09648. [LPT24] Jiatu Li, Edward Pyne, and Roei Tell. Distinguishing, predicting, and certifying: on the long reach of partial notions of pseudorandomness. InIEEE Symposium on Fou...

View on Pith Pith review arXiv doi:10.48550/arxiv.2605.09648 2026
[12]

arXiv: 2508.14470 [quant-ph].url:https://arxiv.org/abs/2508.14470. [MN18] Dmitri Maslov and Yunseong Nam. Use of global interactions in efficient quantum circuit constructions.New Journal of Physics, 20:033018, 2018.doi: 10.1088/1367- 2630/aaa398. [Mer23] Ian Mertz. Reusing space: techniques and open problems.Bulletin of the EATCS (B.EATCS), 141:57–106,

View on Pith Pith review arXiv 2018
[13]

arXiv: 1907 . 05087v3 [quant-ph]. Full version, revised

View on Pith 1907
[1901]

28 [DPT+25] Dean Doron, Edward Pyne, Roei Tell, and R. Ryan Williams. When connectivity is hard, random walks are easy with non-determinism. InACM Symposium on Theory of Computing (STOC), pages 1108–1117. Association for Computing Machinery (ACM), 2025.doi:10.1145/3717823.3718303. [DCM26] Zhenyu Du, Siyuan Cheng, and Xiongfeng Ma. Low-depth random unitari...

View on Pith doi:10.1145/3717823.3718303 2025
[2017]

arXiv: 1706.07884 [quant-ph]. [GKZ25] David Gosset, Robin Kothari, and Chenyi Zhang. Multi-qubit toffoli with exponentially fewer t gates.arXiv preprint arXiv:2510.07223,

View on Pith Pith review arXiv
[2018]

arXiv: 1712.01557 [quant-ph] .url: https://arxiv.org/abs/1712. 01557. [JST+20] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 213–229, 2020.doi: 10 . 1137 / 1 . 97...

View on Pith Pith review arXiv 2020
[2022]

[KG25] Tanuj Khattar and Craig Gidney. Rise of conditionally clean ancillae for efficient quantum circuit constructions.Quantum, 9:1752, 2025.doi: 10.22331/q-2025-05- 21-1752. [Kou16] Michal Kouck´ y. Catalytic computation.Bulletin of the EATCS (B.EATCS), 118,

View on Pith doi:10.22331/q-2025-05- 2025
[2023]

29 [MLW+09] M. M¨ uller, I. Lesanovsky, H. Weimer, H. P. B¨ uchler, and P. Zoller. Mesoscopic Rydberg gate based on electromagnetically induced transparency.Physical Review Letters, 102:170502, 2009.doi:10.1103/PhysRevLett.102.170502. [PMH08] Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits.Quantum Informa...

View on Pith Pith review arXiv 2009
[2025]

27 [BBC+95] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elemen- tary gates for quantum computation.Physical Review A, 52(5):3457–3467, 1995.doi: 10.1103/PhysRevA.52.3457. arXiv:quant-ph/9503016. [BCH+20] Michael Beverland, Earl Campbell, Mark Ho...

View on Pith Pith review arXiv 1995
[2026]

arXiv: 2609.06528 [quant-ph].url: https://arxiv.org/abs/2609. 06528. [FMS+25] Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully charac- terizing lossy catalytic computation. InInnovations in Theoretical Computer Science Conference (ITCS), volume 325 ofLeibniz International Proceedings in Informatics (LIPIcs), 50:1–50:13. Schloss Da...

View on Pith Pith review arXiv

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]

[AG04] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004.doi: 10.1103/PhysRevA.70.052328 . arXiv: quant-ph/0406196. [AM25] Aryan Agarwala and Ian Mertz. Bipartite matching is in catalytic logspace. InIEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society,

View on Pith Pith review arXiv 2004

[2] [3]

[CM25] James Cook and Ian Mertz. Tree evaluation is in space O(log n · log log n).SIAM Journal on Computing (SICOMP), Special Section STOC 2024:130–160, 2025.doi: 10.1137/24M1690126. [CP26] James Cook and Edward Pyne. Efficient catalytic graph algorithms. InInnovations in Theoretical Computer Science Conference (ITCS), volume 362 ofLeibniz International P...

View on Pith Pith review arXiv 2024

[3] [6]

[Gid15] Craig Gidney. Constructing large controlled nots. https://algassert.com/circuits/ 2015/06/05/Constructing-Large-Controlled-Nots.html,

View on Pith 2015

[4] [11]

[KMS26] Michal Kouck´ y, Ian Mertz, and Sasha Sami. Understanding robust catalytic computing. Computing Research Repository (CoRR), abs/2605.09648, 2026.doi: 10.48550/ARXIV. 2605.09648. [LPT24] Jiatu Li, Edward Pyne, and Roei Tell. Distinguishing, predicting, and certifying: on the long reach of partial notions of pseudorandomness. InIEEE Symposium on Fou...

View on Pith Pith review arXiv doi:10.48550/arxiv.2605.09648 2026

[5] [12]

arXiv: 2508.14470 [quant-ph].url:https://arxiv.org/abs/2508.14470. [MN18] Dmitri Maslov and Yunseong Nam. Use of global interactions in efficient quantum circuit constructions.New Journal of Physics, 20:033018, 2018.doi: 10.1088/1367- 2630/aaa398. [Mer23] Ian Mertz. Reusing space: techniques and open problems.Bulletin of the EATCS (B.EATCS), 141:57–106,

View on Pith Pith review arXiv 2018

[6] [13]

arXiv: 1907 . 05087v3 [quant-ph]. Full version, revised

View on Pith 1907

[7] [1901]

28 [DPT+25] Dean Doron, Edward Pyne, Roei Tell, and R. Ryan Williams. When connectivity is hard, random walks are easy with non-determinism. InACM Symposium on Theory of Computing (STOC), pages 1108–1117. Association for Computing Machinery (ACM), 2025.doi:10.1145/3717823.3718303. [DCM26] Zhenyu Du, Siyuan Cheng, and Xiongfeng Ma. Low-depth random unitari...

View on Pith doi:10.1145/3717823.3718303 2025

[8] [2017]

arXiv: 1706.07884 [quant-ph]. [GKZ25] David Gosset, Robin Kothari, and Chenyi Zhang. Multi-qubit toffoli with exponentially fewer t gates.arXiv preprint arXiv:2510.07223,

View on Pith Pith review arXiv

[9] [2018]

arXiv: 1712.01557 [quant-ph] .url: https://arxiv.org/abs/1712. 01557. [JST+20] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. InProceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 213–229, 2020.doi: 10 . 1137 / 1 . 97...

View on Pith Pith review arXiv 2020

[10] [2022]

[KG25] Tanuj Khattar and Craig Gidney. Rise of conditionally clean ancillae for efficient quantum circuit constructions.Quantum, 9:1752, 2025.doi: 10.22331/q-2025-05- 21-1752. [Kou16] Michal Kouck´ y. Catalytic computation.Bulletin of the EATCS (B.EATCS), 118,

View on Pith doi:10.22331/q-2025-05- 2025

[11] [2023]

29 [MLW+09] M. M¨ uller, I. Lesanovsky, H. Weimer, H. P. B¨ uchler, and P. Zoller. Mesoscopic Rydberg gate based on electromagnetically induced transparency.Physical Review Letters, 102:170502, 2009.doi:10.1103/PhysRevLett.102.170502. [PMH08] Ketan N. Patel, Igor L. Markov, and John P. Hayes. Optimal synthesis of linear reversible circuits.Quantum Informa...

View on Pith Pith review arXiv 2009

[12] [2025]

27 [BBC+95] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elemen- tary gates for quantum computation.Physical Review A, 52(5):3457–3467, 1995.doi: 10.1103/PhysRevA.52.3457. arXiv:quant-ph/9503016. [BCH+20] Michael Beverland, Earl Campbell, Mark Ho...

View on Pith Pith review arXiv 1995

[13] [2026]

arXiv: 2609.06528 [quant-ph].url: https://arxiv.org/abs/2609. 06528. [FMS+25] Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker. Fully charac- terizing lossy catalytic computation. InInnovations in Theoretical Computer Science Conference (ITCS), volume 325 ofLeibniz International Proceedings in Informatics (LIPIcs), 50:1–50:13. Schloss Da...

View on Pith Pith review arXiv