betaFeedback

WorksPhysics and Astronomy

Exact quantum Hamming-weight computation at optimal depth and minimum width

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 nn-qubit register with depth O(log⁡n)O(\log n) and size O(nlog⁡n)O(n\log n), using only the nn input qubits and m=⌈log⁡2(n+1)⌉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 mm ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even nn. With only O(log⁡n)O(\log n) ancillary qubits, we obtain expected depth O(log⁡2n)O(\log^2 n) using measurements and classical feedforward, and depth O(n1/4log⁡n)O(n^{1/4}\log n) using unitary gates alone.

Paper details

vlnc:W_yqvmttc6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…