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

07/10/2020
by   Sergey Bravyi, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset