RECORD
Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
Quantum Physics · Submitted 10 Apr 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim For an $n$-qubit input, the depth-optimal algorithm uses $O(n)$ control qubits and the corresponding circuit has depth $O(\log (n))$, assuming that we have the ability to perform qubit resets.
The compiled record
The paper's own sentences, arranged. 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.
Open the compiled record
The abstract, sentence by sentence
A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H} = (\mathbb{C}_2)^{\otimes n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an $n$-qubit input, the depth-optimal algorithm uses $O(n)$ control qubits and the corresponding circuit has depth $O(\log (n))$, assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Given a Hilbert space of the form $\mathcal{H} = (\mathbb{C}_2)^{\otimes n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. | background 1.00 | 0.08 | 0.03 | asserted 1.00 |
| s2 | In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. | contribution 1.00 | 0.90 | 0.33 | asserted 0.98 |
| s3 | We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. | contribution 0.80 | 0.88 | 0.12 | asserted 0.87 |
| s4 | For an $n$-qubit input, the depth-optimal algorithm uses $O(n)$ control qubits and the corresponding circuit has depth $O(\log (n))$, assuming that we have the ability to perform qubit resets. | result 0.99 | 0.90 | 0.56 | asserted 0.99 |
| s5 | Furthermore, the proposed algorithm construction uses only one- and two-qubit gates. | method 0.65 | 0.87 | 0.07 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H} = (\mathbb{C}_2)^{\otimes n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an $n$-qubit input, the depth-optimal algorithm uses $O(n)$ control qubits and the corresponding circuit has depth $O(\log (n))$, assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.
Human review
References
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as background 1 paper
-
Related Hamming-weight primitives appear, for example, in Hamming-weight phasing for fault-tolerant simulation [ref] and in logarithmic-depth circuits for Hamming-weight projections [ref] .
Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions · Basic Hamming Weight Primitives · 0.93
What it cites · 3 sentences without a confident label
Uses the method or tool of 1 paper
-
We now define the semi-classical encoded IQFT, making use of original insights from [ref] (see also [ref] for a visual depiction).
Pretending to factor large numbers on a quantum computer · Depth-Width Tradeoff and 2D Architecture Implementation · 0.83
Compares with 2 papers
-
Note on independent work—While finalizing our paper, we came across the concurrent and independent works [ref] , which also provide shallow-depth circuits for computing Hamming weight coherently.
Approximating many-body quantum states with quantum circuits and measurements · Introduction · 0.97
-
Note on independent work—While finalizing our paper, we came across the concurrent and independent works [ref] , which also provide shallow-depth circuits for computing Hamming weight coherently.
Shallow Quantum Circuit Implementation of Symmetric Functions with Limited Ancillary Qubits · Introduction · 0.97
Cites as background 2 papers
-
Multiple classes of problems have now been shown to have quantum algorithms solving them faster than the current fastest classical algorithms [ref] .
Quantum algorithms: A survey of applications and end-to-end complexities · Introduction · 0.97
-
The Hamming weight of a string is a relevant quantity in multiple different fields such as cryptography [ref] , error correction [ref] , and information theory [ref] .
Subfield Codes of Several Few-Weight Linear Codes Parametrized by Functions and Their Consequences · Introduction · 0.87
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.