Optimizing the depth and number of ancillary qubits in quantum circuits is crucial in quantum computation, given the limitations imposed by current quantum devices. In this article, we introduce an innovative approach for implementing arbitrary symmetric Boolean functions using poly-logarithmic depth quantum circuits with only a logarithmic number of ancillary qubits. Symmetric functions are those whose outputs are dictated solely by the Hamming weight of the inputs. These functions find applications across various domains, including quantum machine learning and arithmetic circuit synthesis. Moreover, by fully leveraging the potential of qutrits, the ancilla count can be further reduced to just one. The key technique involves a novel poly-logarithmic depth quantum circuit designed to compute Hamming weight without the need for ancillary qubits. This quantum circuit for Hamming weight is of independent interest due to its wide-ranging applications, such as in quantum memory, quantum machine learning, and Hamiltonian dynamics simulations.
Optimizing the depth and number of ancillary qubits in quantum circuits is crucial in quantum computation, given the limitations imposed by current quantum devices. In this article, we introduce an innovative approach for implementing arbitrary symmetric Boolean functions using poly-logarithmic depth quantum circuits with only a logarithmic number of ancillary qubits. Symmetric functions are those whose outputs are dictated solely by the Hamming weight of the inputs. These functions find applications across various domains, including quantum machine learning and arithmetic circuit synthesis. Moreover, by fully leveraging the potential of qutrits, the ancilla count can be further reduced to just one. The key technique involves a novel poly-logarithmic depth quantum circuit designed to compute Hamming weight without the need for ancillary qubits. This quantum circuit for Hamming weight is of independent interest due to its wide-ranging applications, such as in quantum memory, quantum machine learning, and Hamiltonian dynamics simulations.
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(logn) with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth O(n) with O(log2n) ancillas, and a matching lower bound showing that Θ(n) is optimal. In both dynamic models, we obtain constant-depth circuits with O(n1+εpolylogn) ancillary qubits for every fixed ε>0. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.
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(logn) and size O(nlogn), using only the n input qubits and m=⌈log2(n+1)⌉ 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(logn) ancillary qubits, we obtain expected depth O(log2n) using measurements and classical feedforward, and depth O(n1/4logn) using unitary gates alone.
Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions:
general total Boolean functions with output size b: with 1≤m≤Θ(n2n) ancilla, size O(log(n+m)b2n), depth O(n+mb2n);
partial Boolean functions of effective support size d and output size b: with Θ(logd)≤m≤Θ(d) ancilla, size O(nlogd+bd), depth O(n+mnlognlogd+logn+md(logd+blogm));
sparse Boolean functions of true input size d: with Θ(logn+logd)≤m≤Θ(logdnd) ancilla, size O(n2logd+log(logd+m/n)nd), depth O(n+mn2lognlogd+logn+mnd).
All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
Hamming-Weight-Preserving (HWP) states, ∣ψH⟩=∑HW(x)=kαx∣x⟩, represent a fundamental class of quantum states on n qubits with fixed excitation number k, playing a pivotal role in quantum simulation, machine learning, and optimization, with prominent examples including the Bethe eigenstates of integrable models and Configuration Interaction states. However, existing preparation methodologies typically rely on sequential architectures whose depth scales linearly with the subspace dimension, whereas practical deployment on realistic quantum hardware demands shallow circuits to mitigate decoherence. In this work, we present quantum circuits that achieve the information theoretic limit of depth logarithmic in the number of populated computational basis states while maintaining asymptotically optimal size. Specifically, for general HWP states, we provide a construction that matches the lower bounds of Θ(log(kn)) depth and Θ((kn)) size. Furthermore, we propose a resource efficient scheme utilizing only O(logk) ancillary qubits. For the k=2 case, where HWP states naturally admit a graph representation, we show that states whose support graphs are trees or grids admit ancilla free preparation with Θ(logn) depth and Θ(m) size. Overall, our work provides logarithmic depth state preparation algorithms across various regimes while establishing a connection between quantum state synthesis and Krawtchouk polynomials.
Quantum arithmetic circuits have attracted extensive attention recently since it plays fundamental roles in many applications of quantum computing. Specifically, quantum circuits for integer multiplication are of great significance to various quantum algorithms, including Shor’s integer factorization and discrete logarithm algorithm. In this article, we design a family of quantum circuits for integer multiplication based on the famous classical integer multiplication algorithm, Schönhage–Strassen algorithm. We have made slight modifications to the algorithm to simplify its quantum circuit implementation. As a result, the quantum circuit we designed has gate depthO(log2n). To the best of our knowledge, this is the first poly-logarithmic depth quantum circuit for integer multiplication which keeps the circuit size and the number of ancillary qubits subquadratic. Our design has sizeO(nlognloglogn)counted by elementary quantum gates which is the same as the time complexity of the Schönhage–Strassen algorithm, and it consumesO(nlognloglogn)clean ancillary qubits. In addition, we also utilize a weaker version of Schönhage–Strassen algorithm to give a family of circuits which has depth at the same orderO(log2n)but with significantly smaller constants, while still keeping the size and number of ancillary qubits subquadratic.
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})}^{\ensuremath{\bigotimes}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 tradeoff 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.