ﻻ يوجد ملخص باللغة العربية
Simons problem is one of the most important problems demonstrating the power of quantum computers, which achieves a large separation between quantum and classical query complexities. However, Simons discussion on his problem was limited to bounded-error setting, which means his algorithm can not always get the correct answer. Exact quantum algorithms for Simons problem have also been proposed, which deterministically solve the problem with O(n) queries. Also the quantum lower bound Omega(n) for Simons problem is known. Although these algorithms are either complicated or specialized, their results give an O(n) versus Omega(sqrt{2^{n}}) separation in exact query complexities for Simons problem (Omega(sqrt{2^{n}}) is the lower bound for classical probabilistic algorithms), but it has not been proved whether this separation is optimal. In this paper, we propose another exact quantum algorithm for solving Simons problem with O(n) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simons algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simons problem can be solved by a classical deterministic algorithm with O(sqrt{2^{n}}) queries (as we are aware, there were no classical deterministic algorithms for solving Simons problem with O(sqrt{2^{n}}) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simons problem: Theta({n}) versus Theta({sqrt{2^{n}}}).
Simons problem is an essential example demonstrating the faster speed of quantum computers than classical computers for solving some problems. The optimal separation between exact quantum and classical query complexities for Simons problem has been p
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantu
We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithm
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for so
We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We ex