论文标题
隐藏加权位功能的有效无邻章可逆和量子电路
Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
论文作者
论文摘要
隐藏的加权位功能在经典计算模型的研究中起着重要作用。一个普遍的信念是，即使引入少量的Ancillae可以实现非常有效的实现，该功能对于通过可逆的无actilla电路而言很难实现。在本文中，我们通过开发多项式可逆的无acncilla电路来驳斥指数硬度的猜想，计算隐藏的加权位函数。我们的电路具有尺寸$ o（n^{6.42}）$，其中$ n $是输入位的数量。我们还表明，隐藏的加权位函数可以通过尺寸$ o（n^2）$的量子无辅助电路来计算。所采用的技术工具来自理论计算机科学（Barrington的定理）和物理学（Fermionic Hamiltonians）技术的组合。
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.
