Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.05469 · IEEE Transactions on Computers

Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function

Sergey B. Bravyi, Theodore J. Yoder, Dmitri Maslov

Published Apr 28, 2021• 10 citations
arXivHTMLPDF

Abstract

The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size O(n^6.42), where n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size O(n^2). The technical tools employed come from a combination of Theoretical Computer Science (Barringtons theorem) and Physics (simulation of fermionic Hamiltonians) techniques.

DOI
10.1109/tc.2021.3076435

Related papers

The Classification of Reversible Bit Operations

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^n*poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.

arXiv:1504.05155•Leibniz international proceedings in informatics•Apr 20, 2015•55 citations

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

Wei Zi, Pei Yuan, Junhong Nie +1 more

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 $Θ(\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.

quant-pharXiv:2608.04627•Aug 6, 2026•1 citation

Design of efficient reversible logic-based binary and BCD adder circuits

Himanshu Thapliyal, Nagarajan Ranganathan

Reversible logic is gaining significance in the context of emerging technologies such as quantum computing since reversible circuits do not lose information during computation and there is one-to-one mapping between the inputs and outputs. In this work, we present a class of new designs for reversible binary and BCD adder circuits. The proposed designs are primarily optimized for the number of ancilla inputs and the number of garbage outputs and are designed for possible best values for the quantum cost and delay. In reversible circuits, in addition to the primary inputs, some constant input bits are used to realize different logic functions which are referred to as ancilla inputs and are overheads that need to be reduced. Further, the garbage outputs which do not contribute to any useful computations but are needed to maintain reversibility are also overheads that need to be reduced in reversible designs. First, we propose two new designs for the reversible ripple carry adder: (i) one with no input carry c 0 and no ancilla input bits, and (ii) one with input carry c 0 and no ancilla input bits. The proposed reversible ripple carry adder designs with no ancilla input bits have less quantum cost and logic depth (delay) compared to their existing counterparts in the literature. In these designs, the quantum cost and delay are reduced by deriving designs based on the reversible Peres gate and the TR gate. Next, four new designs for the reversible BCD adder are presented based on the following two approaches: (i) the addition is performed in binary mode and correction is applied to convert to BCD when required through detection and correction, and (ii) the addition is performed in binary mode and the result is always converted using a binary to BCD converter. The proposed reversible binary and BCD adders can be applied in a wide variety of digital signal processing applications and constitute important design components of reversible computing.

arXiv:1712.02630•ACM Journal on Emerging Technologies in Computing Systems•Sep 1, 2013•111 citations

Design of Ancilla Invariant and Quantum Cost efficient reversible arithmetic components

H. V. Jayashree, V.K. Agrawal

Reversible computing is an emerging field of research and has made remarkable progress. Owing to the reduced energy dissipation in reversible circuits, a lot of research has been done on the design of reversible circuits. In reversible logic circuit designs, along with primary inputs, few constant inputs (Ancilla Inputs) are used to realize required reversible functions. In addition to this, few unused or extra output bits are generated; these bits are named as Garbage Output bits. A challenge in the reversible computation is to use minimum Ancilla Inputs and generate zero Garbage Outputs. In this work, we present designs for addition, subtraction, and addition or subtraction operations. The designs are primarily optimized to achieve zero Garbage Outputs and minimum Ancilla Inputs. In addition, these proposed arithmetic circuits are designed for best Gate Count and Quantum Cost values compared to the existing counterparts.

International Conference on Innovations in Electronics, Signal Processing and Communication (IESC)•Apr 1, 2017•0 citations

Shallow Quantum Circuit Implementation of Symmetric Functions With Limited Ancillary Qubits

Wei Zi, Junhong Nie, Xiaoming Sun

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.

arXiv:2404.06052•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Feb 5, 2025•12 citations

Resource-Efficient Reversible Quantum Circuit for Theta Function in SHA-3

Yeonsong Suh, Younghoon Park

With the advancement of quantum computing, traditional hash based security structures are increasingly exposed to threats posed by quantum algorithms. In particular, Grover's algorithm enables significantly faster pre-image attacks on hash functions than classical approaches, highlighting the need for circuit-level quantum countermeasures. To break with quantum computer, implementation of quantum circuit for the hash function is essential. However, the existing approaches require too many gates or discard ancilla qubits. In this paper, we propose a reversible quantum circuit for the$\theta$operation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse function$\theta^{-1}$. The proposed circuit allows for ancilla qubit reuse and achieves a substantial reduction in number of CNOT gates and qubits compare to previous researches. While the depth of our circuit slightly exceeds that of some existing approaches, the compact and modular design of the$\theta$operation provides a solid foundation for further enhancement.

International Conference on Ubiquitous and Future Networks•Jul 8, 2025•0 citations
The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size O(n^6.42), where n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size O(n^2). The technical tools employed come from a combination of Theoretical Computer Science (Barringtons theorem) and Physics (simulation of fermionic Hamiltonians) techniques.
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. Our theorem implies a linear-time algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^n*poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace." Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the Controlled-NOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Ruling out the possibility of additional classes, not in the list, requires some arguments about polynomials, lattices, and Diophantine equations.
Hamming weight computation maps an nnn-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)O(\log n)O(logn) with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth O(n)O(\sqrt n)O(n​) with O(log⁡2n)O(\log^2 n)O(log2n) ancillas, and a matching lower bound showing that Θ(n)Θ(\sqrt n)Θ(n​) is optimal. In both dynamic models, we obtain constant-depth circuits with O(n1+εpolylog⁡ n)O(n^{1+\varepsilon}\operatorname{polylog}\,n)O(n1+εpolylogn) ancillary qubits for every fixed ε>0\varepsilon>0ε>0. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.
Reversible logic is gaining significance in the context of emerging technologies such as quantum computing since reversible circuits do not lose information during computation and there is one-to-one mapping between the inputs and outputs. In this work, we present a class of new designs for reversible binary and BCD adder circuits. The proposed designs are primarily optimized for the number of ancilla inputs and the number of garbage outputs and are designed for possible best values for the quantum cost and delay. In reversible circuits, in addition to the primary inputs, some constant input bits are used to realize different logic functions which are referred to as ancilla inputs and are overheads that need to be reduced. Further, the garbage outputs which do not contribute to any useful computations but are needed to maintain reversibility are also overheads that need to be reduced in reversible designs. First, we propose two new designs for the reversible ripple carry adder: (i) one with no input carry c 0 and no ancilla input bits, and (ii) one with input carry c 0 and no ancilla input bits. The proposed reversible ripple carry adder designs with no ancilla input bits have less quantum cost and logic depth (delay) compared to their existing counterparts in the literature. In these designs, the quantum cost and delay are reduced by deriving designs based on the reversible Peres gate and the TR gate. Next, four new designs for the reversible BCD adder are presented based on the following two approaches: (i) the addition is performed in binary mode and correction is applied to convert to BCD when required through detection and correction, and (ii) the addition is performed in binary mode and the result is always converted using a binary to BCD converter. The proposed reversible binary and BCD adders can be applied in a wide variety of digital signal processing applications and constitute important design components of reversible computing.
Reversible computing is an emerging field of research and has made remarkable progress. Owing to the reduced energy dissipation in reversible circuits, a lot of research has been done on the design of reversible circuits. In reversible logic circuit designs, along with primary inputs, few constant inputs (Ancilla Inputs) are used to realize required reversible functions. In addition to this, few unused or extra output bits are generated; these bits are named as Garbage Output bits. A challenge in the reversible computation is to use minimum Ancilla Inputs and generate zero Garbage Outputs. In this work, we present designs for addition, subtraction, and addition or subtraction operations. The designs are primarily optimized to achieve zero Garbage Outputs and minimum Ancilla Inputs. In addition, these proposed arithmetic circuits are designed for best Gate Count and Quantum Cost values compared to the existing counterparts.
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.
With the advancement of quantum computing, traditional hash based security structures are increasingly exposed to threats posed by quantum algorithms. In particular, Grover's algorithm enables significantly faster pre-image attacks on hash functions than classical approaches, highlighting the need for circuit-level quantum countermeasures. To break with quantum computer, implementation of quantum circuit for the hash function is essential. However, the existing approaches require too many gates or discard ancilla qubits. In this paper, we propose a reversible quantum circuit for theθ\thetaθoperation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse functionθ−1\theta^{-1}θ−1. The proposed circuit allows for ancilla qubit reuse and achieves a substantial reduction in number of CNOT gates and qubits compare to previous researches. While the depth of our circuit slightly exceeds that of some existing approaches, the compact and modular design of theθ\thetaθoperation provides a solid foundation for further enhancement.