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.
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 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.
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θoperation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse functionθ−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θoperation provides a solid foundation for further enhancement.