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 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 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.
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.
I provide an alternative way of seeing quantum computation. First, I describe an idealized classical problem solving machine that, thanks to a many body interaction, reversibly and nondeterministically produces the solution of the problem under the simultaneous influence of all the problem constraints. This requires a perfectly accurate, rigid, and reversible relation between the coordinates of the machine parts - the machine can be considered the many body generalization of another perfect machine, the bounching ball model of reversible computation. The mathematical description of the machine, as it is, is applicable to quantum problem solving, an extension of the quantum algorithms that comprises the physical representation of the problem-solution interdependence. The perfect relation between the coordinates of the machine parts is transferred to the populations of the reduced density operators of the parts of the computer register. The solution of the problem is reversibly and nondeterministically produced under the simultaneous influence of the state before measurement and the quantum principle. At the light of the present notion of simultaneous computation, the quantum speed up turns out to be "precognition" of the solution, namely the reduction of the initial ignorance of the solution due to backdating, to before running the algorithm, a time-symmetric part of the state vector reduction on the solution; as such, it is bounded by state vector reduction through an entropic inequality. PACS numbers: 03.67.Lx, 01.55.+b, 01.70.+w
Bob chooses a function from a set of functions and gives Alice the black box that computes it. Alice is to find a characteristic of the function through function evaluations. In the quantum case, the number of function evaluations can be smaller than the minimum classically possible. The fundamental reason for this violation of a classical limit is not known. We trace it back to a disambiguation of the principle that measuring an observable determines one of its eigenvalues. Representing Bob's choice of the label of the function as the unitary transformation of a random quantum measurement outcome shows that: (i) finding the characteristic of the function on the part of Alice is a by-product of reconstructing Bob's choice and (ii) because of the quantum correlation between choice and reconstruction, one cannot tell whether Bob's choice is determined by the action of Bob (initial measurement and successive unitary transformation) or that of Alice (further unitary transformation and final measurement). Postulating that the determination shares evenly between the two actions, in a uniform superposition of all the possible ways of sharing, implies that quantum algorithms are superpositions of histories in each of which Alice knows in advance one of the possible halves of Bob's choice. Performing, in each history, only the function evaluations required to classically reconstruct Bob's choice given the advanced knowledge of half of it yields the quantum speed-up. In all the cases examined, this goes along with interleaving function evaluations with non-computational unitary transformations that each time maximize the amount of information about Bob's choice acquired by Alice with function evaluation.
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.