Pith. sign in

REVIEW 5 minor 43 references

Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions

T0 review · 0 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper establishes depth–ancilla tradeoffs for quantum Hamming weight computation: logarithmic depth with sublinear ancillas under all-to-all connectivity, optimal square-root depth on a 2D grid, and constant depth in dynamic models…

desk verdict The stress-test's core objection is wrong: the redundant phase states are orthonormal, so Lemma 4.12 is not impossible; the standard-model results are clean and new, and the dynamic constructions are credible but deserve tighter layout analysis. read the letter →

arxiv 2608.04627 v1 pith:5MW575AJ submitted 2026-08-05 quant-ph

Wei Zi , Pei Yuan , Junhong Nie , Shengyu Zhang This is my paper · ORCID
classification quant-ph MSC 68Q1281P68 PACS 03.67.Lx
keywords HammingweightcomputationsymmetricBooleanfunctionsdepth-ancillatradeoffdynamicquantumcircuits2Dnearest-neighborarchitecturemeasurement-basedfan-outconstant-depth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how shallow a quantum circuit can be while still exactly computing the Hamming weight of an n-bit string, and how many ancilla qubits that costs under different hardware connectivities. It establishes that in the standard all-to-all model the task can be done in $O(\log n)$ depth with $o(n)$ ancillas, and that on a two-dimensional nearest-neighbor grid the optimal depth is $\Theta(\sqrt n)$, attainable with only $O(\log^2 n)$ ancillas. In the dynamic circuit model, where mid-circuit measurements and classical feedforward are allowed, the paper claims constant-depth implementations with $O(n^{1+\varepsilon}\operatorname{polylog} n)$ ancillas for every fixed $\varepsilon>0$, in both connectivity models. Because any symmetric Boolean function reduces to computing the Hamming weight and then evaluating a function of that weight, all of these bounds transfer to symmetric functions such as OR, AND, majority, threshold, and parity.

What carries the argument

The load-bearing reduction is block decomposition into weighted counting: partition the input into blocks of size $B$, compute each local Hamming weight $w_\ell$, write $w_\ell=\sum_j 2^j b_{\ell,j}$, and reduce the global weight to $\sum_{\ell,j} 2^j b_{\ell,j}$. The standard-model constructions implement local weights with the ancilla-free Fourier phase encoding of [40] and finish the weighted sum with carry-save population counting; the 2D version replaces each phase interaction by a multi-output phase gadget built from dirty fan-out along trees and a cyclic token tour around a corridor, so that one control qubit visits every data qubit exactly once. The dynamic constructions use measurement-based fan-out [2] to build cat states—equal superpositions of all zeros and all ones on the leaf qubits—and weighted controlled-phase gates to accumulate $S=\sum_i a_i z_i$ in branch-specific phase states $|\phi_{k,y}(S)\rangle$, followed by a constant-depth Takahashi–Tani parallel decoder to extract the binary value $|S\rangle$. The matching lower bound is the parity light cone: in depth $d$ on a 2D grid, the least significant output bit can depend on at most $O(d^2)$ inputs, and since it equals $x_1\oplus\cdots\oplus x_n$, $d=\Omega(\sqrt n)$.

What would settle it

To test the 2D optimality claim, look for a measurement-free nearest-neighbor circuit on a square grid of depth $o(\sqrt n)$ that computes the parity of all $n$ input bits; since parity is the least significant output bit of Hamming weight, any such circuit falsifies the matching lower bound. For the dynamic clean-subroutine claim, simulate the full compute–copy–uncompute cycle of the $n=4$ dynamic 2D construction on all 16 inputs and check that every ancillary qubit returns to $|0\rangle$ and the output is exactly $|x|\rangle$; any dependence on measurement outcomes in the restored registers would falsify the cleanup argument.

Watch

Extended reading notes

Core claim

The central discovery is that Hamming weight computation is governed by a simple reduction—block the input, compute local weights, then sum a weighted set of bits—and that each circuit model supplies a different optimal way to carry out the two stages. In the standard all-to-all model, blocking the ancilla-free Fourier-encoding construction of [40] and summing local weights with a carry-save adder yields depth $O(\log n)$ with sublinear ancillas. In the standard 2D model, the same Fourier encoding is localized by multi-output phase gadgets routed around grid patches, giving depth $O(\sqrt n)$ with $O(\log^2 n)$ ancillas; the paper proves this depth is optimal because the least significant output bit is the XOR of all $n$ inputs, so its backward light cone on a 2D grid must have radius $\Omega(\sqrt n)$. In both dynamic models, measurement-based fan-out prepares redundant Fourier phase states for the weighted sum, a constant-depth parallel decoder writes out the binary answer, and an $r$-level pyramid of such steps achieves depth $O(r)$ with $O(r n^{1+1/r}\operatorname{polylog} n)$ ancillas, giving constant depth with near-linear ancillas for fixed $\varepsilon>0$. The paper claims the same tradeoffs for arbitrary symmetric Boolean oracles by computing $|x|$, evaluating the outer function on the weight register, and uncomputing.

Load-bearing premise

The constant-depth dynamic results depend on being able to undo every measurement-based primitive after its output has been copied, so that all phase and workspace registers return exactly to their initial states; a decoder or fan-out gadget that can only be run destructively would break the cleanup step and require a different construction.

Editorial extensions

If this is right

  • On a measurement-free 2D nearest-neighbor chip, Hamming weight computation cannot be made faster than $\Theta(\sqrt n)$ depth, so the $O(\sqrt n)$ construction is optimal up to constants.
  • Allowing mid-circuit measurements and classical feedforward removes the square-root barrier even when two-qubit gates remain nearest-neighbor: constant-depth Hamming weight circuits exist with $O(n^{1+\varepsilon}\operatorname{polylog} n)$ ancillas for every fixed $\varepsilon>0$.
  • The $r$-level pyramid gives a smooth depth–ancilla tradeoff: depth $O(r)$ with $O(r n^{1+1/r}\operatorname{polylog} n)$ ancillas, interpolating between the low-ancilla and low-depth regimes.
  • Every symmetric Boolean function oracle—majority, threshold, AND, OR, parity—inherits the same four bounds by composing Hamming weight computation with a small Boolean evaluation on the weight register.
  • In the standard all-to-all model, symmetric Boolean functions gain a logarithmic-depth construction with sublinear ancillas, improving on earlier $O(\log^2 n)$-depth constructions.

Reading between the lines

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

  • A natural next step, suggested by the paper's own open problems, is to convert the dynamic primitives into fault-tolerant circuits and count non-Clifford resources; mid-circuit measurement may reduce $T$-depth as sharply as it reduces ordinary depth, but that is not shown here.
  • The same block-and-weighted-count decomposition could be applied to other additive aggregates, such as weighted sums, inner products, or low-degree polynomials, giving analogous depth–ancilla tradeoffs in these four models.
  • If the dynamic decoder turns out to be destructive rather than reversible, the constant-depth cleanup step would need a measurement-based reset with classical corrections; the paper does not supply that repair.
  • The 2D parity light-cone argument extends to any symmetric function whose value depends on all $n$ inputs, not just parity; the paper states the lower bound for Hamming weight, but the same counting applies to AND, majority, or threshold oracles.
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

0 major / 5 minor

Summary. This paper studies depth-ancilla tradeoffs for Hamming weight computation and symmetric Boolean functions under all-to-all and two-dimensional nearest-neighbor square-grid connectivity, in both the standard and dynamic circuit models. The main results are: in the standard all-to-all model, depth O(log n) with sublinear ancillas; in the standard 2D model, depth O(√n) with O(log^2 n) ancillas and a matching Ω(√n) lower bound; in both dynamic models, constant depth with O(n^{1+ε} polylog n) ancillas for every fixed ε>0, with smooth depth-ancilla tradeoffs and extension to arbitrary symmetric Boolean functions. The constructions are based on blocking, Fourier phase encoding, carry-save summation, measurement-based fan-out, and the Takahashi–Tani decoder.

Significance. If correct, the results are significant: the standard 2D construction is depth-optimal with only polylogarithmic ancillas, and the dynamic results show that mid-circuit measurement and feedforward remove the 2D square-root depth barrier at near-linear ancillary cost. The paper is careful with clean-ancilla accounting, gives explicit layouts for the 2D constructions, and cites external primitives transparently. I also verified the specific concern raised in the review about Lemma 4.12: the states |Φ_R(t)> are not non-orthogonal; for distinct t and t′, the inner product vanishes at k=ν₂(t−t′), so a unitary clean decoder is not ruled out by linearity. The remaining issues are presentation-level and local.

minor comments (5)
  1. [Lemma 4.12] The proof states that a candidate qubit t^y_k is 'extracted' after phase correction, but it does not define the extraction gate or prove that it preserves the phase state; please specify the operation (for example, after correcting to |+⟩/|−⟩, apply H-CNOT-H) and state explicitly that it is unitary and is undone in the clean reversal.
  2. [Lemma 3.3] The sentence 'If temporary registers are produced, we use the standard compute–copy–uncompute procedure' assumes the Takahashi–Tani decoder is reversible on the phase encoding; this is the same property later proved in Lemma 4.12, so please add a cross-reference or a one-sentence justification here.
  3. [Lemma 4.12] It would help to state that the redundant phase states are mutually orthogonal for distinct t (the inner product vanishes at k=ν₂(t−t′)), which is what makes the clean isometry |Φ_R(t)>|0^q⟩ → |Φ_R(t)>|t⟩ possible.
  4. [Theorem 4.17] The proof ignores integer roundings in block sizes; this is standard, but a footnote saying that replacing sizes by ceilings changes only constant factors would improve readability.
  5. [Theorem 5.7] In the constant-bit splitting, please spell out why 2^{m−c+1} ≤ n for a fixed sufficiently large c; this is used to ensure that the borrowed workspace fits in the input register.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new tradeoffs reduce to independent published primitives and standard light-cone arguments, with no fitted parameter renamed as a prediction.

full rationale

The derivation chain is not circular. The standard all-to-all block construction (Theorem 3.1) combines the published ancilla-free Fourier encoding of Ref. [40], a same-group article but an external, parameter-free, falsifiable construction, with the standard carry-save summation of Ref. [10]; the claimed depth-ancilla tradeoff follows from choosing the block size B, not from assuming the tradeoff. The dynamic all-to-all and dynamic 2D results build on the Takahashi-Tani decoder [35] and measurement-based fan-out [2], and the recursive pyramids (Theorems 3.6 and 4.17) are direct parallel compositions of the same weighted-counting primitive; no free parameter is fitted to a target output. The standard 2D upper bound is obtained by localizing the Ref. [40] phase gadget on a grid (Lemmas 4.3-4.7), and the matching Omega(sqrt(n)) lower bound is the independent parity light-cone argument [27,33]. The same-group citations are [39] (leaf recovery after measurement-based fan-out, an elementary Pauli-correction fact) and [40]; neither assumes the present theorems as inputs. A possible concern that Lemma 4.12's clean decoder cannot preserve the redundant phase encoding while writing |t> is not a circularity, and the linearity obstruction in fact fails: for d = t - t' != 0 with k = v_2(d), the branch factor (1 + e^{2 pi i d / 2^{k+1}})/2 vanishes, so the states |Phi_R(t)> are orthogonal and compute-copy-uncompute reversal is not ruled out by unitarity. Overall there is no circular step, no fitted input called a prediction, and no ansatz smuggled in through self-citation.

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

The paper introduces no fitted parameters and no new physical entities. It depends on several external circuit-construction results, including two by the same authors ([40]). The most fragile internal premise is the reversibility of the Takahashi-Tani decoder, which is asserted in Lemma 4.12 but does not hold for non-orthogonal phase states.

assumptions (6)
  • domain assumption Ancilla-free Hamming weight computation in the standard all-to-all model with depth O(log^2 n) and no ancillas (Lemma 2.4, from Ref. [40])
    Used as a black box for local weight computations in Theorem 3.1 and Lemma 4.7. It is a published result by the same authors, cited as external support.
  • domain assumption Carry-save Hamming weight computation with depth O(log n) and O(n) ancillas (Lemma 2.5, from Ref. [10])
    Used to sum local weights in Theorem 3.1 and Theorem 4.8.
  • domain assumption Takahashi-Tani constant-depth Hamming weight in the dynamic model with O(n^2) ancillas (Lemma 2.6, Ref. [35])
    Used as a local weight computation in Theorem 3.4 and Theorem 4.14, and as the basis for the decoder in the weighted-counting primitive.
  • domain assumption Constant-depth fan-out with O(r) ancillas on 1D nearest-neighbor dynamic circuits (Lemma 2.3, Ref. [2])
    Used throughout the dynamic constructions to implement long-range CNOTs and cat states.
  • domain assumption Nonlocal classical feedforward is free in the dynamic circuit model
    The constant-depth dynamic 2D results rely on classical information being routable without quantum cost; if feedforward were local, the square-root barrier would likely return.
  • standard math Two-dimensional light-cone lower bound for parity (Refs. [27,33])
    Used to prove the Ω(√n) lower bound in Theorem 4.8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions." pith.science (2026). https://pith.science/paper/5MW575AJ

@misc{pith2026260804627,
  author       = {Pith},
  title        = {Pith review of: Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5MW575AJ}},
  note         = {Machine review of arXiv:2608.04627}
}
abstract

Hamming weight computation maps an $n$-bit input to the number of ones it contains. It is a basic subroutine in quantum computing, and the core building block for symmetric Boolean functions, whose value depends only on the Hamming weight of the input. Moreover, symmetric Boolean functions are among the most common primitives in quantum computing. Efficient circuits for both problems are therefore important for the efficiency of many quantum algorithms. We study the depth-ancilla tradeoffs of Hamming weight computation under two qubit connectivity models, all-to-all and two-dimensional nearest-neighbor square grid (2D), in both the standard and dynamic circuit models. In the standard all-to-all model, we obtain depth $O(\log n)$ with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth $O(\sqrt n)$ with $O(\log^2 n)$ ancillas, and a matching lower bound showing that $\Theta(\sqrt n)$ is optimal. In both dynamic models, we obtain constant-depth circuits with $O(n^{1+\varepsilon}\operatorname{polylog}\,n)$ ancillary qubits for every fixed $\varepsilon>0$. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.

Figures

Figures reproduced from arXiv: 2608.04627 by the authors.

Figure 1
Figure 1. Overview of the constructions. Panel (a) shows the blocked reduction from Hamming weight [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Weighted phase preparation for one branch [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. One elementary step of the cyclic-tour schedule for [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Layout for the multi-output phase gadget. The large patch is partitioned into [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Two-dimensional weighted phase preparation. Panel (a) shows the [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: Schematic layout for Theorem 4.15. The two-dimensional grid contains L = ⌈n/B⌉ disjoint local block patches and one global weighted-counting patch. Each local patch computes a block Hamming weight, and the corresponding bits bℓ,j are copied by constant-depth dynamic lo…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 19 canonical work pages

  1. [40]

    Wei Zi, Junhong Nie, and Xiaoming Sun. Shallow quantum circuit implementa- tion of symmetric functions with limited ancillary qubits.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 44(8):3060–3072, 2025. DOI: 10.1109/TCAD.2025.3539002. 38

    work page arXiv 2025

  2. [1]

    Quantum supremacy using a programmable superconducting processor.Nature, 574(7779):505–510, 2019

    Frank Arute, Kunal Arya, Ryan Babbush, et al. Quantum supremacy using a programmable superconducting processor.Nature, 574(7779):505–510, 2019. DOI: 10.1038/s41586-019-1666-5

    doi:10.1038/s41586-019-1666-5 2019

  3. [2]

    Measurement-based long-range entangling gates 35 in constant depth.Physical Review Research, 7(2):023120, 2025

    Elisa Bäumer and Stefan Woerner. Measurement-based long-range entangling gates 35 in constant depth.Physical Review Research, 7(2):023120, 2025. DOI: 10.1103/Phys- RevResearch.7.023120

    doi:10.1103/phys- 2025

  4. [3]

    Efficient quantum implementation of majority-based full adder circuit using clifford+t-group

    Laxmidhar Biswal, Bappaditya Mondal, Anindita Chakraborty, and Hafizur Ra- haman. Efficient quantum implementation of majority-based full adder circuit using clifford+t-group. InArtificial Intelligence Driven Circuits and Systems, pages 53–63, Singapore, 2022. Springer Singapore. DOI: 10.1007/978-981-16-6940-8_5

    work page doi:10.1007/978-981-16-6940-8_5 2022

  5. [4]

    Quantum counting

    Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum counting. InInternational colloquium on automata, languages, and programming, pages 820–831. Springer, 1998. DOI: 10.1007/BFb0055105

    work page doi:10.1007/bfb0055105 1998

  6. [5]

    Harry Buhrman, Marten Folkertsma, Bruno Loff, and Niels M. P. Neumann. State preparation by shallow circuits using feed forward.Quantum, 8:1552, December 2024. ISSN 2521-327X. DOI: 10.22331/q-2024-12-09-1552

    doi:10.22331/q-2024-12-09-1552 2024

  7. [6]

    Low-quantum cost circuit construc- tions for adder and symmetric boolean functions

    Anupam Chattopadhyay and Anubhab Baksi. Low-quantum cost circuit construc- tions for adder and symmetric boolean functions. In2016 IEEE International Sym- posium on Circuits and Systems (ISCAS), pages 2294–2297, 2016. DOI: 10.1109/IS- CAS.2016.7539042

    arXiv 2016

  8. [7]

    Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics

    András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singu- lar value transformation and beyond: exponential improvements for quantum matrix arithmetics. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. DOI: 1...

    arXiv 2019

Show all 43 references
  1. [8]

    Quantum error correction below the surface code threshold.Nature, 638(8052):920–926, February 2025

    Google Quantum AI and Collaborators. Quantum error correction below the surface code threshold.Nature, 638(8052):920–926, February 2025. ISSN 1476-4687. DOI: 10.1038/s41586-024-08449-y

    2025 doi

  2. [9]

    Quantum state preparation with opti- mal T-count

    David Gosset, Robin Kothari, and Kewen Wu. Quantum state preparation with opti- mal T-count. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3378–3406, 2026. DOI: 10.1137/1.9781611978971.122

    2026 doi

  3. [10]

    Quantum carry-save arithmetic, 1998

    Phil Gossett. Quantum carry-save arithmetic, 1998. URLhttps://arxiv.org/abs/ quant-ph/9808061

    1998 arXiv

  4. [11]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Comput- ing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Com- puting Machinery. ISBN 0897917855. DOI: 10.1145/2378...

    1996

  5. [12]

    Quantum fan-out is powerful.Theory of Computing, 1(5):81–103, 2005

    Peter Høyer and Robert Špalek. Quantum fan-out is powerful.Theory of Computing, 1(5):81–103, 2005. DOI: 10.4086/toc.2005.v001a005

    2005 doi

  6. [13]

    Krishnageetha Karuppasamy, Varun Puram, Stevens Johnson, and Johnson P. Thomas. A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions.Quantum Rep., 7(1):2, 2025. DOI: 10.3390/quantum7010002

    2025 doi

  7. [14]

    Mendes, and Andriy Miran- skyy

    Mushahid Khan, Jean Paul Latyr Faye, Udson C. Mendes, and Andriy Miran- skyy. Ep-pqm: Efficient parametric probabilistic quantum memory with fewer qubits and gates.IEEE Transactions on Quantum Engineering, 3:1–15, 2022. DOI: 10.1109/TQE.2022.3169987

    2022

  8. [15]

    Evidence for the utility of quantum computing before fault tolerance.Nature, 618 (7965):500–505, 2023

    YoungseokKim, AndrewEddins, SajantAnand, KenXuanWei, EwoutVanDenBerg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, et al. Evidence for the utility of quantum computing before fault tolerance.Nature, 618 (7965):500–505, 2023. DOI: 10.1038/s41586-023-06096-3

    2023 doi

  9. [16]

    Kivlichan, Craig Gidney, Dominic W

    Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut 36 Neven, and Ryan Babbush. Improved fault-tolerant quantum simulation of condensed- phase correlated electrons via t...

    2020 doi

  10. [17]

    Saeed, and Muharrem Umit Uyar

    Janusz Kusyk, Samah M. Saeed, and Muharrem Umit Uyar. Survey on quantum circuit compilation for noisy intermediate-scale quantum computers: Artificial intelli- gence to heuristics.IEEE Transactions on Quantum Engineering, 2:1–16, 2021. DOI: 10.1109/TQE.2021.3068355

    2021

  11. [18]

    Thomson Leighton, Fillia Makedon, and Ioannis G

    F. Thomson Leighton, Fillia Makedon, and Ioannis G. Tollis. A2n−2step algorithm for routing in ann×narray with constant-size queues.Algorithmica, 14(4):291–304,

  12. [19]

    Quantum k-nearest neighbor classifica- tion algorithm based on hamming distance.Quantum Information Processing, 21(1): 18, 2022

    Jing Li, Song Lin, Kai Yu, and Gongde Guo. Quantum k-nearest neighbor classifica- tion algorithm based on hamming distance.Quantum Information Processing, 21(1): 18, 2022. DOI: 10.1007/s11128-021-03361-0

    2022 doi

  13. [20]

    Quantum k-fold cross-validation for nearest neighbor classification algorithm.Physica A: Statistical Mechanics and its Applications, 611:128435, 2023

    Jing Li, Fei Gao, Song Lin, Mingchao Guo, Yongmei Li, Hailing Liu, Sujuan Qin, and QiaoYan Wen. Quantum k-fold cross-validation for nearest neighbor classification algorithm.Physica A: Statistical Mechanics and its Applications, 611:128435, 2023. ISSN 0378-4371. DOI: 10.1016/j...

    2023

  14. [21]

    Block encoding with low gate count for second-quantized hamiltonians, 2025

    Diyi Liu, Shuchen Zhu, Guang Hao Low, Lin Lin, and Chao Yang. Block encoding with low gate count for second-quantized hamiltonians, 2025. URLhttps://arxiv. org/abs/2510.08644

    2025

  15. [22]

    Trading T gates for dirty qubits in state preparation and unitary synthesis.Quantum, 8:1375, June 2024

    Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis.Quantum, 8:1375, June 2024. ISSN 2521-327X. DOI: 10.22331/q-2024-06-17-1375. URLhttps://doi.org/10.22331/ q-2024-06-17-1375

    2024 doi

  16. [23]

    Efficient reversible and quantum implementations of symmetric boolean functions.IEE Proceedings-Circuits, Devices and Systems, 153(5):467–472,

    Dmitri Maslov. Efficient reversible and quantum implementations of symmetric boolean functions.IEE Proceedings-Circuits, Devices and Systems, 153(5):467–472,

  17. [24]

    Quantum advantage for computations with limited space.Nature Physics, 17(8):894– 897, 2021

    Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder, and Sarah Sheldon. Quantum advantage for computations with limited space.Nature Physics, 17(8):894– 897, 2021. DOI: 10.1038/s41567-021-01271-7

    2021 doi

  18. [25]

    Dmitri A. Maslov. Dynamic programming algorithms as quantum circuits: symmetric function realization. InQuantum Information and Computation II, volume 5436 of Proceedings of SPIE, pages 386–393, 2004. DOI: 10.1117/12.541792

    2004 doi

  19. [26]

    Quantum circuits: Fanout, parity, and counting, 1999

    Cristopher Moore. Quantum circuits: Fanout, parity, and counting, 1999. URL https://arxiv.org/abs/quant-ph/9903046

    1999 arXiv

  20. [27]

    Parallel quantum computation and quantum codes.SIAM Journal on Computing, 31(3):799–815, 2001

    Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes.SIAM Journal on Computing, 31(3):799–815, 2001. DOI: 10.1137/S0097539799355053

    2001 doi

  21. [28]

    A quantum algorithm for string matching.npj Quantum Information, 7(1):37, 2021

    Pradeep Niroula and Yunseong Nam. A quantum algorithm for string matching.npj Quantum Information, 7(1):37, 2021. DOI: 10.1038/s41534-021-00369-3

    2021 doi

  22. [29]

    Quantum circuits for computing hamming distance requiring fewer t gates.The Jour- nal of Supercomputing, 80(9):12527–12542, 2024

    Francisco Orts, Gloria Ortega, Elías F Combarro, Ignacio F Rúa, and Ester M Garzón. Quantum circuits for computing hamming distance requiring fewer t gates.The Jour- nal of Supercomputing, 80(9):12527–12542, 2024. DOI: 10.1007/s11227-024-05916-1

    2024 doi

  23. [30]

    Regular realization of symmetric functions using reversible logic

    Marek Perkowski, Pawel Kerntopf, Andrzej Buller, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Xiaoyu Song, Anas Al-Rabadi, L Jezwiak, Alan Coppola, and Bart Massey. Regular realization of symmetric functions using reversible logic. InProceed- ings Euromicro Symposium on Digi...

    2001

  24. [31]

    Regularity and symmetry as a base for efficient realization of reversible logic circuits

    Marek Perkowski, Pawel Kerntopf, Andrzej Buller, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Xiaoyu Song, Anas Al-Rabadi, Lech Jozwiak, Alan Coppola, and Bart Massey. Regularity and symmetry as a base for efficient realization of reversible logic circuits. InProceedings of ...

    2001

  25. [32]

    LaBorde, and Mark M

    Soorya Rethinasamy, Margarite L. LaBorde, and Mark M. Wilde. Logarithmic-depth quantum circuits for hamming weight projections.Physical Review A, 110(5):052401,

  26. [33]

    Rosenbaum

    David J. Rosenbaum. Optimal quantum circuits for nearest-neighbor architectures. In 8th Conference on the Theory of Quantum Computation, Communication and Cryp- tography (TQC 2013), volume 22 ofLeibniz International Proceedings in Informatics, pages 294–307, 2013. DOI: 10.4230...

    2013 doi

  27. [34]

    P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. InProceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. DOI: 10.1109/SFCS.1994.365700

    1994

  28. [35]

    Collapse of the hierarchy of constant-depth exact quantum circuits.Computational Complexity, 25(4):849–881, 2016

    Yasuhiro Takahashi and Seiichiro Tani. Collapse of the hierarchy of constant-depth exact quantum circuits.Computational Complexity, 25(4):849–881, 2016. DOI: 10.1007/s00037-016-0140-0

    2016 doi

  29. [36]

    Power of uninitialized qubits in shal- low quantum circuits.Theoretical Computer Science, 851:129–153, 2021

    Yasuhiro Takahashi and Seiichiro Tani. Power of uninitialized qubits in shal- low quantum circuits.Theoretical Computer Science, 851:129–153, 2021. DOI: 10.1016/j.tcs.2020.11.039

    2021 doi

  30. [37]

    Strong quantum computational advantage using a superconducting quantum processor.Phys

    Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, et al. Strong quantum computational advantage using a superconducting quantum processor.Phys....

    2021 doi

  31. [38]

    Quantum circuit synthesis and compilation optimization: Overview and prospects.CoRR, abs/2407.00736, 2024

    Ge Yan, Wenjie Wu, Chen Yuheng, Kaisen Pan, Xudong Lu, Zhou Zixiang, Wang Yuhan, Ruocheng Wang, and Junchi Yan. Quantum circuit synthesis and compilation optimization: Overview and prospects.CoRR, abs/2407.00736, 2024. URLhttps: //doi.org/10.48550/arXiv.2407.00736

    2024 doi

  32. [39]

    Constant-depth quantum circuits for arbitrary quantum state preparation via measurement and feedback, 2025

    Wei Zi, Junhong Nie, and Xiaoming Sun. Constant-depth quantum circuits for arbitrary quantum state preparation via measurement and feedback, 2025. URL https://arxiv.org/abs/2503.16208

    2025 arXiv

  33. [1995]

    DOI: 10.1007/BF01294128

    doi

  34. [2006]

    DOI: 10.1049/ip-cds:20045213

    doi

  35. [2024]

    DOI: 10.1103/PhysRevA.110.052401

    doi

Pith tools

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