Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function

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 for the implementation by 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 (Barrington's theorem) and Physics (simulation of fermionic Hamiltonians) techniques.

arXiv comment20 pages, 4 figures

References in corpus (9)

• Elementary gates for quantum computation
• Synthesis of Quantum Logic Circuits
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Synthesis and Optimization of Reversible Circuits - A Survey
• Low Depth Quantum Simulation of Electronic Structure
• Techniques for the Synthesis of Reversible Toffoli Networks
• Quantum circuits for strongly correlated quantum systems
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• Application of Permutation Group Theory in Reversible Logic Synthesis

Cited by in corpus (2)

• Quantum advantage for computations with limited space
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition