{'fraction_non_alphanumeric': 0.03978664080494605, 'fraction_numerical': 0.016268638622863377, 'mean_word_length': 4.335144224550511, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The 50% advanced information rule of the quantum algorithms

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 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. 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 number of function evaluations. In unstructured database search, a classical algorithm that knows in advance 50% of the n bits of the database location, to identify the n/2 missing bits should perform Order(2 power n/2) function evaluations. The speed up is quadratic since a classical algorithm without advanced information should perform Order(2 power n) function evaluations. The 50% rule identifies the problems solvable with a quantum sped up in an entirely classical way, in fact by comparing two classical algorithms, with and without the advanced information.


Introduction
We provide some context. The problem typically addressed by a quantum algorithm can be seen as a competition between two players. There is a set of functions known to both players, for example the set of the "periodic" functions f k (x) : {0, 1} n → {0, 1} n−1 -section 4.1. The first player (the oracle) chooses one of these functions and gives to the second player a black box (i. e. non-inspectable inside) hardwired for the computation of that function. The second player should find out a certain character of the function, for example its period, by computing f k (x) for different values of x. As well known, the quantum algorithm requires a substantially lower number of function evaluations than the corresponding classical algorithm.
In (Castagnoli, 2008 and2009), on the basis of theoretical considerations, we showed that the 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 (see also Castagnoli and Finkelstein, 2001).
To see this, the key step is representing physically the interdependence between the problem and the solution: it suffices to represent together the production of the problem on the part of the oracle and the production of the solution on the part of the quantum algorithm. We review this step, which is common to the present work: (i) We represent the function f k (x) chosen by the oracle by means of an auxiliary quantum register K -the oracle's choice register. This register, just a conceptual reference, hosts the suffix k of f k (x), a bit string defined as follows. In the case of the structured problems, k represents the table of f k (x); in the example of the "periodic" functions, k is the sequence of 2 n fields of n − 1 bits, the values of the function for increasing values of the argument. In unstructured data base search, k is the data base location chosen by the oracle -here f k (x) is the Kronecker function δ (k, x).
(ii) The black box hardwired for the computation of f k (x) is replaced by a general purpose black box that, given the inputs k (representing the function chosen by the oracle) and x (the argument to query the black box with) computes f (k, x) = f k (x).
(iii) Register K is ideally added to the usual input register X, containing the value of x, and output register V , hosting the result of function evaluation f (k, x). We should think of preparing K in an even weighted (indifferently coherent or incoherent) superposition of all the possible values of k. As usual, X is prepared in the coherent even weighted superposition of all the possible values of x and V in a coherent initial state depending on the algorithm.
(iv) Each function evaluation entangles the oracle's choice register K and the query register X. Correspondingly, information about the oracle's choice propagates from the former to the latter register.
(v) After each function evaluation, we rotate the basis of X to make this information readable. Function evaluation/rotation of the X basis is done once in the algorithms of Deutsch, Deutsch&Jozsa, and Simon, iteratively (for a number of iterations O 2 n/2 ) in Grover's algorithm.
(vi) Measuring the content of K and X at the end of the algorithm induces state reduction (i. e. projects the state before measurement) on both the function chosen by the oracle (the value of k hosted in register K) and the solution produced by the algorithm (the value of x hosted in register X) 1 . Backdating, to before running the algorithm, the reduction induced by measuring the content of K yields the usual quantum algorithm.
(vii) In this picture, quantum computation is reduction on the solution of the problem under a relation (or correlation) representing problem-solution interdependence -the correlation is between the content of register K (the oracle's choice) and the content of register X (the solution) at the end of the algorithm.
(viii) Backdating in time, to before running the algorithm, a time symmetric part of this reduction shows that the 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 (Castagnoli, 2009). We call this the 50% rule.
(ix) In this context, the information that specifies the solution of the problem is the information that specifies both the solution (the content of register X at the end of the algorithm) and the problem (the content of register K). Since the solution is determined by the content of K, the information that specifies the solution is redundant. Knowing in advance 50% of the information that specifies the solution of the problem amounts to knowing in advance 50% of the information about the solution of the problem contained in the bit string k (read in register K at the end of the algorithm). The 50% rule is reformulated as follows: the quantum algorithm requires the number of function evaluations of a classical algorithm that knows in advance 50% of the information about the solution of the problem contained in k.
(x) In unstructured database search and in Deutsch's problem, k is an unstructured bit string. 50% of the information about the solution of the problem contained in k is represented by any 50% of the bits of k (either one of the two rows of the table of f k (x) in Deutsch's problem). If instead k is structured, which is the case of the structured problems, ascertaining what is 50% of the information that specifies the solution of the problem requires a case by case analysis. It turns out that this information is represented by those half tables of f k (x) that do not already specify the solution of the problem (the half tables that specify the solution, containing 100% of the information about the solution, should be discarded).
The main objective of this work is checking that the 50% rule holds for the main quantum algorithms, namely the algorithms of Deutsch, Deutsch&Jozsa, Simon (where the analysis extends by similarity to the hidden subgroup algorithms, thus in particular to the quantum part of Shor's algorithm), and Grover.
In Deutsch's and the structured problems, the classical algorithm knowing in advance 50% of the rows of the table of f k (x) (excluding the half tables that identify the solution) in order to identify the solution should compute any one of the missing rows -i. e. perform one function evaluation for any value of x outside the advanced information. In the structured problems the speed up is exponential since a classical algorithm without advanced information should compute an exponential number of rows. In unstructured data base search, knowing in advance 50% of the information that specifies the solution of the problem means knowing in advance 50% of the n bits of the data base location chosen by the oracle. To identify the n/2 missing bits, the advanced information classical algorithm should perform O 2 n/2 function evaluations. The speed up is quadratic since a classical algorithm without advanced information should perform O (2 n ) function evaluations.
Thus the speed up comes from comparing two classical algorithms, with and without the advanced information. The 50% rule brings the identification of the problems solvable with a quantum speed up to the classical framework.
We also show that the advanced information classical algorithm defines the quantum algorithm. We consider the "skeleton" of the classical algorithm. This, given the advanced information, performs the function evaluations required to define the solution of the problem (in the classical framework, defining does not mean computing). We consider all the possible histories of this classical algorithm. Each history -corresponding to a possible way of getting the advanced information and a possible result of computing the missing information -is represented in quantum notation as a sequence of sharp states. The sum of the histories yields the function evaluation stage of the quantum algorithm.
The initial phase of each history is chosen in such a way that the transfer of information from the classical to the quantum algorithm is maximized.
As already said, each function evaluation entangles the oracle's choice register K and the solution register X, information about the oracle's choice propagates from the former to the latter register.
Which is this information is clear when the entanglement produced by function evaluation is maximal, like in the algorithms of Deutsch, Deutsch&Jozsa (where the only function evaluation produces a maximally entangled state), and Grover (where each function evaluation feeds the amplitude of a maximally entangled state at the expense of the amplitude of an unentangled state). In the maximally entangled state, each orthogonal state of K (possibly itself a quantum superposition) corresponds to a solution of the problem and is correlated with an orthogonal state of X. This allows to define in a constructive way the rotation of the X basis that makes this solution readable. This completes the definition of the quantum algorithm (of the algorithm's iterate in Grover's case).
Which is the information propagated to register X is less clear in the case of Simon's and the hidden subgroup algorithms, where the entanglement produced by function evaluation is not maximal. The final rotation of the X basis (here the Hadamard transform on X) can still be defined as the transformation that maximizes the information about the oracle's choice readable in it; this completes the definition of the quantum algorithm, although it is no more a constructive definition.
Summing up: (i) the 50% rule brings the search of the speed ups to the classical framework and (ii) once identified a problem solvable with a quantum speed up, the same rule could be used a second time for searching the quantum algorithm that yields the speed up -in fact the advanced information classical algorithm defines this quantum algorithm. In the following sections, for each quantum algorithm: (i) we extend the algorithm to the physical representation of the oracle's choice, (ii) we check the 50% rule, and (iii) we rebuild the quantum algorithm out of the advanced information classical algorithm.
k ≡ k 0 , k 1 , a two-bit string belonging to {0, 1} 2 ; it is both the suffix of f and, clockwise rotated, the table of function values ordered for increasing values of the argument -in fact k 0 = f k (0) and k 1 = f k (1). Then the oracle gives to the second player a black box that, given an input x, computes f k (x). The second player, by trying function evaluation for different values of x, should find whether the function is balanced (i. e. f 01 or f 10 , with an even number of zeroes and ones) or constant (i. e. f 00 or f 11 ). This requires two function evaluations in the classical case (for x = 0 and x = 1), just one in the quantum case. Deutsch's algorithm is the root of all subsequent quantum algorithms for what concerns both the speed up and the representation of quantum computation. Bits are replaced by qubits (Finkelstein, 1969, Benioff, 1982 and reversible logical operations (Bennett, 1973, Fredkin and Toffoli, 1982 by unitary transformations (Finkelstein, 1969, Benioff, 1982. We give directly the extension of Deutsch's algorithm to the representation of the random choice of the function on the part of the oracle (Castagnoli, 2008). A two qubit input register K contains the oracle's choice k. As usual, the one qubit input register X contains the value of x to query the black box with; the one qubit output register V , initially containing v, eventually contains v ⊕ f (k, x) -the result of function evaluation is module 2 added to v for logical reversibility. The black box that, given the input x, computes f k (x) is replaced by a black box that, given the inputs k and x, computes f (k, x) = f k (x). The quantum algorithm consists of three steps: (0) prepare register K in an even weighted superposition of all the possible values of k, register X in the even weighted superposition of all the possible values of x, and register V in the antisymmetric state, (1) perform function evaluation (which leaves the content of K and X unaltered and changes that of V ), and (2) apply the Hadamard transform to register X.
The initial state is thus The superposition hosted in register K is indifferently coherent or incoherent (in this latter case |00 K should be replaced by e iδ00 |00 K , with δ 00 a random phase with uniform distribution in [0, 2π], etc.). Function evaluation yields (3) Applying the Hadamard transform to register X yields Let us denote by [K] the content of register K, by [X] the content of X. (4) determines the moves of both players: the oracle's choice k in register K and the solution found by the second player in register X. Backdating to before running the algorithm the state reduction induced by measuring [K] gives the original Deutsch's algorithm -it generates at random the value of k hosted in the black box.

Checking the 50% rule
The information acquired by measuring [K] and [X] in (4) is the two bits of the unstructured bit string k -since the content of X is a function of the content of K the information contained in X is redundant. The quantum algorithm requires the number of function evaluations of a classical algorithm working on a solution space reduced in size because one bit of k, either k 0 = f (k, 0) or k 1 = f (k, 1), is known in advance. To identify the character of the function, this algorithm must acquire the other bit of information by computing, respectively, either k 1 = f (k, 1) or k 0 = f (k, 0). Thus the classical algorithm has to perform one function evaluation like the quantum algorithm.
This verifies the 50% rule for Deutsch's algorithm. This rule shows that Deutsch's problem is solvable with a quantum speed up independently of our knowledge of the quantum algorithm. In fact the speed up comes from comparing two classical algorithms, with and without the advanced information.

Building the quantum algorithm out of the advanced information classical algorithm
We build the function evaluation stage of the quantum algorithm out of the corresponding stage of a classical algorithm that knows in advance 50% of k.
We should consider all the possible ways of getting the advanced information and all the possible results of computing the missing information, see table (5).
# advanced information result of function evaluation character of the function We represent the possible histories in quantum notation. Since we are dealing with classical computations, we require that the input and the output of each history (before and after function evaluation) is a sharp quantum state. There are sixteen possible histories: • Row #1. The advanced information is k 0 = 0. The classical algorithm should compute k 1 = f (k, 1) that, for this row, is k 1 = f (k, 1) = 0. The quantum representation of the oracle's choice is thus |00 K . The initial state of register X should be |1 X , the state to query the black box with in order to compute f (k, 1). Since the result of this computation is module 2 added to the initial content of register V , we should split row #1 into two sub-rows: #1.1 with register V initially in |0 V and #1.2 with register V initially in |1 V . The initial state of history #1.1 is thus Ψ These computation histories have to be added together and must be given an initial phase. For the time being, we set the initial phase of each history in such a way that, in the superposition of all histories, we obtain the initial state of the quantum algorithm; further below we justify this choice independently of our a priori knowledge of the quantum algorithm. To simplify the notation, we sum together the initial states of these two histories: Ψ We take care of normalization at the end. Function evaluation transforms Ψ (module 2 adding f (00, 1) = 0 to the former content of V leaves this content unaltered).
• Row #5. Advanced information k 1 = 0, result of function evaluation k 0 = f (k, 0) = 0. Applying the same rationale of the above point, we obtain the initial state Ψ • The sum of the histories of rows #1 and #5 yields the transformation of (module 2 adding f (01, 1) = 1 to the former content of V swaps |0 V and |1 V ; the overall result is rotating the phase of the present pair of histories by π).
• The sum of the histories of rows #2 and #7 yields the transformation of , namely the function evaluation stage of Deutsch's algorithm when K is in |01 K .
• We proceed in a similar way for the other histories. Summing together the quantum representations of the 16 classical histories and normalizing yields the transformation of Ψ 0 (equation 2) into Ψ 1 (equation 3).
In hindsight, we can see a shortcut. For each |k K , we perform function evaluation not only for those values of x required to identify the solution of the problem, but also for all the other possible values of x. In other words, we perform function evaluation for each product |k K (|0 X + |1 X ) (|0 V − |1 V ); junk histories (for that |k K ) do not harm, the important thing is performing function evaluation for the values of x required to identify the solution. As one can see, this yields directly the transformation of Ψ 0 (equation 2) into Ψ 1 (equation 3). Conversely, by simply inspecting the form of Ψ 0 in equation (2), one can see that each |k K (|0 X + |1 X ) (|0 V − |1 V ) is the initial state of a bunch of histories as from the above shortcut.
Summing up, quantum parallel computation can be seen as the sum of the histories of a classical algorithm that, given the advanced information, computes the missing information required to identify the solution of the problem. This holds in general for the function evaluation stage of all quantum algorithms.
By considering the sum of the histories, we can justify the choice of the initial phase. We take the generic initial state of register V : Under the amplitude α, the computation performed by the advanced information classical algorithm gets lost in the quantum translation, since the overall initial state is transformed into itself. Under β, the transfer of information from the classical to the quantum algorithm is maximum (we obtain the above development). This justifies the choice α = 0 and β = 1. Now we look at the outcome of the second stage -equation (3). Function evaluation has created a maximal entanglement between registers K and X, two orthogonal states of K, |00 K − |11 K and |01 K − |10 K (or indifferently e iδ00 |00 K − e iδ11 |11 K and e iδ01 |01 K − e iδ10 |10 K ) are correlated with two orthogonal states of X, respectively |0 X + |1 X and |0 X − |1 X . This means that, after function evaluation, register X contains the information that discriminates between |00 K − |11 K and |01 K − |10 K , namely between constant and balanced functions. Therefore we should rotate the X basis in such a way that this information becomes readable: |0 X + |1 X should be transformed into |0 X , etc.. This is a constructive definition of the Hadamard transform on register X. This completes the derivation of the quantum algorithm from the classical algorithm with the advanced information.
3 Deutsch&Jozsa algorithm 3.1 Reviewing and extending the algorithm Deutsch&Jozsa's algorithm is a generalization of Deutsch's algorithm that achieves an exponential speed up (Deutsch and Jozsa, 1989). This time we deal with the set of the functions f k : {0, 1} n → {0, 1} such that the function is either constant (all zeroes or all ones), or balanced (even number of zeroes and ones). k ≡ k 0 , k 1 , ..., k 2 n −1 is a 2 n bit string rpresenting the table of the functionnamely the sequence of function values for increasing values of the argument. Table (6) shows this set of functions for n = 2 -we shall focus on this example. Note that k 0 = f k (00), k 1 = f k (01), k 2 = f k (10) and k 3 = f k (11). The string k is both the suffix of f and, clockwise rotated, the table of the function chosen by the oracle.
The problem is as follows. An oracle chooses at random one of these functions and gives to the second player the black box hardwired for the computation of that function. The second player, by trying function evaluation for different values of x, must find whether the function is balanced or constant. In the worst case, this requires a number of function evaluations exp (n) in the classical case, just one in the quantum case.
We give directly the extension of the quantum algorithm to the representation of the choice of the function on the part of the oracle. The black box, given the inputs k and x, computes f (k, x) = f k (x). The 2 n qubit oracle's choice register K contains the table of the function -we should keep in mind that this register is just a conceptual reference. The query register X is n qubit. The output register V is one qubit. The algorithm consists of three steps: (0) prepare register K in an even weighted superposition of all the possible values of k, register X in the even weighted superposition of all the possible values of x, and register V in the antisymmetric state, (1) perform function evaluation, which changes the content of V from v to v ⊕ f (k, x), and (2) apply the Hadamard transform to register X.
The initial state is Function evaluation yields (8) Applying the Hadamard transform to register X yields (9) Measuring [K] and [X] in (9) determines the moves of both players, namely the oracle's choice (a value of k) and the solution provided by the second player: all zeroes if the function is constant, not so if the function is balanced. Backdating to before running the algorithm the state reduction induced by measuring [K] gives the original Deutsch&Jozsa's algorithm -it generates at random the value of k hosted in the black box.

Checking the 50% rule
The information acquired by measuring [K] and [X] in (9) is the information in the structured bit string k -the table of the function f k (x). Since the content of X is a function of the content of K, the information contained in X is redundant. 50% of the information about the solution (in k) is represented by all the possible half tables that do not contain different values of the function. Those with different values already say that the function is balanced -they provide 100% of the information about the solution and should be discarded. For example, with reference to table (6), let us consider the half tables for x = 00 and x = 01. Those in the first four columns contain exactly 50% of the information in k (which is also evident for reasons of symmetry) and thus represent the advanced information. The half tables in the last four columns (for x = 00 and x = 01) already say that the function is balanced and are discarded. By the way, this does not mean discarding these columns; e. g. in the fifth column, the half table for x = 00 and x = 10 and that for x = 01 and x = 11 are good.
With this definition of the advanced information, the solution is always identified by computing an extra row, namely by performing one function evaluation for any value of x outside the advanced information (if the value of the function is still the same, the function is constant, otherwise it is balanced).
This verifies the 50% rule for Deutsch&Jozsa algorithm. This rule shows that Deutsch&Jozsa's problem is solvable with an exponential speed up independently of our knowledge of the quantum algorithm -the speed up comes from comparing two classical algorithms, with and without the advanced information.

Building the quantum algorithm out of the advanced information classical algorithm
The function evaluation stage of the quantum algorithm -namely the transformation of Ψ 0 (equation 7) into Ψ 1 (equation 8) -is the sum of the histories of the advanced information classical algorithm. This is clear by looking at the form of Ψ 0 with the shortcut of section 2.3 in mind. Without shortcut we obtain the same result, as follows: • Register K in |0000 K ; advanced information k 0 = 0 and k 1 = 0; in order to ascertain whether the function is constant or balanced, we should perform function evaluation for either x = 10 or x = 11; as we are building the superposition of all the possible histories, we do it for the superposition of x = 10 and x = 11; with K in |0000 K , the result of function evaluation is k 2 = 0 and k 3 = 0; thus the initial state is Ψ (1)
• Register K in |0000 K ; advanced information k 2 = 0 and k 3 = 0; result of function evaluation (for x = 10 or x = 11) k 0 = 0 and k 1 = 0; initial state Ψ (2) 0 • The sum of the histories #1 and #2 yields the function evaluation stage of Deutsch&Jozsa's algorithm when K is in |0000 K ; with normalization, considering other ways of getting the advanced information (with K in |0000 K ) does not modify the result already obtained.
• Register K in |0101 K ; advanced information, e. g., k 0 = 0 and k 1 = 1; we already know that the function is balanced, no function evaluation is needed, and there are no histories in such a case.
By summing together all the histories corresponding to the good half tables, we obtain the function evaluation stage of the quantum algorithm.
The choice of the initial phase of each history is justified as in Deutsch's algorithm.
We examine the outcome of function evaluation, namely Ψ 1 (equation 8).
There is a maximal entanglement between registers K and X. Orthogonal states of K , discriminating between constant and balanced functions (also between different kinds of balanced functions, but this is not relevant), are correlated with orthogonal states of X. This means that the information whether the function is constant or balanced has propagated to register X. To read this information, we should rotate the X basis in such a way that (|0000 K − |1111 K )(|00 X + |01 X + |10 X + |11 X goes into (|0000 K − |1111 K ) |00 X , etc.. This is a constructive definition of the Hadamard transform on register X. This completes the derivation of the quantum algorithm from the classical algorithm with the advanced information.

Simon's algorithm 4.1 Reviewing and extending the algorithm
We deal with the set of the "periodic" functions f k : .., k 2 n (n−1)−1 is a 2 n (n − 1) bit string, the sequence of function values (each a field of n − 1 bits) for increasing values of the argument, n−1 is an n bit string (depending on the value of k) belonging to {0, 1} n with the exclusion of the all zeroes string, (iii) x and y are variables belonging to {0, 1} n also represented as n bit strings, and (iv) ⊕ denotes bit by bit module 2 addition.
Thus, the string h (k) , also called the hidden string, is a sort of period of the function f k (x). Since h (k) ⊕ h (k) = 0, each value of the function appears exactly twice in the table of the function. This means that 50% of the rows plus one surely contain a same value twice, which identifies the period.
The problem is as follows. The oracle chooses at random a function f k (x), then he gives to the second player the black box hardwired for the computation of that function. The second player should find the string h (k) (the "period" of the function) by performing function evaluation for different values of x.
To find h (k) with probability, say, 2 3 , f k (x) must be computed the order of 2 n 3 times in the classical case, the order of 3n times in the quantum case. There is an exponential speed up (Simon, 1994).
We give directly the extension of the quantum algorithm to the representation of the choice of the function on the part of the oracle. The black box, given the inputs k and x, computes f (k, x) = f k (x). The oracle's choice register K is 2 n (n − 1) qubit. The query register X is n qubit. The output register V is n − 1 qubit. The algorithm consists of three steps: (0) prepare register K in an even weighted superposition of all the possible values of k, register X in the even weighted superposition of all the possible values of x, and register V in the all zeroes string |0 V , (1) perform function evaluation, which changes the content of V from v (an n − 1 bit string) to v ⊕ f (k, x), where ⊕ denotes bit by bit module 2 addition, and (2) apply the Hadamard transform to register X.
The initial state is (11) Function evaluation yields (12) Applying the Hadamard transform to register X yields (13) Backdating to before running the algorithm the state reduction induced by measuring [K] gives the original Simon's algorithm -it generates at random the value of k hosted in the black box.
As one can see (equation 13), for each pair of complementary values of the oracle's choice (e. g. for register K in |0011 K + |1100 K ) and for each value of f k (x) (e. g. for register V in |0 V ), register X hosts an even weighted superposition (e. g. |00 X +|10 X ) of the 2 n−1 strings s (k) j (j = 0, 1, ..., 2 n−1 −1) "orthogonal" to the hidden string h (k) (if we multiply bit by bit two orthogonal strings and take the module 2 addition of the product bits, the result is zero) -00 and 10 are the two strings orthogonal to the hidden strings h (0011) = h (1100) = 01. Note that, in (13), only the phase of the terms of this superposition depend on the value of f k (x). Therefore, by measuring [K] and [X] in (13), we obtain at random the oracle's choice k and one of the s (k) j orthogonal to h (k) . At this point, we leave register K in its after-measurement state, so that the value of k remains fixed, and iterate the right part of the algorithm (initial preparation of registers X and V , function evaluation, Hadamard transform on (k) j . This allows to find h (k) by solving a system of n−1 module 2 linear equations. If the algorithm is iterated, say, 3n times, the probability of obtaining n − 1 different h (k) j , thus of finding the solution, is 2 3 . The probability of not finding the solution goes down exponentially with the number of iterations.

Checking the 50% rule
For the sake of simplicity, we reformulate Simon's problem as the problem of generating at random a string s (k) j orthogonal to h (k) -rather than finding the hidden string h (k) . Any s (k) j is thus a "solution of the problem". For what concerns the character of the speed up, the two formulations are equivalent: an exponential speed up in the former implies an exponential speed up in the latter and vice-versa.
The information acquired by measuring [K] and [X] in (13) is the information in the structured bit string k, the table of the function f k (x) -since the content of X (the string s (k) j ) is a function of the content of K, the information contained in X is redundant. As one can check, e. g. in table (10), 50% of the information in k is represented by the half tables that do not contain a same value of the function twice (which already identifies the period and thus any s With this definition of the advanced information, the solution is always identified by computing an extra row, namely by performing one function evaluation for any value of x outside the advanced information (because of the structure of the problem, the new value of the function is necessarily a value already present in the advanced information).
This verifies the 50% rule for Simon's algorithm. This rule shows that Simon's problem is solvable with an exponential speed up independently of our knowledge of the quantum algorithm -the speed up comes from comparing two classical algorithms, with and without the advanced information.
One can readily see that the same holds by similarity for the generalized Simon's algorithm, thus for the hidden subgroup algorithms (Mosca and Ekert, 1999), like finding orders, finding the period of a function (the quantum part of Shor's factorization algorithm), finding discrete logarithms, etc. (e. g., Kaye et al., 2007).

Building the quantum algorithm out of the advanced information classical algorithm
The function evaluation stage of the quantum algorithm -namely the transformation of Ψ 0 (equation 11) into Ψ 1 (equation 12) -is the sum of the histories of the advanced information classical algorithm (the rationale is the same of sections 2.3 and 3.3).
We justify the choice of the initial state of V . We start with the generic initial state α |0 V + β |1 V (α is thus the initial phase of the histories beginning with |0 V , etc.). Under α, we obtain the transformation of Ψ 0 (equation 11) into Ψ 1 (equation 12). Under β, we obtain the same result with |0 V and |1 V interchanged. Since we are interested in the superposition hosted in register X, which is the same in either case, we can suppress either α or β.
We examine the outcome of function evaluation, namely Ψ 1 (equation 12). This time the entanglement between registers K and X is not maximal. We know that function evaluation moves to register X information about the oracle's choice, but we do not know which is this information. The Hadamard transform on register X can still be defined as the rotation of the X basis that maximizes the information about the oracle's choice readable in it. However, this is no more a constructive definition, we are left with the problem of discovering that this information is a string orthogonal to h (k) .

Reviewing and extending the algorithm
The problem addressed by Grover's algorithm (Grover, 1996) is data base search. We deal with the set of the Kronecker functions δ (k, x), where k ≡ k 0 , k 1 , ..., k n−1 is an n bit string belonging to {0, 1} n . The oracle chooses one of these functions -chooses the data base location k -and gives to the second player the black box hardwired for the computation of that function. The second player has to find the value of k by computing δ (k, x) for different values of x. In the classical case δ (k, x) must be computed O (2 n ) times, in the quantum case O 2 n/2 times. There is a quadratic speed up.
We give directly the extension of the quantum algorithm to the representation of the choice of the function on the part of the oracle. The black box, given the inputs k and x, computes δ (k, x). The n qubit register K contains the bit string k -the data base location chosen by the oracle. The query register X is n qubit. The output register V is one qubit. The algorithm consists of three steps: (0) prepare register K in an even weighted superposition of all the possible values of k, register X in the even weighted superposition of all the possible values of x, and register V in the antisymmetric state, (1) perform function evaluation, which changes the content of V from v to v ⊕ δ (k, x), and (2) apply the transformation U (see further below) to register X.
We start with n = 2, then generalize to n > 2. The initial state is: (14) Function evaluation yields: This is four orthogonal states of K correlated with four orthogonal states of X. Applying to register X the Hadamard transform, then the transformation obtained by computing δ (0, x), then another time the Hadamard transform (for short, applying the transformation U ) yields: namely an entangled state where each value of k is correlated with the corresponding solution found by the second player (the same value of k but in register X). The final measurement of [K] and [X] in state (16) determines the moves of both players, the oracle's choice (the value of k) and the solution provided by the second player. The reduction induced by measuring [K], backdated to before running the algorithm, yields the original Grover's algorithm.

Checking the 50% rule
The information acquired in the final measurement of [K] and [X] in (16) is the two bits of the unstructured bit string k -since the content of X is a function of the content of K the information contained in X is redundant. The quantum algorithm requires the number of function evaluations of a classical algorithm working on a solution space reduced in size because one bit of k, either k 0 or k 1 , is known in advance. To identify the missing bit, the classical algorithm has to perform just one function evaluation -for example, if the advanced information is k 0 = 0 , it should compute δ (k, x) for either x = 00 (if δ (k, 00) = 1 then k 1 = 0 if δ (k, 00) = 0 then k 1 = 1 ) or x = 01 (if δ (k, 01) = 1 then k 1 = 1 if δ (k, 01) = 0 then k 1 = 0 ). This verifies the 50% rule for n = 2.
More in general, a classical algorithm that knows in advance 50% of the n bits that specify the data base location, in order to identify the n/2 missing bits should perform O 2 n/2 function evaluations, against the O (2 n ) of a classical algorithm without advanced information. This verifies the 50% rule for n > 2.
This rule says that unstructured data base search is solvable with a quadratic speed up independently of our knowledge of the quantum algorithm. The speed up comes by comparing two classical algorithms, with and without the advanced information.

Building the quantum algorithm out of the advanced information classical algorithm
The function evaluation stage of the quantum algorithm -namely the transformation of Ψ 0 (equation 14) into Ψ 1 (equation 15) -is the sum of the histories of the advanced information classical algorithm (see section 2.3). The choice of the initial phase of each history is justified as in Deutsch's algorithm.
We examine the outcome of the function evaluation stage, namely Ψ 1 (equation 15). Registers K and X are maximally entangled, orthogonal states of K, each corresponding to a value of k, are correlated with orthogonal states of X. This means that the value of k has propagated to register X. To read this value, we should rotate the X basis in such a way that − |00 X + |01 X + |10 X + |11 X (correlated with |00 K ) goes into |00 X , etc. This is a constructive definition of the transformation U .
Generalizing to n > 2 is straightforward. Given the advanced knowledge of n/2 bits, in order to compute the missing n/2 bits we should perform function evaluation and rotate the basis of X an O 2 n 2 times. The first time we obtain a superposition of an unentangled state of the form (14) (the initial state transformed into itself with a slightly smaller amplitude) and a maximally entangled state of the form (16). At each successive iteration, the amplitude of the latter state is amplified at the expense of the amplitude of the former, until it becomes about 1 in O 2 n 2 iterations.

Conclusions
We have verified that the 50% rule, the fact 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, holds for the main quantum algorithms.
This rule, besides shading light on the nature of quantum computation, brings the search of the problems solvable with a quantum speed up to an entirely classical framework. The quantum speed up comes out by comparing two classical algorithms, with and without the advanced information. In hindsight, one can see that the existing speed ups are skillfully designed around the 50% rule. This rule can be used for a systematic exploration of the possibility of achieving speed ups, perhaps to explain why the speed ups discovered until now are so few. Once identified a problem solvable with a speed up, the same rule can be used a second time for the search of the quantum algorithm that solves the problem. In fact the advanced information classical algorithm defines the quantum algorithm.
The 50% rule establishes a correspondence between quantum computation and classical computation with advanced information. It is natural to ask ourselves whether, in some more general sense, quantum mechanics is classical mechanics with advanced information. This question would deserve further investigation.