arXiv preprint ·
Exact quantum Hamming-weight computation at optimal depth and minimum width
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Symmetry-breaking chelation enables room-temperature all-optical spin coherence readout of aqueous Cu(II) for chemoselective discrimination
Quantum State Search with Classical Interactive Advice
Chiral Floquet Selection of an Algebraic Rydberg Bound State in the Continuum
Subsystem quantum Rényi-Bhattacharyya distance in 2D CFTs and its holographic applications
Large Language Model Steering of Acousto-Optic Tweezer Arrays
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.