Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function
| Autor: | Dmitri Maslov, Sergey Bravyi, Theodore J. Yoder |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Quantum Physics Model of computation FOS: Physical sciences Computer Science - Emerging Technologies 02 engineering and technology Function (mathematics) Computational Complexity (cs.CC) 020202 computer hardware & architecture Theoretical Computer Science Exponential function Computer Science - Computational Complexity Quantum circuit Emerging Technologies (cs.ET) Computer Science::Emerging Technologies Computational Theory and Mathematics Hardware and Architecture 0202 electrical engineering electronic engineering information engineering Quantum Physics (quant-ph) Hamming weight Algorithm Quantum Software Quantum computer Electronic circuit |
| Zdroj: | IEEE Transactions on Computers. 71:1170-1180 |
| ISSN: | 2326-3814 0018-9340 |
| DOI: | 10.1109/tc.2021.3076435 |
| Popis: | 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. 20 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|