The oracle chooses a function out of a known set of functions and gives to the player a black box that, given an argument, evaluates the function. The player should find out a certain character of the function (e. g. its period) through function evaluation. This is the typical problem addressed by the quantum algorithms. In former theoretical work, we showed that a quantum algorithm requires the number of function evaluations of a classical algorithm that knows in advance 50 % of the information that specifies the solution of the problem. This requires representing physically, besides the solution algorithm, the oracle’s choice. Here we check that this 50 % rule holds for the main quantum algorithms. In the structured problems, a classical algorithm with the advanced information, to identify the missing information should perform one function evaluation. The speed up is exponential since a classical algorithm without advanced information should perform an exponential
The oracle chooses a function out of a known set of functions and gives to the player a black box that, given an argument, evaluates the function. The player should find out a certain character of the function (e. g. its period) through function evaluation. This is the typical problem addressed by the quantum algorithms. In former theoretical work, we showed that a quantum algorithm requires the number of function evaluations of a classical algorithm that knows in advance 50 % of the information that specifies the solution of the problem. This requires representing physically, besides the solution algorithm, the oracle’s choice. Here we check that this 50 % rule holds for the main quantum algorithms. In the structured problems, a classical algorithm with the advanced information, to identify the missing information should perform one function evaluation. The speed up is exponential since a classical algorithm without advanced information should perform an exponential
In former work, we showed that a quantum algorithm requires the number of operations (oracle's queries) of a classical algorithm that knows in advance 50% of the information that specifies the solution of the problem. We gave a preliminary theoretical justification of this "50% rule" and checked that the rule holds for a variety of quantum algorithms. Now, we make explicit the information about the solution available to the algorithm throughout the computation. The final projection on the solution becomes acquisition of the knowledge of the solution on the part of the algorithm. Backdating to before running the algorithm a time-symmetric part of this projection, feeds back to the input of the computation 50% of the information acquired by reading the solution.
We explain the mechanism of the quantum speed-up -quantum algorithms requiring fewer computation steps than their classical equivalentfor a family of algorithms.Bob chooses a function and gives to Alice the black box that computes it.Alice, without knowing Bob's choice, should find a character of the function (e. g. its period) by computing its value for different arguments.There is naturally correlation between Bob's choice and the solution found by Alice.We show that, in quantum algorithms, this correlation becomes quantum.This highlights an overlooked measurement problem: sharing between two measurements the determination of correlated (thus redundant) measurement outcomes.All is like Alice, by reading the solution at the end of the algorithm, contributed to the initial choice of Bob, for half of it in quantum superposition for all the possible ways of taking this half.This contribution, back evolved to before running the algorithm, where Bob's choice is located, becomes Alice knowing in advance half of this choice.The quantum algorithm is the quantum superposition of all the possible ways of taking half of Bob's choice and, given the advanced knowledge of it, classically computing the missing half.This yields a speed-up with respect to the classical case where, initially, Bob's choice is completely unknown to Alice.
Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50 % of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective ”advanced information classical algorithm”. This algorithm, given the advanced information (50 % of the bits encoding the problem solution), performs the operations (oracle’s queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up. 1
The usual representation of quantum algorithms, limited to the problem solving process, is incomplete as it lacks the initial measurement. Completing it involves three steps: (i) representing the problem setting process, (ii) relativizing this representation to Alice, the problem solver, to whom the problem setting must be concealed, (iii) representing the reversibility of the computation process by symmetrizing it for time reversal. The latter step shows that all is as if Alice, before beginning her problem solving action, knew half of the information that specifies the solution of the problem she will read in the future. An optimal quantum algorithm is a sum over classical histories in each of which Alice knows in advance one of the possible halves of the solution and performs the computation steps (oracle queries) necessary to identify the missing half. This explains the quantum computational speedup and allows to predict the speedup offered by the optimal quantum solution of any oracle problem.
In former work, we showed that a quantum algorithm is the sum over the histories of a classical algorithm that knows in advance 50% of the information about the solution of the problem - each history is a possible way of getting the advanced information and a possible result of computing the missing information. We gave a theoretical justification of this 50% advanced information rule and checked that it holds for a large variety of quantum algorithms. Now we discuss the theoretical justification in further detail and counter a possible objection. We show that the rule is the generalization of a simple, well known, explanation of quantum nonlocality - where logical correlation between measurement outcomes is physically backed by a causal/deterministic/local process with causality allowed to go backward in time with backdated state vector reduction. The possible objection is that quantum algorithms often produce the solution of the problem in an apparently deterministic way (when their unitary part produces an eigenstate of the observable to be measured and measurement produces the corresponding eigenvalue - the solution - with probability 1), while the present explanation of the speed up relies on the nondeterministic character of quantum measurement. We show that this objection would mistake the nondeterministic production of a definite outcome for a deterministic production.
In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.