We extend the representation of quantum algorithms to the preparation of the problem setting. An initial measurement serves to set the problem, the final one as usual to read the solution. This extension highlights the possibility of ascribing the selection of a variable fraction R of the information that specifies the random outcome of the initial measurement to the final measurement. The input state of the quantum algorithm to the problem solver (Alice), of maximal ignorance of the problem setting that to her should be hidden, would consequently be projected on a state of lower entropy where she knows in advance an R-th part of the setting (i. e. of the information that specifies it). Given the appropriate value of R, the quantum algorithm turns out to be a sum over classical histories in each of which Alice knows in advance one of the possible R-th parts of the problem setting and performs the Q(R) computations (oracle queries) still needed to find the solution. Grover's search problem can be solved with any value of R from 0 to about 1/2, when the solution algorithm becomes the optimal Grover algorithm. In all the optimal quantum algorithms examined, R is close to 1/2 and Q(1/2) yields the order of magnitude of the number of queries. If this held in general, as it seems to be plausible, given any oracle problem we would know the order of magnitude of the number of queries needed for its optimal quantum solution.
We extend the representation of quantum algorithms to the preparation of the problem setting. An initial measurement serves to set the problem, the final one as usual to read the solution. This extension highlights the possibility of ascribing the selection of a variable fraction R of the information that specifies the random outcome of the initial measurement to the final measurement. The input state of the quantum algorithm to the problem solver (Alice), of maximal ignorance of the problem setting that to her should be hidden, would consequently be projected on a state of lower entropy where she knows in advance an R-th part of the setting (i. e. of the information that specifies it). Given the appropriate value of R, the quantum algorithm turns out to be a sum over classical histories in each of which Alice knows in advance one of the possible R-th parts of the problem setting and performs the Q(R) computations (oracle queries) still needed to find the solution. Grover's search problem can be solved with any value of R from 0 to about 1/2, when the solution algorithm becomes the optimal Grover algorithm. In all the optimal quantum algorithms examined, R is close to 1/2 and Q(1/2) yields the order of magnitude of the number of queries. If this held in general, as it seems to be plausible, given any oracle problem we would know the order of magnitude of the number of queries needed for its optimal quantum solution.
We investigate the reason for the quantum speedup -- quantum algorithms requiring fewer computation steps than their classical counterparts. We extend their representation to the process of setting the problem. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. This representation is to Bob and any external observer, it cannot be to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden inside it. We resort to relational quantum mechanics. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action. To her, the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. We show that we can ascribe to the final measurement the selection of any part -- say the R-th part -- of the random outcome of the initial measurement. This projects the input state to Alice on a state of lower entropy where she knows a corresponding part of the problem setting. The quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given an oracle problem and a value of R, this retrocausality model provides the number of black box computations required to solve it. Conversely, given a known quantum algorithm, it yields the value of R that explains its speed up. R = 1/2 always yields the number of black box computations required by an existing quantum algorithm and the order of magnitude of the number required by optimal one.
We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.
We investigate the reason for the quantum speedup -- quantum algorithms requiring fewer computation steps than their classical counterparts. We extend their representation to the process of setting the problem. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. This representation is to Bob and any external observer, it cannot be to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden inside it. We resort to relational quantum mechanics. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action. To her, the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. We show that we can ascribe to the final measurement the selection of any part -- say the R-th part -- of the random outcome of the initial measurement. This projects the input state to Alice on a state of lower entropy where she knows a corresponding part of the problem setting. The quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given an oracle problem and a value of R, this retrocausality model provides the number of black box computations required to solve it. Conversely, given a known quantum algorithm, it yields the value of R that explains its speed up. R = 1/2 always yields the number of black box computations required by an existing quantum algorithm and the order of magnitude of the number required by optimal one.
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 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.
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