Search

An algorithm is exact if it always produces the correct answer on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. Nim game is a well-known combinatorial game which has a complete mathematical theory, and many kinds of Nim games have been studied in the literature. One famous kind of Nim games are subtraction games played with one heap of tokens, with players taking turns removing from the heap a number of tokens belonging to a specified subtraction set. The last player to move wins. In this paper, we propose a restricted subtraction game with the subtraction set determined by a specified matrix, and present an exact quantum algorithm to solve it. We show that the query complexity of our quantum algorithm is $O(n^{\frac {3}{2}})$, while the classical exact query complexity is Θ(n2).

We devise new quantum algorithms that exponentially speeds up the training and prediction procedures of twin support vector machines (TSVM). To train TSVMs using quantum methods, we demonstrate how to prepare the desired input states according to classical data, and these states are used in the quantum algorithm for the system of linear equations. In the prediction process, we employ a quantum circuit to estimate the distances from a new sample to the hyperplanes and then make a decision. The proposed quantum algorithms can learn two non-parallel hyperplanes and classify a new sample by comparing the distances from the sample to the two hyperplanes in $O(\log mn)$ time, where $m$ is the sample size and $n$ is the dimension of each data point. In contrast, the corresponding classical algorithm requires polynomial time for both the training and prediction procedures.

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)={x}_{{i}_{1}}$ or ${x}_{{i}_{1}}\ensuremath{\bigoplus}{x}_{{i}_{2}}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP ( p , n , k ) , is a natural extension of Simon's problem: Given a function f : Z p n → X where X is a finite set and the promise that for any x , y ∈ Z p n , f ( x ) = f ( y ) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k n , the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O ( n − k ) . However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP ( p , n , k ) has to query at least Ω ( max ⁡ { k , p n − k } ) values and any classical nonadaptive deterministic algorithm for GSP ( p , n , k ) has to query at least Ω ( max ⁡ { k , k ⋅ p n − k } ) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O ( max ⁡ { k , k ⋅ p n − k } ) on the classical deterministic query complexity of GSP ( p , n , k ) , by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem.