Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Multi-Controlled Quantum Gates in Linear Nearest Neighbor

T0 review · 2 major / 4 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 claims that multi-controlled X and SU(2) gates on a linear nearest-neighbor chain can be implemented with 4k+8n−16 and 4k+8n−14 CNOT gates respectively, for any placement of controls, target, and dirty ancilla.

desk verdict Real advance in LNN multi-controlled gate decompositions, but the proof of the advertised worst-case constant has a small gap in the swap-cancellation step. read the letter →

arxiv 2506.00695 v2 pith:KV662PO4 submitted 2025-05-31 quant-ph

Ben Zindorf , Sougato Bose This is my paper
classification quant-ph MSC 81P68 PACS 03.67.Lx
keywords multi-controlledgateslinearnearestneighborCNOTcountToffoligaterelative-phaseClifford+TSU(2)quantumcircuitdecomposition
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

The paper tries to establish that multi-controlled single-target gates — the quantum analog of if-then-else, applying a one-qubit operation only when all $n$ control qubits are in the state $|11\dots 1\rangle$ — can be implemented cheaply even on a linear nearest-neighbor (LNN) chip, where two-qubit gates act only on adjacent qubits. It exhibits a deterministic construction that implements a multi-controlled X (MCX) gate, with one dirty (unknown-state) ancilla, using at most $4k+8n-16$ CNOT gates, and a multi-controlled SU(2) (MCSU2) gate, with no ancilla, using at most $4k+8n-14$, where $n$ is the number of controls and $k$ the number of qubits in the smallest chain containing them. These counts improve on previous linear-nearest-neighbor decompositions by up to 60%, and unlike earlier linear-cost methods, they hold for every choice of controls, target, and ancilla. If the bounds are correct, the same construction also shows that an all-to-all MCSU2 can be done with only 6 arbitrary $R_z$ rotations instead of 8, without extra Clifford+T cost, and that a single long-range CNOT over $k$ qubits costs at most $4k$ CNOTs.

What carries the argument

The load-bearing identity is Lemma 3, which writes any multi-controlled rotation $[R_{\hat v'}(\lambda)]_C^{q_t}$ as the product $[\Pi(\hat v_2)]_{C_2}^{q_t}[\Pi(\hat v_1)]_{C_1}^{q_t}[\Pi(\hat v_2)]_{C_2}^{q_t}[\Pi(\hat v_1)]_{C_1}^{q_t}$ with $C_1\cup C_2=C$, $\hat v_1\perp \hat v'$, and $\hat v_2=\hat R_{\hat v'}(\lambda/4)\hat v_1$. On top of it sits the V-chain: a recursive decomposition of MCZ-$\Delta$ in which each step brackets the previous gate by two nearest-neighbor relative-phase Toffoli gates $[X]_{\{q_j,c_j^-\}}^{q_{j-1}}$, producing a circuit whose internal Toffoli targets sit between their controls and therefore cost the unrestricted-connectivity price of 3 CNOT gates. The $\Pi$-gate notation ($\Pi_{\hat x}=X$, $\Pi_{\hat y}=Y$, $\Pi_{\hat z}=Z$, $H=\Pi_{\bar y}^{\pi/4}$, etc.) is the bookkeeping that makes the cancellations visible.

What would settle it

Directly verify Lemma 3 on a small chain, say k=4: enumerate every choice of target and controls, simulate the four-Pi decomposition with the C1/C2 split, and check the resulting unitary against the intended multi-controlled rotation; any mismatch refutes the method. For the headline bounds, compile the constructed circuit for a concrete instance such as n=2 controls over k=4 LNN qubits with controls not neighboring the target, and count CNOT gates; a count above 4k+8n-16 for MCX or above 4k+8n-14 for MCSU2 would refute the claimed upper bound.

Watch

Extended reading notes

Core claim

Using the Hermitian $\pi$-rotation formalism, the paper derives a relative-phase multi-controlled $Z$ gate, MCZ-$\Delta$, whose Clifford+T cost is $L_{Z\Delta}(k_1,n_1)=(2k_1+4n_1-3,\,8n_1-8,\,4n_1-2,\,0)$ in (CNOT, T, H). Two MCZ-$\Delta$ gates plus two multi-controlled $\Pi_{\bar x}$-$\Delta$ gates around an axis-changing $\Pi_M$ implement any MCSU2; for MCX the paper uses the identity $[X]_C^{q_t}=[H]_{q_t}[R_{\hat x}(2\pi)]_{C'}^{q_a}[H]_{q_t}$, with a freely chosen dirty ancilla $q_a$, so the MCX becomes an MCSU2 with $n+1$ controls. The counts follow by summing the recursive V-chain decomposition of MCZ-$\Delta$, which stacks relative-phase Toffoli gates whose target lies between its controls so each costs only 3 CNOT, 4 T, and 2 H gates. The construction makes no assumption about control location, and a rule for choosing the dirty ancilla guarantees the worst-case counts $4k+8n-16$ (MCX) and $4k+8n-14$ (MCSU2).

Load-bearing premise

The load-bearing premise is Lemma 3, which says any multi-controlled rotation can be decomposed into four multi-controlled pi-rotations for any partition of the control set; if this fails for some placement of the controls, the reported upper bounds do not follow.

Editorial extensions

If this is right

  • The LNN MCX gate with $n$ controls over $k$ qubits uses at most $4k+8n-16$ CNOT gates; the previous linear-cost construction used $8k+14n-34$.
  • The LNN MCSU2 gate without ancilla uses at most $4k+8n-14$ CNOT gates and, when the target is at the end of the chain, only 6 arbitrary $R_z$ gates.
  • The all-to-all MCSU2 gate, obtained by setting $k=n+1$, uses $12n+O(1)$ CNOTs, $16n+O(1)$ T gates, and only 6 $R_z$ gates, improving the previous 8-$R_z$ count.
  • For a single long-range CNOT ($n=1$), the bound becomes $4k$, the best known for one CNOT across $k$ LNN qubits.
  • Because LNN connectivity embeds in essentially any qubit layout, these circuits can be routed to 2D grids without paying the quadratic SWAP overhead of earlier methods.

Reading between the lines

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

  • A practical consequence the authors only hint at: in fault-tolerant settings the two saved $R_z$ rotations are usually the most expensive resource, so the 6-$R_z$ all-to-all MCSU2 could lower total cost even where the CNOT count is unchanged.
  • Because the $n=1$ long-range CNOT case is embedded in the general construction, any future improvement below $4k$ CNOTs for one long-range CNOT would automatically lower the $4k+8n-16$ MCX bound; conversely, the headline bound cannot be improved without improving that simpler gate.
  • The reported average CNOT counts from the authors' software are below the worst-case bound; a broader numerical study of random control placements could reveal which constant-term reductions are generic, something the paper does not claim to prove.
  • The same V-chain of relative-phase Toffolis should apply to other multi-controlled parameterized gates by swapping the axis-transforming $\Pi_M$ gates, so the method may extend beyond $X$ and SU(2) targets.
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 / 4 minor

Summary. The manuscript proposes a recursive linear-nearest-neighbor (LNN) decomposition for multi-controlled SU(2) gates without ancilla and for multi-controlled X (MCX) gates with one dirty ancilla, built from Hermitian pi-rotation identities and relative-phase Toffoli / MCZ-delta structures. It derives closed-form resource counts with headline bounds of 4k+8n-16 CNOTs for MCX and 4k+8n-14 CNOTs for MCSU2, together with an all-to-all MCSU2 implementation using only six arbitrary Rz rotations. The construction is intended to be flexible with respect to the locations of controls, target, and ancilla, and the paper also reports constant-factor, depth, and ancilla-based reductions in the appendices.

Significance. If the central bounds are correct, the MCX result improves the leading CNOT coefficient of the best previous LNN construction from 8k to 4k, and the six-Rz all-to-all MCSU2 result improves the previous eight-Rz count while retaining the same leading Clifford+T scaling. The cost formulas are explicit and parameter-free, and the small boundary cases (n=1,k=3 for MCX gives 4 CNOTs; n=1,k=2 for MCSU2 gives 2 CNOTs) match known optimal values, which lends credibility to the construction. The main correctness risks are the undocumented SWAP-cancellation step in the MCX worst-case reduction and the unproved foundational Lemma 3, both of which are load-bearing for the headline upper bounds.

major comments (2)
  1. [Section 5, after Eq. (13)] The reduction of the case n1>0, n2=0, n+=0, n-=1 is load-bearing but not established. Direct substitution into the second line of Eq. (13) gives 4k+8n-12 CNOTs, not the claimed 4k+8n-16. The text closes this gap by asserting that swapping the bottom qubit with the one above it requires two SWAP gates and that these increase the CNOT count by only 4 because a pair of CNOT gates commute with the MCX gate and cancel out. Two neighboring-qubit SWAPs normally cost six CNOTs, and the swapped qubits are a dirty ancilla and a member of the controls-target set, so the MCX is not invariant under the swap in any obvious way. Please provide the explicit circuit identity for the claimed two-CNOT cancellation, or revise the upper bound accordingly.
  2. [Section 2, Lemma 3 and Circuit (4)] The decomposition of an arbitrary multi-controlled SU(2) rotation into four multi-controlled pi-rotations with an arbitrary split of the control set is stated without proof and attributed to Ref. [35], which is the authors' arXiv preprint. Since Circuit (4) and therefore the MCSU2 cost in Eq. (15) and the MCX cost in Eq. (13) all depend on this identity, the manuscript should include a proof in an appendix or cite a peer-reviewed version of Ref. [35]. As written, the paper is not self-contained on this load-bearing point.
minor comments (4)
  1. [Section 5, after Eq. (15)] The displayed upper bound reads LSU(k,n) <= (4k-8n-14, ...), but the abstract, conclusion, and Table 3 all use 4k+8n-14; this appears to be a sign typo and should be corrected.
  2. [Section 5, Eq. (13)] The overline notation used for (n±)_1, (n±)_3, and (n±)_5 in the paragraph after Eq. (13) is not rendered or defined distinctly from the earlier (n±)_j definitions in Eq. (12). Please introduce separate symbols and state their definitions explicitly before they are used in Eq. (13).
  3. [Section 5, Figure 2] The average-case CNOT counts and the software mentioned in the text are not accompanied by code, data, or a detailed algorithmic description, so the curves in Figure 2 cannot be independently verified. Please release the software or clearly label these curves as illustrative.
  4. [Throughout] There are several typographical and formatting issues, including "prioratize achieveing" in Section 5, "acheve" in Appendix C, and inconsistent line-breaking of "SWAP" in the appendices. These should be cleaned up.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the CNOT bounds are computed by explicit gate-count recursion, with self-cited lemmas serving as independent parameter-free building blocks.

full rationale

The claimed upper bounds 4k+8n-16 (MCX) and 4k+8n-14 (MCSU2) are not equivalent to any input to the derivation. They are obtained by summing explicit CNOT/T/H/Rz vectors over a recursively constructed decomposition: Eq.11 for MCZ-∆ follows from Eq.9/Eq.10 and the explicit base circuit (19); Eq.12 and Eq.14 follow by substitution into Eq.7 and Eq.5; Eq.13 and Eq.15 follow by substituting these into Eq.3 and Eq.1. None of these equations contains the target bound as an assumption, and the final worst-case maximization over n+ and n- in Section 5 is a separate argument. The load-bearing identities from the authors' earlier papers appear as Lemma 1 (from [60]), Lemma 2 (from [60]), Lemma 3 (from [35]), and Lemma 5 (from [60]); these are parameter-free gate identities whose stated assumptions do not include the CNOT bounds. In particular, Lemma 3 is a controlled version of the two-Π decomposition of SU(2) and is reused as a building block rather than as the result being proved, so the self-citation is real evidence under the stated criteria. The only unproved step is the Section 5 claim that swapping the bottom ancilla costs four CNOTs after two CNOT cancellations; this is a correctness gap in the worst-case analysis, not a circular reduction, because it does not identify the bound with a fitted parameter or a self-citation. There are no fitted inputs, no empirical predictions, and no uniqueness theorem invoked to rule out alternatives. The derivation is therefore self-contained apart from routine reuse of the authors' earlier, independently statable lemmas.

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

The central claims rest on the authors' own prior lemmas (Refs. [35,60]) and on a known lower bound for long-range CNOT (Ref. [64]). No free parameters are fitted to data; all resource counts follow from the circuit construction.

assumptions (5)
  • domain assumption Lemma 3 from Ref. [35]: any [R_{v'}(λ)]^C_qt decomposes into four MCΠ gates with control sets C1,C2 partitioning C.
    Foundation of Circuit (4), used for all MCSU2 and MCX cost derivations; proved in the authors' prior paper, not in this manuscript.
  • domain assumption Lemma 2 from Ref. [60]: any MCSU2 gate reduces to MCRx plus two single-qubit Π gates.
    Used at the start of Section 2 to focus the construction on MCRx.
  • domain assumption Lemma 5 from Ref. [60]: controlled Π(v) equals R_σ(θ) R_τ R_σ†(θ) when v = R_σ(θ)τ.
    Used to decompose controlled Π gates in Circuits 13 and 14.
  • domain assumption A long-range CNOT over k LNN qubits costs about 4k CNOT gates (Ref. [64]).
    Used to argue that the 4(k-n) overhead over ATA is minimal (Section 6).
  • domain assumption Dirty ancillas are in arbitrary unknown states and must be returned unchanged; relative-phase gates (Δ) may be assigned arbitrarily and cancel in pairs.
    Standard assumption in relative-phase Toffoli constructions; the MCZ-delta recursion relies on this cancellation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi-Controlled Quantum Gates in Linear Nearest Neighbor." pith.science (2026). https://pith.science/paper/KV662PO4

@misc{pith2026250600695,
  author       = {Pith},
  title        = {Pith review of: Multi-Controlled Quantum Gates in Linear Nearest Neighbor},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KV662PO4}},
  note         = {Machine review of arXiv:2506.00695}
}
abstract

Multi-controlled single-target (MC) gates are some of the most crucial building blocks for varied quantum algorithms. How to implement them optimally is thus a pivotal question. To answer this question in an architecture-independent manner, and to get a worst-case estimate, we should look at a linear nearest-neighbor (LNN) architecture, as this can be embedded in almost any qubit connectivity. Motivated by the above, here we describe a method which implements MC gates using no more than $\sim 4k+8n$ CNOT gates -- up-to $60\%$ reduction over state-of-the-art -- while allowing for complete flexibility to choose the locations of $n$ controls, the target, and a dirty ancilla out of $k$ qubits. More strikingly, in case $k \approx n$, our upper bound is $\sim 12n$ -- the best known for unrestricted connectivity -- and if $n = 1$, our upper bound is $\sim 4k$ -- the best known for a single long-range CNOT gate over $k$ qubits -- therefore, if our upper bound can be reduced, then the cost of one or both of these simpler versions of MC gates will be immediately reduced accordingly. In practice, our method provides circuits that tend to require fewer CNOT gates than our upper bound for almost any given instance of MC gates.

Figures

Figures reproduced from arXiv: 2506.00695 by the authors.

Figure 1
Figure 1. A geometrical description of the axes mentioned in this section. (a) The parameterized axes ˆv [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Our upper bound and the average CNOT count of the LNN MCX gate with [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

Discussion (0). Sign in to comment.

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

  1. Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound

    quant-ph 2026-01 conditional novelty 7.0 of 10

    An explicit construction of (n,n−1) quantum random access codes achieves the conjectured success probability 1/2 + sqrt((n−1)/n)/2 for every n, with an O(n)-depth decoding circuit.

  2. Generalized tensor transforms and their applications in classical and quantum computing

    quant-ph 2025-07 reject novelty 3.0 of 10

    The claim that tunable tensor-product transforms outperform fixed transforms for quantum compression and encoding rests on fits to the data, not on independent predictions.

Reference graph

Works this paper leans on

73 extracted references · 52 canonical work pages · cited by 2 Pith papers

  1. [35]

    Efficient Implementation of Multi-Controlled Quantum Gates,

    B. Zindorf and S. Bose, “Efficient Implementation of Multi-Controlled Quantum Gates,” Apr. 2024, arXiv:2404.02279 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2404.02279

    arXiv 2024

  2. [1]

    Universal quantum circuits for quantum chemistry,

    J. M. Arrazola, O. D. Matteo, N. Quesada, S. Jahangiri, A. Delgado, and N. Killoran, “Universal quantum circuits for quantum chemistry,” Quantum, vol. 6, p. 742, Jun. 2022, publisher: Verein zur F¨ orderung des Open Access Publizierens in den Quantenwissenschaften. [Online]. Available: https://quantum-journal.org/papers/q-2022-06-20-742/

    work page 2022

  3. [2]

    Parametrized Constant-Depth Quantum Neuron,

    J. H. A. De Carvalho and F. M. D. P. Neto, “Parametrized Constant-Depth Quantum Neuron,” IEEE Transactions on Neural Networks and Learning Systems , pp. 1–12, 2024. [Online]. Available: https://ieeexplore.ieee.org/document/10180218/

    work page arXiv 2024

  4. [3]

    Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz

    X.-H. Ni, L.-X. Li, Y.-Q. Song, Z.-P. Jin, S.-J. Qin, and F. Gao, “Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz,” Sep. 2024, arXiv:2405.04303 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2405.04303

    work page Pith review arXiv 2024

  5. [4]

    Quantum circuits for isometries,

    R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, “Quantum circuits for isometries,” Physical Review A , vol. 93, no. 3, p. 032318, Mar. 2016. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.93.032318

    doi:10.1103/physreva.93.032318 2016

  6. [5]

    Quantum Circuits for Sparse Isometries,

    E. Malvetti, R. Iten, and R. Colbeck, “Quantum Circuits for Sparse Isometries,” Quantum, vol. 5, p. 412, Mar. 2021, publisher: Verein zur F¨ orderung des Open Access Publizierens in den Quantenwissenschaften. [Online]. Available: https://quantum-journal.org/papers/q-2021-03-15-412/

    work page 2021

  7. [6]

    Efficient quantum circuits for port-based teleportation,

    D. Grinko, A. Burchardt, and M. Ozols, “Efficient quantum circuits for port-based teleportation,” 2023, version Number: 2. [Online]. Available: https://arxiv.org/abs/2312.03188

    arXiv 2023

  8. [7]

    Distribution of controlled unitary quantum gates towards factoring large numbers on today’s small-register devices,

    A. T˘ an˘ asescu, D. Constantinescu, and P. G. Popescu, “Distribution of controlled unitary quantum gates towards factoring large numbers on today’s small-register devices,” Scientific Reports , vol. 12, no. 1, p. 21310, Dec. 2022, publisher: Nature Publishing Group. [Online]. Available: https://www.nature.com/articles/s41598-022-25812-z

    work page 2022

Show all 73 references
  1. [8]

    Circuit-Based Quantum Random Access Memory for Classical Data,

    D. K. Park, F. Petruccione, and J.-K. K. Rhee, “Circuit-Based Quantum Random Access Memory for Classical Data,” Scientific Reports , vol. 9, no. 1, p. 3949, Mar. 2019. [Online]. Available: https://www.nature.com/articles/s41598-019-40439-3

    2019

  2. [9]

    Function Design for Minimum Multiple-Control Toffoli Circuits of Reversible Adder/Subtractor Blocks and Arithmetic Logic Units,

    M. B. Ali, T. Hirayama, K. Yamanaka, and Y. Nishitani, “Function Design for Minimum Multiple-Control Toffoli Circuits of Reversible Adder/Subtractor Blocks and Arithmetic Logic Units,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vo...

    2018

  3. [10]

    Quantum Mechanics Helps in Searching for a Needle in a Haystack,

    L. K. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack,” Physical Review Letters, vol. 79, no. 2, pp. 325–328, Jul. 1997, publisher: American Physical Society. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.79.325 17

    1997 doi

  4. [11]

    Quantum circuits for partial differential equations in Fourier space,

    M. Lubasch, Y. Kikuchi, L. Wright, and C. M. Keever, “Quantum circuits for partial differential equations in Fourier space,” May 2025, arXiv:2505.16895 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2505.16895

    2025

  5. [12]

    Double-bracket algorithm for quantum signal processing without post-selection,

    Y. Suzuki, B. H. Tiang, J. Son, N. H. Y. Ng, Z. Holmes, and M. Gluza, “Double-bracket algorithm for quantum signal processing without post-selection,” Apr. 2025, arXiv:2504.01077 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2504.01077

    2025

  6. [13]

    TEPID-ADAPT: Adaptive variational method for simultaneous preparation of low-temperature Gibbs and low-lying eigenstates,

    B. Sambasivam, K. Sherbert, K. Shirali, N. J. Mayhall, E. Barnes, and S. E. Economou, “TEPID-ADAPT: Adaptive variational method for simultaneous preparation of low-temperature Gibbs and low-lying eigenstates,” Mar. 2025, arXiv:2503.14490 [quant-ph]. [Online]. Available: http:/...

    2025

  7. [14]

    Quantum Circuits for SU(3) Lattice Gauge Theory,

    P. Balaji, C. Conefrey-Shinozaki, P. Draper, J. K. Elhaderi, D. Gupta, L. Hidalgo, A. Lytle, and E. Rinaldi, “Quantum Circuits for SU(3) Lattice Gauge Theory,” Mar. 2025, arXiv:2503.08866 [hep-lat]. [Online]. Available: http://arxiv.org/abs/2503.08866

    2025 arXiv

  8. [15]

    Double-bracket quantum algorithms for quantum imaginary-time evolution,

    M. Gluza, J. Son, B. H. Tiang, Y. Suzuki, Z. Holmes, and N. H. Y. Ng, “Double-bracket quantum algorithms for quantum imaginary-time evolution,” Dec. 2024, arXiv:2412.04554 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2412.04554

    2024

  9. [16]

    Implementing semiclassical Szegedy walks in classical-quantum circuits for homomorphic encryption,

    S. A. Ortega, P. Fern´ andez, and M. A. Martin-Delgado, “Implementing semiclassical Szegedy walks in classical-quantum circuits for homomorphic encryption,” Journal of Physics: Complexity , vol. 6, no. 2, p. 025010, May 2025, publisher: IOP Publishing. [Online]. Available: htt...

    2025 doi

  10. [17]

    Quantum Wave Simulation with Sources and Loss Functions,

    C. B¨ osch, M. Schade, G. Aloisi, S. D. Keating, and A. Fichtner, “Quantum Wave Simulation with Sources and Loss Functions,” Feb. 2025, arXiv:2411.17630 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2411.17630

    2025 arXiv

  11. [18]

    An improved quantum algorithm of the multislice method,

    Y. Wang, Y. Sun, and Z. Ding, “An improved quantum algorithm of the multislice method,” iScience, vol. 28, no. 4, Apr. 2025, publisher: Elsevier. [Online]. Available: https://www.cell.com/iscience/abstract/S2589-0042(25)00426-2

    2025

  12. [19]

    Solving lattice gauge theories using the quantum Krylov algorithm and qubitization,

    L. W. Anderson, M. Kiffner, T. O’Leary, J. Crain, and D. Jaksch, “Solving lattice gauge theories using the quantum Krylov algorithm and qubitization,” Quantum, vol. 9, p. 1669, Mar. 2025, publisher: Verein zur F¨ orderung des Open Access Publizierens in den Quantenwissenschaft...

    2025

  13. [20]

    Block encoding of matrix product operators,

    M. Nibbi and C. B. Mendl, “Block encoding of matrix product operators,” Physical Review A , vol. 110, no. 4, p. 042427, Oct. 2024, publisher: American Physical Society. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.110.042427

    2024 doi

  14. [21]

    Matrix Representation of Arbitrarily Controlled Quantum Gates,

    M. Lewis, S. Soudjani, and P. Zuliani, “Matrix Representation of Arbitrarily Controlled Quantum Gates,” May 2022, arXiv:2205.02525 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2205.02525

    2022 arXiv

  15. [22]

    Universal quantum computation with ideal Clifford gates and noisy ancillas,

    S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” Physical Review A , vol. 71, no. 2, p. 022316, Feb. 2005. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.71.022316

    2005 doi

  16. [23]

    Quantum Computation and Quantum Information,

    M. A. Nielsen and I. Chuang, “Quantum Computation and Quantum Information,” American Journal of Physics, vol. 70, no. 5, pp. 558–559, May 2002, publisher: American Association of Physics Teachers. [Online]. Available: https://aapt.scitation.org/doi/10.1119/1.1463744

    2002 doi

  17. [24]

    Logic Synthesis for Fault-Tolerant Quantum Computers,

    N. C. Jones, “Logic Synthesis for Fault-Tolerant Quantum Computers,” Oct. 2013, arXiv:1310.7290 [quant-ph]. [Online]. Available: http://arxiv.org/abs/1310.7290 18

    2013 arXiv

  18. [25]

    IBM Quantum Computers: Evolution, Performance, and Future Directions,

    M. AbuGhanem, “IBM Quantum Computers: Evolution, Performance, and Future Directions,” Sep. 2024, arXiv:2410.00916 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2410.00916

    2024 arXiv

  19. [26]

    A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates,

    ——, “A Toffoli Gate Decomposition via Echoed Cross-Resonance Gates,” Jan. 2025, arXiv:2501.02222 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2501.02222

    2025 arXiv

  20. [27]

    Quantum logic with spin qubits crossing the surface code threshold,

    X. Xue, M. Russ, N. Samkharadze, B. Undseth, A. Sammak, G. Scappucci, and L. M. K. Vandersypen, “Quantum logic with spin qubits crossing the surface code threshold,” Nature, vol. 601, no. 7893, pp. 343–347, Jan. 2022. [Online]. Available: https://www.nature.com/articles/s41586...

    2022

  21. [28]

    Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures,

    M. Pedram and A. Shafaei, “Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures,” IEEE Circuits and Systems Magazine , vol. 16, no. 2, pp. 62–74, 2016. [Online]. Available: http://ieeexplore.ieee.org/document/7476978/

    2016

  22. [29]

    Synthesis of quantum circuits for linear nearest neighbor architectures,

    M. Saeedi, R. Wille, and R. Drechsler, “Synthesis of quantum circuits for linear nearest neighbor architectures,” Quantum Information Processing , vol. 10, no. 3, pp. 355–377, Jun. 2011. [Online]. Available: https://doi.org/10.1007/s11128-010-0201-2

    2011 doi

  23. [30]

    The Mapping and Optimization Method of Quantum Circuits for Clifford + T Gate,

    X. He, Z. Guan, and F. Ding, “The Mapping and Optimization Method of Quantum Circuits for Clifford + T Gate,” Journal of Applied Mathematics and Physics , vol. 07, no. 11, pp. 2796–2810, 2019. [Online]. Available: http://www.scirp.org/journal/doi.aspx?DOI=10.4236/jamp.2019.711192

    2019

  24. [31]

    Cost Reduction in Nearest Neighbour Based Synthesis of Quantum Boolean Circuits,

    M. H. A. Khan, “Cost Reduction in Nearest Neighbour Based Synthesis of Quantum Boolean Circuits,” Engineering Letters, vol. 16, no. 1, 2008

    2008

  25. [32]

    Optimization of LNN Reversible Circuits Using an Analytic Sifting Method,

    M. Lukac, P. Kerntopf, and M. Kameyama, “Optimization of LNN Reversible Circuits Using an Analytic Sifting Method,” Journal of Circuits, Systems and Computers , vol. 30, no. 09, p. 2150166, Jul. 2021, publisher: World Scientific Publishing Co. [Online]. Available: https://www....

    2021 doi

  26. [33]

    A Fast Optimization Algorithm for Nearest Neighbor Architecture Based on Quantum Weight,

    F. Ding, Z. Guau, and F. Ren, “A Fast Optimization Algorithm for Nearest Neighbor Architecture Based on Quantum Weight,” in 2019 IEEE 6th International Conference on Cloud Computing and Intelligence Systems (CCIS) , Dec. 2019, pp. 73–78. [Online]. Available: https://ieeexplore...

    2019

  27. [34]

    A Method of Mapping and Nearest-Neighbor for IBM QX Architecture,

    C. Zhang, Z. Guan, Y. Qian, and S. Feng, “A Method of Mapping and Nearest-Neighbor for IBM QX Architecture,” in 2022 International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT) , Aug. 2022, pp. 402–409. [Online]. Available: https://ieeexplor...

    2022

  28. [36]

    Elementary gates for quantum computation,

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Physical Review A , vol. 52, no. 5, pp. 3457–3467, Nov. 1995, publisher: American Physical Society. [Online]. A...

    1995 doi

  29. [37]

    Decomposition of Multi-controlled Special Unitary Single-Qubit Gates,

    R. Vale, T. M. D. Azevedo, I. C. S. Ara´ ujo, I. F. Araujo, and A. J. da Silva, “Decomposition of Multi-controlled Special Unitary Single-Qubit Gates,” Feb. 2023, arXiv:2302.06377 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2302.06377

    2023 arXiv

  30. [38]

    Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity,

    Y. He, M.-X. Luo, E. Zhang, H.-K. Wang, and X.-F. Wang, “Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity,” International Journal of Theoretical Physics , vol. 56, no. 7, pp. 2350–2361, Jul. 2017. [Online]. Available: https://doi.org/10.1007/s10773-017-3389-4 19

    2017 doi

  31. [39]

    Efficient Constructions for Simulating Multi Controlled Quantum Gates,

    S. Balauca and A. Arusoaie, “Efficient Constructions for Simulating Multi Controlled Quantum Gates,” in Computational Science – ICCS 2022 , ser. Lecture Notes in Computer Science, D. Groen, C. de Mu- latier, M. Paszynski, V. V. Krzhizhanovskaya, J. J. Dongarra, and P. M. A. Sl...

    2022

  32. [40]

    Reversible Circuit Optimization via Leaving the Boolean Domain,

    D. Maslov and M. Saeedi, “Reversible Circuit Optimization via Leaving the Boolean Domain,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 6, pp. 806–816, Jun. 2011, arXiv:1103.0215 [quant-ph]. [Online]. Available: http://arxiv.org/a...

    2011 arXiv

  33. [41]

    Improved NCV Gate Realization of Arbitrary Size Toffoli Gates,

    A. Kole and K. Datta, “Improved NCV Gate Realization of Arbitrary Size Toffoli Gates,” in 2017 30th International Conference on VLSI Design and 2017 16th International Conference on Embedded Systems (VLSID) , Jan. 2017, pp. 289–294, iSSN: 2380-6923. [Online]. Available: https:...

    2017

  34. [42]

    NCV realization of MCT gates with mixed controls,

    Z. Sasanian and D. M. Miller, “NCV realization of MCT gates with mixed controls,” in Proceedings of 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing , Aug. 2011, pp. 567–571, iSSN: 2154-5952. [Online]. Available: https: //ieeexplore.ieee.org/...

    2011

  35. [43]

    Improving the Realization of Multiple-Control Toffoli Gates Using the NCVW Quantum Gate Library,

    L. Biswal, C. Bandyopadhyay, R. Wille, R. Drechsler, and H. Rahaman, “Improving the Realization of Multiple-Control Toffoli Gates Using the NCVW Quantum Gate Library,” in 2016 29th International Conference on VLSI Design and 2016 15th International Conference on Embedded Syste...

    2016

  36. [44]

    Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques,

    M. B. Ali, T. Hirayama, K. Yamanaka, and Y. Nishitani, “Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques,” in 2015 International Conference on Computational Science and Computational Intelligence (CSCI) , Dec. 2015, pp. 59–64. [Online]. ...

    2015

  37. [45]

    T-depth Optimization for Fault-Tolerant Quantum Circuits,

    P. Niemann, A. Gupta, and R. Drechsler, “T-depth Optimization for Fault-Tolerant Quantum Circuits,” in 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL) , May 2019, pp. 108–113, iSSN: 2378-2226. [Online]. Available: https://ieeexplore.ieee.org/document/87...

    2019

  38. [46]

    Decomposing -Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla,

    J. Leng, F. Yang, and X.-B. Wang, “Decomposing -Qubit Toffoli Gate with Shallow Circuit Depth and No Ancilla,” Advanced Quantum Technologies , vol. 7, no. 2, p. 2300370, 2024. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/qute.202300370

    2024 doi

  39. [47]

    Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits,

    N. Abdessaied, M. Amy, M. Soeken, and R. Drechsler, “Technology Mapping of Reversible Circuits to Clifford+T Quantum Circuits,” in 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL) , May 2016, pp. 150–155, iSSN: 2378-2226. [Online]. Available: https://iee...

    2016

  40. [48]

    Rise of conditionally clean ancillae for optimizing quantum circuits,

    T. Khattar and C. Gidney, “Rise of conditionally clean ancillae for optimizing quantum circuits,” Jul. 2024, arXiv:2407.17966 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2407.17966

    2024 arXiv

  41. [49]

    Implementing multi-controlled X gates using the quantum Fourier transform,

    V. V. Arsoski, “Implementing multi-controlled X gates using the quantum Fourier transform,” Quantum Information Processing , vol. 23, no. 9, p. 305, Aug. 2024. [Online]. Available: https://doi.org/10.1007/s11128-024-04511-w

    2024 doi

  42. [50]

    Multi-controlled single-qubit unitary gates based on the quantum Fourier transform and deep decomposition,

    ——, “Multi-controlled single-qubit unitary gates based on the quantum Fourier transform and deep decomposition,” Feb. 2025, arXiv:2408.00935 [quant-ph]. [Online]. Available: http: //arxiv.org/abs/2408.00935 20

    2025 arXiv

  43. [51]

    Mapping from multiple-control Toffoli circuits to linear nearest neighbor quantum circuits,

    X. Cheng, Z. Guan, and W. Ding, “Mapping from multiple-control Toffoli circuits to linear nearest neighbor quantum circuits,” Quantum Information Processing , vol. 17, no. 7, p. 169, May 2018. [Online]. Available: https://doi.org/10.1007/s11128-018-1908-8

    2018 doi

  44. [52]

    Nearest Neighbour based Synthesis of Quantum Boolean Circuits,

    A. Chakrabarti and S. Sur, “Nearest Neighbour based Synthesis of Quantum Boolean Circuits,” Engineering Letters, 2007. [Online]. Available: https://www.engineeringletters.com/issues v15/issue 2/ EL 15 2 26.pdf

    2007

  45. [53]

    Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates,

    D. M. Miller, R. Wille, and Z. Sasanian, “Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates,” in 2011 41st IEEE International Symposium on Multiple-Valued Logic , May 2011, pp. 288–293, iSSN: 2378-2226. [Online]. Available: https://ieeexplore.ieee.org/doc...

    2011

  46. [54]

    Quantum circuit compilation for nearest-neighbor architecture based on reinforcement learning,

    Y. Li, W. Liu, M. Li, and Y. Li, “Quantum circuit compilation for nearest-neighbor architecture based on reinforcement learning,” Quantum Information Processing, vol. 22, no. 8, p. 295, Jul. 2023. [Online]. Available: https://doi.org/10.1007/s11128-023-04050-w

    2023 doi

  47. [55]

    Multi-strategy based quantum cost reduction of linear nearest-neighbor quantum circuit,

    Y.-y. Tan, X.-y. Cheng, Z.-j. Guan, Y. Liu, and H. Ma, “Multi-strategy based quantum cost reduction of linear nearest-neighbor quantum circuit,” Quantum Information Processing , vol. 17, no. 3, p. 61, Jan. 2018. [Online]. Available: https://doi.org/10.1007/s11128-018-1832-y

    2018 doi

  48. [56]

    Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,

    D. Maslov, “Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,” Physical Review A , vol. 93, no. 2, p. 022311, Feb. 2016, publisher: American Physical Society. [Online]. Available: https://link.aps.org/doi/10.1103/Phy...

    2016 doi

  49. [57]

    Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-Phase Toffoli Gates,

    K. Oonishi, T. Tanaka, S. Uno, T. Satoh, R. Van Meter, and N. Kunihiro, “Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-Phase Toffoli Gates,” IEEE Transactions on Quantum Engineering , vol. 3, pp. 1–18, 2022. [Online]. Available: ht...

    2022

  50. [58]

    Optimization of Quantum Boolean Circuits by Relative-Phase Toffoli Gates,

    S. Kuroda and S. Yamashita, “Optimization of Quantum Boolean Circuits by Relative-Phase Toffoli Gates,” in Reversible Computation, C. A. Mezzina and K. Podlaski, Eds. Cham: Springer International Publishing, 2022, pp. 20–27

    2022

  51. [59]

    Quantum circuits of T -depth one,

    P. Selinger, “Quantum circuits of T -depth one,” Physical Review A , vol. 87, no. 4, p. 042302, Apr

  52. [60]

    All You Need is pi: Quantum Computing with Hermitian Gates,

    B. Zindorf and S. Bose, “All You Need is pi: Quantum Computing with Hermitian Gates,” Feb. 2025, arXiv:2402.12356 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2402.12356

    2025

  53. [61]

    Quantum Computation and Quantum Informa- tion: 10th Anniversary Edition,

    M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Informa- tion: 10th Anniversary Edition,” Dec. 2010, iSBN: 9780511976667 Publisher: Cam- bridge University Press. [Online]. Available: https://www.cambridge.org/highereducation/books/ quantum-computation-and-quan...

    2010

  54. [62]

    Efficient quantum computing between remote qubits in linear nearest neighbor architectures,

    P. Kumar, “Efficient quantum computing between remote qubits in linear nearest neighbor architectures,” Quantum Information Processing , vol. 12, no. 4, pp. 1737–1757, Apr. 2013. [Online]. Available: https://doi.org/10.1007/s11128-012-0485-5

    2013 doi

  55. [63]

    Depth Optimization of CZ, CNOT, and Clifford Circuits,

    D. Maslov and B. Zindorf, “Depth Optimization of CZ, CNOT, and Clifford Circuits,” IEEE Transactions on Quantum Engineering, vol. 3, pp. 1–8, 2022, conference Name: IEEE Transactions on Quantum Engineering. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/9792395

    2022

  56. [64]

    Computation at a distance,

    S. A. Kutin, D. P. Moulton, and L. M. Smithline, “Computation at a distance,” Jan. 2007, arXiv:quant-ph/0701194. [Online]. Available: http://arxiv.org/abs/quant-ph/0701194 21

    2007 arXiv

  57. [65]

    Efficient variational synthesis of quantum circuits with coherent multi-start optimization,

    N. A. Nemkov, E. O. Kiktenko, I. A. Luchnikov, and A. K. Fedorov, “Efficient variational synthesis of quantum circuits with coherent multi-start optimization,” Quantum, vol. 7, p. 993, May 2023. [Online]. Available: https://quantum-journal.org/papers/q-2023-05-04-993/

    2023

  58. [66]

    Benchmarking 16-element quantum search algorithms on superconducting quantum processors,

    J. Gwinner, M. Bria´ nski, W. Burkot, L. Czerwi´ nski, and V. Hlembotskyi, “Benchmarking 16-element quantum search algorithms on superconducting quantum processors,” Jan. 2021, arXiv:2007.06539 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2007.06539

    2021 arXiv

  59. [67]

    Quantum-gate decomposer,

    K. M. Nakanishi, T. Satoh, and S. Todo, “Quantum-gate decomposer,” Sep. 2021, arXiv:2109.13223 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2109.13223

    2021 arXiv

  60. [68]

    Decompositions of multiple controlled- Z gates on various qubit-coupling graphs,

    ——, “Decompositions of multiple controlled- Z gates on various qubit-coupling graphs,” Physical Review A , vol. 110, no. 1, p. 012604, Jul. 2024. [Online]. Available: https: //link.aps.org/doi/10.1103/PhysRevA.110.012604

    2024 doi

  61. [69]

    Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging,

    P. M. Q. Cruz and B. Murta, “Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging,” May 2023, arXiv:2305.18128 [quant-ph]. [Online]. Available: http://arxiv.org/abs/2305.18128 Appendix A Constant reductions Whi...

    2023 arXiv

  62. [71]

    Define the orientation of the leftmost Toffoli of each set accordingly

    Choose αd, and set αi = 1 for any i < d. Define the orientation of the leftmost Toffoli of each set accordingly

  63. [72]

    A Toffoli, without a defined orientation, located to the right of a Toffoli with a defined orientation will have the opposite orientation

  64. [73]

    We are looking for the depth reduction obtained for any scenario

    Each CNOT gate which is applied directly to the right of an upwards Toffoli is replaced with a SW AP gate. We are looking for the depth reduction obtained for any scenario. We define Di(ni) = (DCX i (ni), DT i (ni), DH i (ni)) to hold the depth reduction of each gate type, ach...

  65. [2013]

    Available: https://link.aps.org/doi/10.1103/PhysRevA.87.042302

    [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.87.042302

    doi

Pith tools

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