论文标题
用于计数零交叉的量子算法
A quantum algorithm for counting zero-crossings
论文作者
论文摘要
我们提出了一个零交叉计数问题，这是伯恩斯坦 - 瓦泽拉尼问题的概括。此问题的目的是计算特殊类型的序列s中的零交叉数（或符号更改）的数量，其定义取决于秘密字符串。提出了一种量子算法来解决此问题。 The proposed quantum algorithm requires only one oracle query to solve the problem, whereas a classical algorithm would need at least n oracle queries, where $2^n$ is the size of the sequence S. In addition to solving the zero-crossings counting problem, we also give a quantum circuit for performing the Walsh-Hadamard transforms in sequency ordering. WALSH-HADAMARD序列排序中的变换用于广泛的科学和工程应用，包括数字信号和图像处理。因此，为序列排序计算walsh-hadamard变换的拟议量子电路可能有助于量子计算算法的应用程序，该算法需要按序列排序计算WALSH-HADAMARD转换的应用。
We present a zero-crossings counting problem that is a generalization of the Bernstein-Vazirani problem. The goal of this problem is to count the number of zero-crossings (or sign changes) in a special type of sequence S, whose definition depends upon a secret string. A quantum algorithm is presented to solve this problem. The proposed quantum algorithm requires only one oracle query to solve the problem, whereas a classical algorithm would need at least n oracle queries, where $2^n$ is the size of the sequence S. In addition to solving the zero-crossings counting problem, we also give a quantum circuit for performing the Walsh-Hadamard transforms in sequency ordering. The Walsh-Hadamard transform in sequency ordering is used in a wide range of scientific and engineering applications, including in digital signal and image processing. Therefore, the proposed quantum circuit for computing the Walsh-Hadamard transforms in sequency ordering may be helpful in quantum computing algorithms for applications for which the computation of the Walsh-Hadamard transform in sequency ordering is required.
