#  Unobservable causal loops explain both the quantum computational speedup
and quantum nonlocality

G. Castagnoli111 Formerly: Quantum Optics Laboratory and ICT Division of Elsag
Bailey, now part of the Leonardo Company. Email<EMAIL_ADDRESS>
###### Abstract

We consider the reversible process between two one-to-one correlated
measurement outcomes common to both the quantum computational speedup and
quantum nonlocality. The two outcomes are the setting and the solution of the
problem and respectively the outcomes of measuring in the same basis two
maximally entangled observables in a state of spatial separation of the
respective subsystems. Of course the ordinary quantum description of a
reversible process leaves the direction of causality unspecified. We show that
for this reason it is incomplete. It allows causal structures that ensure the
correlation between the two measurement outcomes that violate the time
symmetry required from the description of a reversible process. This also says
that the process description can be completed by time-symmetrizing it. Doing
this leaves the description unaltered, as it should be, but shows that it is
the quantum superposition of unobservable time-symmetrization instances whose
causal structure is completely specified. Both the speedup and nonlocality are
explained by the fact that each of these instances hosts a causal loop. The
speedup is due to the fact that the final measurement of the solution
retrocausally tells the problem solver half of the information about the
solution she will produce in the future. She can use this knowledge to produce
the solution with fewer computation steps (oracle queries). Nonlocality to the
fact that the measurement on either subsystem retrocausally and locally
changes the state of both subsystems when the two were not spatially separate.

##  1 Extended summary

The need of completing the quantum description has been put forward by
Einstein, Podolsky and Rosen in their famous EPR paper $\left[1\right]$. The
description would have been incomplete because it mathematically predicts the
action at a distance that characterizes quantum nonlocality but does not
explain it physically. The present work revives their argument in today’s
context. We refer in particular to Costa de Beauregard retrocausal explanation
of quantum nonlocality $\left[2\right]$, Bell’s inequality $\left[3\right]$,
time-symmetric $\left[4-10\right]$ and relational $\left[11,12\right]$ quantum
mechanics, and the discovery of the quantum computational speedup
$\left[13\right]$. The speedup is not unrelated. Of course the quantum
description mathematically predicts the speedup, quantum algorithm by quantum
algorithm, but – as we will see – it cannot highlight its constant physical
reason, which by the way is the same of nonlocality.

The unconventional character of this work justifies choosing the extended
summary form. As we will move in unexplored waters, we will try to provide our
line of thinking in the most tangible way possible.

Both the speedup and nonlocality reside in a reversible process between two
one-to-one correlated measurement outcomes. These are the setting and solution
of the problem222 To start with, we assume that the solution is an invertible
function of the problem-setting and is obtained with probability $1$. and
respectively the outcomes of measuring in the same basis two maximally
entangled observables in a state of spatial separation of the respective
subsystems. Note that the process between the two outcomes is reversible in
spite of comprising the final measurement. Since the latter selects a
measurement outcome entirely correlated with that of the initial measurement,
no information is lost in it.

The ordinary quantum description of this kind of process – a unitary evolution
– of course does not specify the time-direction of causality. This allows two
possible interpretations of it:

(i) The information that specifies the sorted out pair of outcomes, among all
the possible equiprobable pairs, is all selected by the initial measurement.
The corresponding measurement outcome unitarily propagates toward the final
measurement until becoming its outcome. The final measurement selects no
information. The initial measurement outcome is the cause and the final one
the effect. This is of course the usual interpretation of the ordinary quantum
description.

(ii) Time-symmetrically, the information in question is all selected by the
final measurement. The corresponding measurement outcome unitarily propagates
(by the inverse of the time-forward transformation) toward the initial
measurement until becoming its outcome. The initial measurement selects no
information. The final measurement outcome is the cause, the initial one the
effect.

We argue that either interpretation, introducing a preferred time-direction of
causality, violates the time-symmetry that should be required from the
description of a reversible process. This is where our line of thinking begins
to diverge from the conventional one.

Of course, if (i) and (ii) were the only possible interpretations of the
ordinary quantum description, there would be no way out. One would be forced
to make a virtue out of necessity. Apparently, this is what has happened so
far. By the way, the quantum description remains the same in either
interpretation – the same input and output states and unitary transformation
in between. One might therefore think that both the freedom that the ordinary
quantum description leaves to the direction of causality and the present
criticism are practically insignificant. However, we show that the quantum
processes we are dealing with offer a way out that has instead very
significant consequences.

To see it, it suffices to go from causality between the two full outcomes to
the causations between corresponding parts of the two outcomes, namely any
part of the initial outcome and the part of the final outcome one-to-one
correlated with it. Of course also in this case the ordinary quantum
description describes the correlation, but leaves the direction of the
causation free to go from the initial to the final outcome or vice-versa.

The point is that, in the case of disjoint pairs of corresponding parts of the
two outcomes, the ordinary quantum description allows that, in each pair, the
direction of the causation is freely chosen independently of that of the other
pair. There are two consequences: (i) the number of the structures of the
causations between corresponding parts of the two outcomes allowed by the
ordinary quantum description is exponential in outcomes size and (ii) unless
the directions of the causations are all the same, part of the information
that specifies the sorted out pair of outcomes is selected by the initial
measurement and the complementary part by the final measurement. Of course,
the information selected by either measurement – the corresponding measurement
outcome – propagates toward the other measurement according to the unitary
transformation in between.

According to our previous argument, if the initial and final measurements do
not evenly contribute to the selection of the sorted out pair of outcomes,
this is a violation of the time-symmetry required from the description of a
time-reversible process. This obviously brings us to these two considerations:
(i) the ordinary quantum description, which allows such violations, is
incomplete and (ii) it is completed simply by asking that the selection of the
information that specifies the pair of outcomes evenly shares between the
initial and final measurements. In other words, we should time-symmetrize the
ordinary quantum description.

This is naturally the way out we were looking for – made available by the fact
of having passed from causality between the full outcomes to the causations
between their corresponding parts. Since there is a plurality of ways of
evenly sharing between the two measurements the selection of the information
about the pair of outcomes, we should take their quantum superposition.

This time-symmetrization of the ordinary quantum description has an important
consequence. It leaves the ordinary quantum description unaltered, as it
should be: being the description of a reversible process, it has to be
invariant under time-symmetrization. However, at the same time, it shows that
this description is a quantum superposition of unobservable time-
symmetrization instances whose causal structure is completely specified333 Up
to an inversion of all the causation directions together. However, this just
provides the mirror image of the causal structure and is irrelevant. .

These instances are unobservable since an observer external to the quantum
system, the ordinary observer of the Copenhagen interpretation, cannot say
whether the initial measurement outcome, or part of it, has been selected by
that very measurement or is the backwards in time propagation of a selection
performed by the final measurement. A similar discourse holds for the final
measurement outcome.

In each time-symmetrization instance, the initial measurement selects a well
defined half of the information that specifies the pair of measurement
outcomes. The corresponding measurement outcome runs forward in time the
unitary transformation that physically connects the two measurements until
becoming the state immediately before the final measurement. The latter
completes the selection of the information about the pair of outcomes. The
resulting measurement outcome runs backwards in time the inverse of the time-
forward unitary transformation until becoming the state immediately after it
(we make reference to the ordinary direction of time). The latter propagation,
which inherits both selections, is an instance of the time symmetrized
process.

In each instance, the ordinary quantum description changes. The unitary
transformation between the initial and final measurement outcomes remains of
course the same, but the two outcomes change.

Completed in this way, the quantum description acquires a superior explanatory
power of what goes on inside the quantum process. It immediately explains both
the quantum speedup and quantum nonlocality. It shows that both rely on
unobservable causal loops: a quantum measurement that retrocausally changes
the input state of the unitary transformation that leads to the state
immediately before it. Naturally, such loops cannot be seen in the ordinary
quantum description, which leaves the direction of causality free, or in its
usual interpretation, which excludes retocausality.

In the speedup case, the causal loop is as follows. In any time-symmetrization
instance, the projection of the quantum state due to the final measurement of
the solution (which selects half of the information about it or, identically,
about the pair of outcomes) propagates backwards in time along the unitary
part of the quantum algorithm until changing the initial state of knowledge of
the solution on the part of the problem solver. From complete ignorance of the
solution, it becomes knowledge of half of the information about it. All is as
if the problem solver knew in advance half of the information about the
solution she will produce in the future and could use this knowledge to
produce the solution with a quantum computational speedup.

This also tells us the number of oracle queries (computation steps) required
to solve an oracle problem in an optimal quantum way444 We will explain in
Section 2 what oracle queries and oracle problems are. For the time being, we
can see them just as computation steps and problems. . It is that logically
(classically) required to find the solution given the advanced knowledge of
half of the information about it. Of course this is a synthetic solution (i.e.
axiomatically derived from fundamental principles) of the well known quantum
query complexity problem, which is central to quantum computer science and
still unsolved in the general case.

In the nonlocality case, the causal loop is as follows. In any time-
symmetrization instance, the projection of the quantum state of either
subsystem, due to the measurement performed on it when the two are space-
separate, runs backwards in time the unitary transformation that spatially
separates the two subsystems until changing the state of both subsystems at
the time they were not space-separate. The changed state, going forward in
time, at the time the two subsystems are space-separate locally emulates
quantum nonlocality. There are two causal loops, one for each measurement.
Together, they ensure the correlation between the two full measurement
outcomes.

Of course, all the above calls into play retrocausality, whose capability of
changing the past leads to well-known paradoxes. In this regard, we should
note that the quantum form of retrocausality generated by the present time-
symmetrization formalism – TS formalism in the following – has both a
justification and a remedy. The justification is that it is generated by the
legitimate time-symmetrization of the quantum description of a reversible
process. The remedy is that the change of a past quantum state remains
confined within the unobservable time-symmetrization instances and vanishes in
their quantum superposition, that is in the ordinary quantum description. In
fact, we will see that the quantum superposition of all the changed states is
the unchanged state of the ordinary quantum description. In other words, the
quantum form of retrocausality we are dealing with does not change the past
described by the ordinary quantum description.

This work is a further advancement of the theory of the quantum computational
speed developed in $\left[14-17\right]$. In these works, the time-
symmetrization of the quantum algorithm was a legitimate operation that
explained the quantum speedup. Now we are dealing with a generalization
thereof, namely with the time-symmetrization of the ordinary quantum
description of an important class of quantum processes. This highlights the
existence of an unsuspected quantum effect hidden within quantum correlation:
unobservable causal loops that exactly explain both the quantum speedup and
quantum nonlocality.

We are dealing with a new and more complete way of describing quantum
processes that, unlike their ordinary quantum description alone, highlights
the causal structure hidden in them. It could be considered a paradigm shift
in the way of describing quantum processes.

In sections 2 and 3 we apply the TS formalism to respectively the quantum
speedup and quantum nonlocality. Section 4 is a discussion: the TS formalism
requires some changes in the way of seeing a number of fundamental issues.
Section 5 gives the conclusions.

##  2  Applying the time-symmetrization formalism to the quantum computational
speedup

This section is a revisitation of the explanation of the quantum computational
speedup provided in $\left[17\right]$.

Before proceeding, let us explain what is an oracle problem and an oracle
query in the present context. An oracle is a black box that computes a
function, for example the Kronecker delta. The oracle problem is finding a
characteristic of that function, for example the argument for which the delta
function is $1$. Alice, the problem solver, gives the oracle a value of the
argument of the function; in jargon, she performs an oracle query. The oracle
gives her back the corresponding value of the function. The all procedure
counts for a single computation step, or oracle query. The number of oracle
queries needed to solve an oracle problem in an optimal quantum way is its
quantum computational complexity.

It is natural to think that, in order to understand what happens in a quantum
process, one must have a description of the same as complete as possible. With
respect to the usual description of quantum algorithms, which is limited to
the process of solving the problem, this means physically describing: (1) also
the process of setting the problem and consequently (2) the fact that the
problem-setting should be hidden from the problem solver – otherwise it would
tell her the solution of the problem before she begins her problem-solving
action. Only after these two completions of the object of the description, we
will complete the description itself by applying the TS formalism to it – this
is step (3).

###  2.1 Step 1 – extending the physical description to the process of setting
the problem

Let us consider the simplest instance of the oracle problem solved by Grover
algorithm $\left[18\right]$ – Grover’s problem from now on. Bob hides a ball
in one of four drawers. Alice is to locate it by opening drawers. In technical
jargon, opening drawer number $a$ amounts to querying the oracle with the
question: is the ball in drawer $a$ ? The oracle computes the Kronecker
function $\delta\left(b,a\right)$, where $b$ is the number of the drawer with
the ball, and of course gives back $1$ if $a=b$ and $0$ otherwise. As well
known, the simplest instance of Grover algorithm always yields the solution of
the problem – locates the ball – with just one oracle query, performed in a
quantum superposition of all the possible drawer numbers. Since in the
classical case it may be necessary to perform up to three queries, there is a
quantum computational speedup.

The usual description of quantum algorithms is limited to Alice’s problem-
solving action. We extend it to Bob’s action of setting the problem.

Let us introduce the notation first:

We number the four drawers in binary notation: $00,01,10,11$.

A quantum register $B$, under the control of the problem setter Bob, is meant
to contain the problem-setting  $b\text{}$ (the number of the drawer with the
ball). Its basis vectors are thus:
$|00\rangle_{B},|01\rangle_{B},|10\rangle_{B},|11\rangle_{B}$.

A quantum register $A$, under the control of the problem solver Alice, is
meant to contain $a$, the number of the drawer that Alice wants to open ; it
will eventually contain the solution of the problem – the number of the drawer
with the ball $b$ . Its basis vectors are thus:
$|00\rangle_{A},|01\rangle_{A},|10\rangle_{A},|11\rangle_{A}$.

Let the observable $\hat{B}$, of eigenstates/eigenvalues respectively
$|00\rangle_{B},|01\rangle_{B},|10\rangle_{B},|11\rangle_{B}$ / $00,01,10,11$,
be the number contained in register $B$, the observable $\hat{A}$, of
eigenstates/eigenvalues respectively
$|00\rangle_{A},|01\rangle_{A},|10\rangle_{A},|11\rangle_{A}$ / $00,01,10,11$,
the number contained in register $A$.

The process of setting and solving the problem is represented by the following
table (from now on we disregard normalization):

$\begin{array}[]{ccc}\begin{array}[]{c}\;\text{time }t_{1}\text{, meas.
of}\;\hat{B}\end{array}&t_{1}\rightarrow t_{2}&\text{time }t_{2}\text{, meas.
of}\;\hat{A}\\\ &&\\\
\left(|00\rangle_{B}+|01\rangle_{B}+|10\rangle_{B}+|11\rangle_{B}\right)|00\rangle_{A}&&\\\
\Downarrow&&\\\
|01\rangle_{B}|00\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(1)

We assume that, in the initial state, the number of the drawer with the ball
is completely indeterminate. This is represented by taking a uniform quantum
superposition of all the basis vectors of register $B$ – top-left corner of
the table. Register $A$ is initially in an arbitrary sharp state (standing for
a blank blackboard).

At time $t_{1}$, Bob measures $\hat{B}$ in the initial state. This projects
the initial superposition on an eigenstate of $\hat{B}$ selected at random,
say $|01\rangle_{B}$ (follow the vertical arrow on the left of the table). The
corresponding eigenvalue, $b=01$, is the problem-setting (here the number of
the drawer with the ball) selected by Bob. By the way, Bob could unitarily
change it into a desired number. For simplicity we disregard this operation.

We denote by $\hat{\mathbf{U}}_{1,2}$ the unitary part of Alice’s problem-
solving action. It sends the input state $|01\rangle_{B}|00\rangle_{A}$ into
the output state
$|01\rangle_{B}|01\rangle_{A}=\hat{\mathbf{U}}_{1,2}|01\rangle_{B}|00\rangle_{A}$,
which contains the solution in register $A$ – right looking horizontal arrows.

Of course $\hat{\mathbf{U}}_{1,2}$ can be the unitary part of Grover
algorithm, or even a less efficient quantum algorithm that solves Grover’s
problem. However, to us, it can remain an unknown unitary transformation. We
only need to know that there can be a unitary transformation between the input
and output states, what is always the case with this kind of representation
where the output has a full memory of the input. Note that the input and
output states of $\hat{\mathbf{U}}_{1,2}$ are known once the oracle problem –
the set of the problem-settings and the corresponding solutions – is known. In
other words, we are dealing with an external description of the quantum
algorithm that only depends on the oracle problem.

Eventually, at time $t_{2}$, Alice acquires the solution by measuring
$\hat{A}$. The output state of $\hat{\mathbf{U}}_{1,2}$, namely
$|01\rangle_{B}|01\rangle_{A}$, with register $A$ in an eigenstate of
$\hat{A}$, remains unaltered; there is in fact a unitary transformation
between the initial and final measurement outcomes; the process between them
is physically reversible as no information is lost along it.

###  2.2  Step 2 – relativizing the extended description to the problem solver

Register $B$ contains the problem-setting $b$. Its state represents the
observer’s knowledge of the problem-setting. Initially it represents complete
ignorance of it – see the top-left corner of table (1). After the initial
measurement of $B$ on the part of Bob, it represents full knowledge of it –
bottom-left corner of the table.

Therefore we can see that the description of table (1) works for Bob and any
external observer, not for Alice. Immediately after the initial measurement,
she would know the solution of the problem (the problem-setting and thus the
solution – both the number of the drawer with the ball) before she begins her
problem-solving action. To Alice, the problem-setting selected by Bob must be
hidden inside a black box.

To physically represent the concealment of the outcome of the initial
measurement from Alice (the observer of the final measurement), we must resort
to relational quantum mechanics $\left[11,12\right]$. In it, quantum states
are not absolute but relative to the observer. We relativize the description
of the quantum algorithm to Alice as follows.

To her, we postpone after the end of her problem-solving action the projection
of the quantum state associated with the initial measurement (note that
$\hat{B}$ and $\hat{A}$ commute). This is of course a mathematically
legitimate operation provided that the two ends of the projection undergo the
unitary transformation $\hat{\mathbf{U}}_{1,2}$ 555 Alternatively, we could
postpone at the end of Alice’s action the very measurement of $\hat{B}$: the
reduced density operator of register $B$ remains unaltered throughout the
unitary part of Alice’s action – see the input and output states of
$\hat{\mathbf{U}}_{1,2}$. .

While the description of the quantum algorithm with respect to Bob and any
external observer is that of the previous subsection, that with respect to
Alice becomes:

$\begin{array}[]{ccc}\begin{array}[]{c}\text{time}\text{ }t_{1}\text{, meas.
of}\;\hat{B}\end{array}&t_{1}\rightarrow
t_{2}&\text{\text{time}\text{}}t_{2}\text{, meas. of}\;\hat{A}\\\ &&\\\
\left(|00\rangle_{B}+|01\rangle_{B}+|10\rangle_{B}+|11\rangle_{B}\right)|00\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}\\\
&&\Downarrow\\\ &&|01\rangle_{B}|01\rangle_{A}\end{array}$ (2)

To Alice, the initial quantum superposition remains unaltered after the
initial Bob’s measurement – top-left corner of the table. It represents her
complete ignorance of the number of the drawer with the ball selected by Bob.
By $\hat{\mathbf{U}}_{1,2}$ (horizontal arrows), this superposition unitarily
evolves into the superposition of four tensor products, each the product of a
number of the drawer with the ball and the corresponding solution (that same
number but in register $A$). Eventually, the final measurement of $\hat{A}$
projects the latter superposition on $|01\rangle_{B}|01\rangle_{A}$, the
tensor product of the number of the drawer with the ball already selected by
Bob and the corresponding solution (vertical arrow). Note that this projection
is indifferently that due to the initial Bob’s measurement, postponed.

###  2.3  Step 3 – Completing the ordinary quantum description by time-
symmetrizing it

With probability one of reading the solution, there is the unitary
transformation $\hat{\mathbf{U}}_{1,2}$ between the initial and final
measurement outcomes. The process between them is reversible in spite of
comprising the final measurement since no information is lost along it.
Correspondingly, its ordinary quantum description leaves the direction of
causality unspecified. We time-symmetrize the description by imposing that the
initial and final measurements evenly contribute to the selection of the
information that specifies the sorted out pair of correlated measurement
outcomes (among all the equiprobable pairs). Since there is a plurality of
ways of evenly sharing the information in question, we should take their
quantum superposition.

We should assume that the initial measurement of $\hat{B}$ and the final
measurement of $\hat{A}$ in all the possible ways reduce to complementary
partial measurements that evenly and non-redundantly contribute to the
selection of the pair of outcomes.

For example, the initial measurement of $\hat{B}$ could reduce to that of
$\hat{B}_{l}$ (the left binary digit – bit – of the number in register $B$ )
and the final measurement of $\hat{A}$ to that of $\hat{A_{r}}$ (the right bit
of the number in register $A$). Or vice-versa, etc. Together, the measurement
of $\hat{B}_{l}$ at time $t_{1}$ and that of $\hat{A_{r}}$ at time $t_{2}$
select a well defined problem-setting, say it is $01$. How to arrange together
the selections performed by the two successive measurements is explained in
the next two sections.

####  2.3.1  Time-symmetrizing the description to Bob and any external
observer

The description of the quantum algorithm of table (1) is that with respect to
Bob and any external observer. We time-symmetrize it by the TS formalism. The
following zigzag diagram yields the time-symmetrization instance for
measurement outcome $b=01$, the measurement of $\hat{B}$ reduced to that of
$\hat{B}_{l}$, and the measurement of $\hat{A}$ to that of $\hat{A_{r}}$:

$\begin{array}[]{ccc}\begin{array}[]{c}\;\text{time }t_{1}\text{,
}\text{}\text{meas.
of}\;\hat{B}_{l}\end{array}&t_{1\rightleftarrows}t_{2}&\text{time
}\text{}t_{2}\text{, meas. of}\;\hat{A_{r}}\\\ &&\\\
\left(|00\rangle_{B}+|01\rangle_{B}+|10\rangle_{B}+|11\rangle_{B}\right)|00\rangle_{A}&&\\\
\Downarrow&&\\\
\left(|00\rangle_{B}+|01\rangle_{B}\right)|00\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}\\\
&&\Downarrow\\\
|01\rangle_{B}|00\rangle_{A}&\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(3)

The initial measurement of $\hat{B}_{l}$, selecting the $0$ of $01$, projects
the initial quantum superposition on the superposition of the terms beginning
with $0$ – vertical arrow on the left of the table. Under
$\hat{\mathbf{U}}_{1,2}$, the latter superposition evolves into the
superposition of the two products number of the drawer with the ball $\otimes$
corresponding solution – right looking horizontal arrows. Then the final
measurement of $\hat{A_{r}}$, selecting the $1$ of $01$, projects the
superposition in question on the term ending in $1$ (vertical arrow on the
right of the table). The backwards in time propagation of this output state by
$\hat{\mathbf{U}}_{1,2}^{{\dagger}}$, which inherits both selections, is an
instance of the time-symmetrized description of the quantum algorithm to Bob
and any external observer – bottom line of the table. Moreover, it is also the
superposition of all instances since their bottom lines are all identical to
each other. In fact one can see that the bottom line of the table remains the
same regardless of how we evenly share the selection between the initial and
final measurements. It is also identical to the bottom line of table (1),
namely to the ordinary description of the quantum algorithm, since the symbol
“ $\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow$ ” is of course
equivalent to “ $\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow$ ”. As
anticipated in the Introduction, the superposition of all the time-
symmetrization instances gives the ordinary quantum description back again –
in a trivial way in the present case.

The time-symmetrization of the quantum algorithm to Bob and any external
observer does not explain the quantum speedup. It anyway exemplifies how to
introduce the correct time-directions of the causations between corresponding
parts of the two measurement outcomes. This will explain the speedup in the
next subsection.

####  2.3.2  Time-symmetrizing the description to Alice

We time-symmetrize the description of the quantum algorithm with respect to
Alice of table (2). The following zigzag diagram is the time-symmetrization
instance for problem-setting $b=01$, the measurement of $\hat{B}$ reduced to
that of $\hat{B}_{l}$, and the measurement of $\hat{A}$ reduced to that of
$\hat{A_{r}}$:

$\begin{array}[]{ccc}\begin{array}[]{c}\;\text{time }t_{1}\text{, meas.
of}\;\hat{B}_{l}\end{array}&t_{1\rightleftarrows}t_{2}&\text{time
}t_{2}\text{, meas. of}\;\hat{A_{r}}\\\ &&\\\
\left(|00\rangle_{B}+|01\rangle_{B}+|10\rangle_{B}+|11\rangle_{B}\right)|00\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}\\\
&&\Downarrow\\\
\left(|01\rangle_{B}+|11\rangle_{B}\right)|00\rangle_{A}&\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow&|01\rangle_{B}|01\rangle_{A}+|11\rangle_{B}|11\rangle_{A}\end{array}$
(4)

The projection of the quantum state associated with the initial measurement of
$\hat{B}_{l}$ must be postponed after the end of Alice’s problem-solving
action – outside table (4) which is limited to this action. In fact any
information about the problem-setting must be hidden from her. The top line of
the diagram is thus the same of table (2). Then the measurement of
$\hat{A_{r}}$ in the output state of $\hat{\mathbf{U}}_{1,2}$, selecting the
$1$ of $01$, projects it on the superposition of the terms ending in $1$
(vertical arrow). The propagation of the latter superposition backwards in
time by $\hat{\mathbf{U}}_{1,2}^{{\dagger}}$ (left looking horizontal arrows),
which inherits both selections, is an instance of the time-symmetrized quantum
algorithm to Alice. See the bottom line of table (4), repeated here for
convenience:

$\begin{array}[]{ccc}\text{time }t_{1}&t_{1}\leftarrow t_{2}&\text{time
}t_{2}\\\ &&\\\
(|01\rangle_{B}+|11\rangle_{B})|00\rangle_{A}&\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow&|01\rangle_{B}|01\rangle_{A}+|11\rangle_{B}|11\rangle_{A}\end{array}$
(5)

Of course it can also be read the other way around as:

$\begin{array}[]{ccc}\text{time }t_{1}&t_{1}\rightarrow t_{2}&\text{time
}t_{2}\\\ &&\\\
(|01\rangle_{B}+|11\rangle_{B})|00\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|01\rangle_{B}|01\rangle_{A}+|11\rangle_{B}|11\rangle_{A}\end{array}$
(6)

By the way, let us say for completeness that the output state
$|01\rangle_{B}|01\rangle_{A}+|11\rangle_{B}|11\rangle_{A}$ will eventually be
projected on $|01\rangle_{B}|01\rangle_{A}$ by the projection due to the
initial measurement of $\hat{B}_{l}$ postponed after the end of Alice’s
action, outside table (4) which is limited to this action.

For $b=01$, there are in total three time-symmetrization instances. In each of
them, the problem-setting selected by Bob, $b=01$, pairs with another problem-
setting (it pairs with $b=11$ in the above instance). The superposition of all
instances, also for all the possible problem-settings, gives back the unitary
part of the original quantum algorithm to Alice666 In the quantum algorithm to
Alice, the problem-setting is selected only after the unitary part of Alice’s
problem-solving action. – table (2). Of course, the superposition of all the
pairs of basis vectors of register $B$ yields the superposition of all the
basis vectors.

In view of what will follow, let us note that a zigzag diagram of the kind of
table (4) could represent also uneven ways of sharing between the initial and
final measurements the selection of the information that specifies the two
correlated measurement outcomes.

####  2.3.3  Interpretation

Table (5), or identically (6), yields an instance of the time-symmetrization
of the extended representation of Grover algorithm with respect to Alice. From
now on we will refer to the latter table which is a more familiar description
of a quantum algorithm.

Note that, besides the element of a quantum superposition, each instance can
be seen itself as a full fledged quantum algorithm. In the instance we are
dealing with, it suffices to think that actually Bob measures $\hat{B}_{l}$ in
the initial state and Alice $\hat{A_{r}}$ in the output state of
$\hat{\mathbf{U}}_{1,2}$ – of course this selects the problem setting too.
Time-symmetrization in this case only consists in propagating forward in time
the selection due to the initial measurement and backwards in time that due to
the final measurement.

We should keep in mind that table (6) is the complete description of the
quantum algorithm with respect to Alice. As one can see, in it, the
computational complexity of Grover’s problem reduces. Alice’s problem is now
locating the ball hidden in the pair of drawers $\left\\{01,11\right\\}$ –
check the input and output states of $\hat{\mathbf{U}}_{1,2}$ in table (6).
Let us call it the reduced problem.

In equivalent terms, table (6) tells us that Alice, immediately after the
initial measurement, knows that the ball is in the pair of drawers
$\left\\{01,11\right\\}$. Note that, in the description of the quantum
algorithm with respect to her, the input state of register $B$ represents her
initial state of knowledge of the number of the drawer with the ball. From
knowledge that the ball is in one of four drawers (i.e. from complete
ignorance of the drawer number), it becomes knowledge that it is in one of two
drawers – compare the states in the top-left and bottom-left corners of table
(4). This is because Alice is shielded from the half information about the
number of the drawer with the ball coming to her from the initial measurement,
not from the half coming to her back in time from the final measurement.

Summing up, all is as if Alice knew one of the possible halves of the
information about the solution of the problem she will read in the future and
could use this information to reduce the computational complexity of the
problem to be solved. Below, we show that this allows to compute the number of
queries needed to solve Grover’s problem in an optimal quantum way (of course
without knowing the quantum algorithm).

The reduced problem, as any other problem, can always be solved quantumly with
the number of oracle queries required by a (reversible) classical algorithm –
i.e. logically required777 What face each other here are not quantum and
classical physics but quantum physics and classical logic. . The question then
becomes whether it could be solved with even fewer queries, namely itself with
a quantum speedup. Now, under the reasonable assumption that the quantum
speedup is essentially related to the reduction, under time-symmetrization, of
the computational complexity of the problem to be solved, the answer must be
negative. In fact, the quantum algorithm that solves the reduced problem has
been time-symmetrized already. Further time-symmetrizing it would leave it
unaltered without further reducing the computational complexity of the
problem888 We have seen that Bob and Alice can effectively perform the partial
measurements of the instance we are dealing with. Then time-symmetrization
consists in propagating forward in time the selection performed by Bob’s
measurement and backwards in time that performed by Alice’s measurement. Doing
this a second time changes nothing. .

Summing up, it turns out that the number of queries needed to solve Grover’s
problem in an optimal quantum way is that needed to solve the corresponding
reduced problem in an optimal logical (classical) way. In the present four
drawer instance of Grover’s problem, this is only one query. In fact, the
reduced problem, locating a ball hidden in a pair of drawers, can of course be
classically solved by opening either drawer. Note that we have found the
number of oracle queries needed to solve Grover’s problem in an optimal
quantum way without knowing Grover algorithm, namely $\hat{\mathbf{U}}_{1,2}$.

More in general, we should consider the generic number of drawers $N=2^{n}$,
where $n$ is the number of digits (bits) in the drawer number. Note that, in
the variant provided by Long $\left[19\right]$, Grover algorithm gives the
solution with certainty for any value of $N$. Everything we said for the four
drawers still holds.

Evenly sharing between the two measurements the selection of the $n$ bits that
specify the number of the drawer with the ball means ascribing to the final
measurement the selection of $n/2$ bits. Since Alice knows these bits in
advance, the reduced problem is locating the ball in $2^{n/2}$ drawers. It can
be solved logically (classically) with $\operatorname*{O}\left(2^{n/2}\right)$
queries. This is therefore also the number of queries needed to solve the
original Grover’s problem in an optimal quantum way.

Summarizing, the time-symmetrization formalism foresees that the number of
queries needed to solve Grover’s problem in an optimal quantum way is that
needed to solve the corresponding reduced problem in an optimal logical
(classical) way, namely $\operatorname*{O}\left(2^{n/2}\right)$ queries. Also
in the quantum case we must make reference to an optimal quantum algorithm
since a non optimal one could take any higher number of queries. That Grover’s
problem can be solved quantumly with any number of queries above that required
by the optimal Grover/Long algorithm has been shown in $\left[19,20\right]$.

All the above is in agreement with the fact that Grover algorithm (more
precisely Grover/Long algorithm) is demonstrably optimal $\left[19-21\right]$
and employs $\operatorname*{O}\left(2^{n/2}\right)$ queries $\left[18\right]$.

Let us eventually note that the present interpretation of the quantum speedup
ascribes it in the first place to a temporal form of nonlocality, namely to
the fact that the final measurement changes back in time the initial state of
knowledge of the problem-setting (and the consequent solution) on the part of
Alice.

####  2.3.4  From Grover’s problem to any oracle problem

It is easy to see that the method to compute the number of oracle queries
needed to solve Grover’s problem in an optimal quantum way immediately extends
to any oracle problem. It suffices to replace, in table (4), the input and
output states of Grover’s problem by their general definition, the one that
holds for any oracle problem. These are respectively the superposition of all
the problem-settings tensor product the blank blackboard and the superposition
of all the tensor products of each problem-setting and the corresponding
solution. In any case, the backwards in time propagation of the outcome of the
final partial measurement (the one that evenly contributes with the initial
measurement to the selection of the two correlated measurement outcomes)
changes these input and output states into those of the reduced problem. The
number of oracle queries needed to solve the reduced problem in an optimal
logical (classical) way is always the number needed to solve the original
problem in an optimal quantum way.

Let us now introduce a simplification. We go back to Grover’s problem and
table (4). We can see that the measurement of $\hat{A_{r}}$ in the final state
is equivalent to the measurement of $\hat{B}_{r}$ (the right bit of the number
in register $B$ ) in the same state. The latter in turn is equivalent to the
measurement of $\hat{B}_{r}$ in the initial state. In fact, by looking at the
form of the input and output of the unitary part of the quantum algorithm, we
can see that the reduced density operator of register $B$ remains unaltered
through it. In conclusion, measuring $\hat{A_{r}}$ in the final state is
equivalent to measuring $\hat{B}_{r}$ in the initial state.

Therefore the requirement of evenly sharing the selection of the pair of
correlated measurement outcomes between the initial and final measurements
becomes that of splitting the initial measurement into two partial
measurements that evenly and non redundantly contribute to selecting both the
problem-setting and the solution of the problem. Alice knows in advance the
information selected by either measurement. One can see that also this holds
for any oracle problem. Taking it into account yields the following advanced
knowledge rule:

We should split the initial measurement of the problem-setting in a state of
maximal indetermination of it into two partial measurements that evenly and
non-redundantly contribute to the selection of the problem-setting and the
corresponding solution. Alice knows in advance the information acquired by
either partial measurement. The number of queries needed to solve the oracle
problem in an optimal quantum way is that needed to solve it in an optimal
logical (classical) way given the advanced knowledge in question.

By the way, since we require that the two partial measurements evenly
contribute to the selection of both the problem-setting and the corresponding
solution, as shown in $\left[17\right]$ we can give up the requirement that
the solution is an invertible function of the problem-setting.

The rule in question quantitatively fits all the quantum algorithms examined:
those of Grover, Deutsch&Jozsa, Simon, Shor, and more in general the quantum
algorithms of the Abelian hidden subgroup $\left[17\right]$. As is well known,
these are the major quantum algorithms discovered until now and cover both the
quadratic and exponential speed ups.

##  3  Applying the time-symmetrization formalism to quantum nonlocality

We go now the quantum nonlocality of the EPR paradox $\left[1\right]$. Let us
consider the generation, by parametric down conversion at time $t_{0}$, of a
pair of photons in a state of maximally entangled polarizations – equation (7)
– and diverging velocities.

$\frac{1}{\sqrt{2}}\left(|0\rangle_{B}\left|1\right\rangle_{A}-|1\rangle_{B}\left|0\right\rangle_{A}\right).$
(7)

$B$ and $A$ are the photon labels and $0/1$ horizontal/vertical polarization.
Then, in the interval $\left(t_{0},t_{1}\right)$, the two photons get
spatially separate in a unitary way. Measuring, after their spatial
separation, the polarization of either photon of course instantly changes the
polarization state of the other photon. There is what Einstein, Podolsky, and
Rosen, in their famous EPR paper $\left[1\right]$ called the spooky action at
a distance. Eventually, if the polarization of the two photons are measured in
the same basis, there is one-to-one correlation between the two measurement
outcomes. The unitary evolution between them can go directly from $t_{1}$, the
time of the measurement of photon $B$ polarization, to $t_{2}$, the time of
the measurement of photon $A$ polarization, or – identically from the
mathematical standpoint – from $t_{1}$ to $t_{2}$ via $t_{0}$. In the latter
case, the first unitary evolution encountered goes backwards in time from
$t_{1}$ to $t_{0}$, the second forward from $t_{0}$ to $t_{2}$.

Note that the unitary transformation that connects the two measurement
outcomes via $t_{0}$ is local and thus physical, provided that we consider
retrocausality physical too. The one that goes directly from $t_{1}$ to
$t_{2}$ is nonlocal – it implies the spooky action at a distance and is
certainly unphysical.

In 1947, Costa de Beauregard $\left[2,22\right]$ explained the action at a
distance that characterizes quantum nonlocality by assuming a succession of
causations that are local but go first backwards in time from $t_{1}$ to
$t_{0}$ and then forward in time from $t_{0}$ to $t_{2}$.

Measuring the polarization of photon $B$ at time $t_{1}$, in causal order,
would change only its reduced density operator, say into
$\left|0\right\rangle_{B}\left\langle 0\right|_{B}$, leaving that of the other
photon unaltered. Then this result would propagate towards the other
measurement along the unitary evolution that physically (i.e. locally)
connects the two measurements, which in present assumptions necessarily goes
from $t_{1}$ to $t_{2}$ via $t_{0}$. First, by the inverse of the time forward
unitary evolution, it would go backwards in time from $t_{1}$ to $t_{0}$ until
locally changing, at time $t_{0}$, the polarization state of both photons into
$|0\rangle_{B}\left|1\right\rangle_{A}$. Then this state, still on its way
toward the other measurement, would propagate forward in time again until
becoming the state immediately before and after the measurement of photon $A$
polarization at time $t_{2}$. In particular, one can see that all is as if the
measurement of photon $B$ polarization at time $t_{1}$ instantly changed the
overall state of the two spatially separate photons into
$|0\rangle_{B}\left|1\right\rangle_{A}$, thus emulating action at a distance.

To explain quantum nonlocality by means of the TS formalism, we should evenly
share between the two measurements the selection of the single bit that
specifies the pair of correlated outcomes. To this end, we represent the
polarization state (7) in the redundant way:

$|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}.$
(8)

One can see that, if we take the XOR (exclusive OR) between the two bits of
each register, we obtain the state
$|0\rangle_{B}|0\rangle_{A}+|1\rangle_{B}|1\rangle_{A}$. If, in (8), we
changed the two central plus signs into minus signs, the represented state
would become $|0\rangle_{B}|0\rangle_{A}-|1\rangle_{B}|1\rangle_{A}$, which
can trivially be brought to state (7). However, we will do without these
changes that are irrelevant here since we never rotate any measurement basis.
Now the problem is the same as that of the simplest instance of Grover
algorithm: evenly sharing between the measurements of $\hat{B}$ and $\hat{A}$
the selection of the two bits that specify the pair of correlated outcomes.

To obtain the quantum nonlocality situation we should assume that: (i) at time
$t_{0}$, registers $B$ and $A$ are not yet spatially separate, so that the
change of the reduced density operator of one register locally projects the
state of both registers and (ii) in the time interval
$\left(t_{0},t_{1}\right)$, the two registers get space separate by the
unitary transformation $\hat{\mathbf{U}}_{0,1}$.

###  3.1  Costa de Beauregard’s explanation

First, we provide the ordinary description of quantum nonlocality, namely of
the fact that measuring the content of register $B$ at time $t_{1}$ instantly
changes the state of the two space separate registers $B$ and $A$. See the
following table:

$\begin{array}[]{ccc}\text{time }t_{1}\text{, }\text{}\text{meas.
of}\;\hat{B}&t_{1}\rightarrow t_{2}&\text{time
}t_{2}\text{}\text{}\text{}\text{, meas. of }\text{}\hat{A}\\\ &&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}&&\\\
\Downarrow&&\\\
|01\rangle_{B}|01\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(9)

At time $t_{1}$, the measurement of $\;\hat{B}$ (the content of register $B$)
in the entangled state in the top-left of the table selects at random, say,
the eigenvalue $b=01$ projecting the state of the two registers on
$|01\rangle_{B}|01\rangle_{A}$ (vertical arrow). The fact that this
measurement instantly changes also the state of the space separate register
$A$ is of course the “spooky action at a distance”. The measurement outcome
$|01\rangle_{B}|01\rangle_{A}$, by the unitary transformation
$\hat{\mathbf{U}}_{1,2}$, directly (not via $t_{0}$) propagates to immediately
before the measurement of $\text{}\hat{A}$ (the content of register $A$) at
time $t_{2}$ (horizontal arrows). Then the latter measurement
deterministically acquires the correlated eigenvalue $a=01$.

The following table provides the quantum process corresponding to Costa de
Beauregard’s explanation of quantum nonlocality $\left[2,22\right]$. Formally,
it suffices to apply to the description of table (9) the mathematical identity
$\hat{\mathbf{U}}_{1,2}=\hat{\mathbf{U}}_{1,0,2}$ , where
$\hat{\mathbf{U}}_{1,0,2}=\hat{\mathbf{U}}_{0,2}\hat{\mathbf{U}}_{0,1}^{{\dagger}}$.
Here $\mathbf{U}_{0,1}$ is the unitary transformation undergone by the quantum
system between $t_{0}$ and $t_{1}$ and $\hat{\mathbf{U}}_{0,2}$ that between
$t_{0}$ and $t_{2}$. The result is trivially:

$\begin{array}[]{ccc}\text{time }t_{1}\text{, }\text{}\text{meas.
of}\;\hat{B}&t_{1}\rightarrow t_{0}\rightarrow t_{2}&\text{time }t_{2}\text{,
mes. of }\text{}\hat{A}\\\ &&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}&&\\\
\Downarrow&&\\\
|01\rangle_{B}|01\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,0,2}\Rightarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(10)

The only difference with respect to table (9) is that now the outcome of
measuring $\;\hat{B}$ at time $t_{1}$ unitarily propagates to $t_{2}$ via
$t_{0}$. First it propagates backwards in time – by
$\hat{\mathbf{U}}_{0,1}^{{\dagger}}$ – to $t_{0}$. Then it propagates forward
in time – by $\hat{\mathbf{U}}_{0,2}$ – to $t_{2}$, becoming the state
immediately before the measurement of $\text{}\hat{A}$.

The point is that table (10) hosts Costa de Beauregard’s explanation of
quantum nonlocality. One should assume that, in causal order, the measurement
of $\;\hat{B}$ at time $t_{1}$ only projects the reduced density operator of
register $B$ on $\left|01\right\rangle_{B}\left\langle 01\right|_{B}$, leaving
that of register $A$ unaltered. Then this reduced density operator, by
$\hat{\mathbf{U}}_{0,1}^{{\dagger}}$, propagates backwards in time from
$t_{1}$ to $t_{0}$, where it locally projects the original entangled state on
the sharp state $|01\rangle_{B}|01\rangle_{A}$. Eventually the latter state,
by $\hat{\mathbf{U}}_{0,2}$ , propagates forward in time from $t_{0}$ to
$t_{2}$. Note that, under this interpretation, the fact that the measurement
of$\;\hat{B}$ at time $t_{1}$ instantly changes also the state of the space
separate register $A$ is, so to speak, a coincidence. It does change the state
of register $A$, but locally, through the unitary propagation that first goes
backwards in time from $t_{1}$ to $t_{0}$, then forward in time from $t_{0}$
to $t_{1}$. This is what creates the semblance of action at a distance.

As is well known, Costa de Beauregard’s explanation received little attention
by the community of physicists in general $\left[15\right]$. It is difficult
to say why because one should explain silence. Likely, the notion that
causality can go backwards in time, even along the objectively ideal
reversible processes of quantum mechanics, is hardly accepted. In the next
subsection, we will rebuild a similar explanation by means of the TS
formalism.

###  3.2  Application of the time-symmetrization formalism

First, we apply the time-symmetrization (TS) formalism to the usual
description of quantum nonlocality of table (9), where the outcome of the
first measurement directly propagates to immediately before the second
measurement. Note that we are dealing with a description with respect to any
observer. We do not have to hide anything from anyone here. We consider the
time-symmetrization instance where the sorted out value of the two correlated
measurement outcomes is $01$ , the measurement of $\hat{B}$ at time $t_{1}$
reduces to that of $\hat{B}_{l}$ (the left bit of the number contained in
register $B$ ) and the measurement of $\hat{A}$ at time $t_{2}$ to that of
$\hat{A_{r}}$ (the right bit of the number in register $A$). The corresponding
zigzag diagram is:

$\begin{array}[]{ccc}\text{time }t_{1}\text{, }\text{}\text{meas. of
$\hat{B}_{l}$}&t_{1}\rightleftarrows t_{2}&\text{time }t_{2}\text{,
}\text{}\text{meas. of}\text{$\hat{A_{r}}$}\\\ &&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}&&\\\
\Downarrow&&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow&|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}\\\
&&\Downarrow\\\
|01\rangle_{B}|01\rangle_{A}&\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(11)

The measurement of $\hat{B}_{l}$ at time $t_{1}$ projects the initial state
superposition (top-left of the table) on the superposition of the terms
beginning with $0$ (vertical arrow on the left of the table). The latter
superposition, by $\hat{\mathbf{U}}_{1,2}$, propagates to $t_{2}$ (right
looking horizontal arrows), where the measurement of $\hat{A_{r}}$ projects it
on the sharp state $|01\rangle_{B}|01\rangle_{A}$ ending with $1$ (vertical
arrow on the right of the table). This measurement outcome, by
$\hat{\mathbf{U}}_{1,2}^{{\dagger}}$, propagates backwards in time to $t_{1}$
(left looking horizontal arrows). The propagation in question, which inherits
both selections, is both a time-symmetrization instance and the superposition
of all instances for measurement outcome $01$ – the bottom lines of all these
instances being identical to each other. They are also identical to the
ordinary quantum description – bottom line of table (9) – since “
$\Leftarrow\hat{\mathbf{U}}_{1,2}^{{\dagger}}\Leftarrow$ ” is equivalent to “
$\Rightarrow\hat{\mathbf{U}}_{1,2}\Rightarrow$ ”.

Now we apply the TS formalism to the description of the quantum process that
goes from $t_{1}$ to $t_{2}$ via $t_{0}$. It suffices to replace, in table
(11), $\hat{\mathbf{U}}_{1,2}$ by the mathematically identical
$\hat{\mathbf{U}}_{1,0,2}$. This yields:

$\begin{array}[]{ccc}\text{time }t_{1}\text{, }\text{}\text{meas. of
$\hat{B}_{l}$}&t_{1}\rightleftarrows t_{0}\rightleftarrows t_{2}&\text{time
}t_{2}\text{, }\text{}\text{meas. of}\text{$\hat{A_{r}}$}\\\ &&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}+|10\rangle_{B}|10\rangle_{A}+|11\rangle_{B}|11\rangle_{A}&&\\\
\Downarrow&&\\\
|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}&\Rightarrow\hat{\mathbf{U}}_{1,0,2}\Rightarrow&|00\rangle_{B}|00\rangle_{A}+|01\rangle_{B}|01\rangle_{A}\\\
&&\Downarrow\\\
|01\rangle_{B}|01\rangle_{A}&\Leftarrow\hat{\mathbf{U}}_{1,0,2}^{{\dagger}}\Leftarrow&|01\rangle_{B}|01\rangle_{A}\end{array}$
(12)

Of course, also in this case the bottom lines of the time-symmetrization
instances are all identical to each other, and to that of the ordinary quantum
description of table (10), as we can replace “
$\Leftarrow\hat{\mathbf{U}}_{1,0,2}^{{\dagger}}\Leftarrow$ ” by “
$\Rightarrow\hat{\mathbf{U}}_{1,0,2}\Rightarrow$ ”. The important point is
that both reduced density operators, that of register $B$ after the
measurement of $\hat{B}_{l}$ and that of register $A$ after the measurement of
$\hat{A_{r}}$, in their propagation toward the other measurement go via
$t_{0}$. At time $t_{0}$ they locally project the state of the entire quantum
system. Also the present zigzag diagram hosts the local explanation of spatial
nonlocality.

One might wander how the reduced density operator of either register “knows”
that it has to propagate to the other measurement via $t_{0}$. We have a
simple answer to this question: it propagates in all the possible ways. In the
case that it goes from $t_{1}$, or from $t_{2}$, to $t_{0}$, at time $t_{0}$
it locally changes the state of both registers. In all the other cases it
changes nothing. This is why we can focus only on the propagation that
physically connects the two measurement outcomes via $t_{0}$.

Eventually, let us note that what explains spatial nonlocality is in the first
place a temporal form of nonlocality: the fact that the two measurements, at
times $t_{1}$ and $t_{2}$, change back in time the state of the two registers
at time $t_{0}$.

By the way, it can be interesting to note that the present time-symmetrized
description of quantum nonlocality is the only possible – symmetric – way of
seeing the causations that ensure the correlation between the two outcomes
when the respective measurements become simultaneous – when $t_{1}=t_{2}$.
Time-symmetry simply becomes the complete symmetry between the two measurement
actions. The same holds for the time-symmetrized description of the quantum
speedup, since nothing changes if we postpone the initial measurement of
$\hat{B}$ to the time of the final measurement of $\hat{A}$.

We will compare the explanation of nonlocality provided by the TS Formalism
and that of Costa de Beauregard in the discussion.

##  4  Discussion

The causal loops generated by the time-symmetrization formalism are of course
a puzzling notion. They ask for a change in our way of seeing the relation
between time and causality and of course the quantum description itself. They
also defy our common sense notion of time. We think it is important to defend
the notion of retrocausality implicit in the present time-symmetrization (TS)
formalism from both the theoretical and the psychological standpoint.

Each of the following subsections provides a comparison between the customary
way of seeing a particular physical issue and the way implied, or required, by
the TS formalism.

###  4.1  The whole and its parts

We have extended the physical description to all the parts of the phenomenon
under study. Until now our motivation has been generic: in order to understand
a physical phenomenon, it may be important to make its description as complete
as possible.

Now that the TS formalism has highlighted the temporally nonlocal character of
both the quantum speedup and quantum nonlocality, we can produce a more
specific motivation.

We consider problem-solving first. The usual description of quantum algorithms
starts with the input state of the unitary part of Alice’s problem-solving
action. The initial measurement that selects the problem-setting, although a
physically necessary step for the subsequent solution of the problem, is
omitted. It is replaced by its measurement outcome, which is in fact the input
of the described part.

At this point, we must realize that breaking the description of the whole into
that of adjacent spatio-temporal parts each with its surrounding conditions is
an application of the principle of locality, namely of the assumption that an
object is directly influenced only by its immediate space-time surroundings.
It is common practice and harmless in the classical case, where the
description of the whole can always be reconstructed from that of the parts.
However, in the quantum case, it might prevent a complete description of the
process nonlocality. Here of the fact that the final measurement changes in a
temporally nonlocal way the initial state of knowledge of the solution on the
part of Alice. Compare the two states in the top-left and bottom left corners
of table (4).

A similar consideration applies to the quantum nonlocality of the EPR paradox.
Its usual quantum description starts with a state in which the two subsystems
are already spatially separate. The process of spatial separation between the
two subsystems is replaced by its output state, which becomes the input of the
described part. Of course, also this is an application of the principle of
locality. Here it prevents a complete description of quantum nonlocality
itself.

###  4.2  Is quantum retrocausality physical?

The application of the TS formalism to problem-solving seems to provide a
unique occasion to discuss whether quantum retrocausality is physical or
unphysical.

We have already noted that the Parisian zigzag diagram of the quantum
algorithm to Alice (table 4) also works for uneven ways of sharing between the
initial and final measurements the selection of the information that specifies
the pair of correlated measurement outcomes. Therefore, it can trivially be
extended to cover the full range of assumptions: no retrocausality at all (the
usual way of thinking), mutual-causality, retrocausality only (backwards in
time propagation of the entire measurement outcome). Let $k$ be the fraction
of the information about the pair of correlated measurement outcomes whose
selection is ascribed to the final measurement. Then, $k=0$ means no
retrocausality at all, $k=1/2$ mutual-causality, and $k=1$ retrocausality
only.

The point is that, in all cases, the Parisian zigzag tells us that the problem
solver Alice knows in advance the $k$ -th fraction of the information about
the solution. This gives us a relation between the assumed “amount of
retrocausality” $k$ and the consequent number of oracle queries needed to
solve an oracle problem in an optimal quantum way. It is the number needed to
solve the oracle problem in an optimal logical (classical) way given the
advanced knowledge of the $k$-th part of the information that specifies its
solution. It is of course a number that can be compared with the number of
queries taken by the known optimal quantum algorithms. The “amount of
retrocausality” $k$ becomes thus empirically verifiable, for the first time as
far as we know.

Let us discuss the possible values of $k$ at the light of the above. We should
keep in mind that we are talking of a quantum process that is reversible from
the initial to the final measurement outcome:

$k=1$, namely ascribing all the selection of the information that specifies
the pair of correlated outcomes to the final measurement, is clearly
unphysical. First, $k=1$ would violate the time-symmetry required from the
description of the reversible process between the two outcomes – the fact that
the selection of the information about the pair of measurement outcomes should
evenly share between the two measurements. Second, Alice would know the entire
solution of the problem in advance without doing anything.

$k=1/2$, namely mutual-causality, satisfies the time-symmetry in question and,
in all the cases examined, yields the number of oracle queries of the known
optimal quantum algorithms.

$k=0$, no retrocausality at all, would mean no advanced knowledge of the
solution on the part of Alice and therefore no speedup. It does not satisfy
the time-symmetry of the process description and is of course in disagreement
with what the known quantum algorithms do.

Summing up, the only “non non-physical” assumption would be $k=1/2$, namely
mutual-causality. Also $k=1$, the absence of retrocausality of the usual
interpretation of the ordinary quantum description, would be unphysical.

###  4.3 Impact on the notion of time

As is well known, there have been authoritative applications of the notion of
retrocausality in physics, by: Costa de Beauregard $\left[2\right]$, Wheeler
and Feynman $\left[4\right]$, Aharonov and his school $\left[5-9\right]$, and
Cramer $\left[10\right]$, among others. In spite of this, it can be safely
said that the use of this notion still encounters a strong resistance from
most physicists.

We think that the main reason is as follows. Let us place the “present” at the
time of the cause. Then retrocausality means causing in the present an effect
in the past. There are only two possibilities: either that effect had already
happened, or the past must be changed. The former case is trivial, it is just
reading the quantum description of a reversible process in the reverse way.
The latter is the one we are interested in. Of course, the possibility of
changing the past can be seen with suspicion both from a technical and
psychological point of view. On the one hand, it generates well-known
paradoxes. On the other, if there is one thing that we are certain of, it is
that the past cannot be changed.

Another difficulty is as follows. If we shift the “present” from the time of
the final measurement to that of the initial measurement, the fact that the
latter changes the input state of the unitary evolution that leads to the
state immeditely before it becomes precognition, on the part of the problem
solver, of half of the information that specifies the solution. Although
perfectly equivalent to the quantum retrocausality we are dealing with, from a
psychological point of view precognition can be an even more disconcerting
notion.

We show that the TS formalism eludes the above problems in a rather cunning
way.

Let us consider the time-symmetrization of Grover algorithm to Alice, an
instance thereof – table (4). Here the initial state of register $B$
represents Alice’s knowledge of the number of the drawer with the ball. The
final measurement of the solution changes it from knowledge that the ball is
in one of four drawers (i.e. complete ignorance of the ball location) to
knowledge that it is in one of two drawers – compare the state of register $B$
in the top-left and bottom-left corners of the table. Now, the ordinary
quantum description is the superposition of all the time-symmetrization
instances. The superposition of all the possible pairs of drawers is the
superposition of all the possible drawers, namely the state of complete
ignorance of the ball’s location. In other words, the TS formalism tells us
that the ordinary quantum description of the past does not undergo any change.
The change remains confined within the unobservable internal structure of the
description produced by time-symmetrizing it.

###  4.4 Causal loops

A causal loop is an event that causes another event, which is in turn among
the causes of the first event. The explanations of the speedup and nonlocality
essentially imply causal loops. In either case the causal loop is a quantum
measurement that changes the input state of the unitary evolution that leads
to the state immediately before it.

We consider an instance of the time-symmetrization of Grover algorithm with
respect to the problem-solver Alice – see table (4). Let us start with the
feedback part of the loop. The outcome selected by Alice’s final measurement
of $\hat{A_{r}}$ (the right bit of the number contained in register $A$) is
the starting event. Propagating backwards in time along the unitary part of
the quantum algorithm, it causes back in time a change of Alice’s initial
state of knowledge of the solution – compare the states of register $B$ in the
top-left and bottom left corners of the table. The resulting Alice’s state of
knowledge is the caused event. This is in turn among the causes that lead
(possibly with a speedup) to the the final measurement outcome, namely the
first event, what closes the loop. In the case that Alice’s problem-solving
action benefits of that advanced knowledge to achieve a speedup, this action
is the concause of the speedup. The loop is evident also in its computational
interpretation. The final measurement of the solution produced by Alice tells
her back in time, before she begins her problem solving action, half of the
information about the solution. She can benefit of that knowledge to produce
the solution with fewer oracle queries. This is apparently paradoxical of
course. However, it exactly represents the well known quantum efficiency. With
respect to similar paradoxes related to changing a past quantum state, it has
the advantage of being verifiable by comparison with the known quantum
algorithms.

In the case of quantum nonlocality, each time-symmetrization instance hosts
two causal loops – see table (12).

In one, the starting event is the selection of the reduced density operator of
register $B$ by the measurement of $\hat{B}_{l}$ (the left bit of the number
contained in register $B$) at time $t_{1}$. On its way toward the other
measurement via $t_{0}$, at time $t_{0}$ it locally causes a change of the
overall state of registers $B$ and $A$. The changed state in turn, continuing
to proceed toward the other measurement, now forward in time, at time $t_{1}$
changes the previous overall state of registers $B$ and $A$. Since the
previous density operator of register $B$ at time $t_{1}$ was the starting
event, this closes the loop – emulating nonlocality for the measurement of the
bit in question.

The other loop is naturally the one that starts with the selection of the
reduced density operator of register $A\text{}$ by the measurement of
$\hat{A_{r}}$ (the right bit of the number contained in register $A$) at time
$t_{2}$. The discourse is completely similar.

Causal loops are topological facts that can have paradoxical consequences.
However, here they are implicit in a TS formalism that should only produce the
good part of them: (i) they are produced by a legitimate time-symmetrization
operation and (ii) they are confined within the unobservable time-
symmetrization instances and vanish in their quantum superposition, namely in
the ordinary quantum description. They do not change any past state described
by the ordinary quantum description.

###  4.5  Comparing the TS formalism with Costa de Beauregard’s explanation

Costa de Beauregard’s explanation assumes that the entire outcome of the first
measurement goes backwards in time along the inverse of the time-forward
unitary evolution to the time $t_{0}$ the two subsystems were not spatially
separate – (table 10). This corresponds to $k=1$ – see Section 4.3. It
introduces a preferred direction of time in a reversible process and should
therefore be unphysical – we have seen that $k=1$ is obviously so in the
problem-solving context. Eventually, it can be considered arbitrary in the
measure that it is an ad hoc assumption which is only justified by the
explanation it provides.

The TS formalism replaces the full retrocausality of Costa de Beauregard’s
explanation of table (10) by the mutual-causality of table (12) – it replaces
$k=1$ by $k=1/2$. While the assumption of full retrocausality is arbitrary,
mutual causality is the consequence of time-symmetrizing the ordinary quantum
description of the reversible process between the two measurement outcomes.
This, in present assumptions, besides being legitimate, is mandatory to
complete the quantum description. Furthermore, the two not yet space-separate
subsystems are told how to behave in the future measurements by hidden –
unobservable – variables. This should be a more acceptable way of sending
information back in time: it does not change the observable past.

Another advantage of the TS Formalism is that it also explains the quantum
speedup. The propagation backwards in time of an entire measurement outcome
could not – we have seen that it would clearly be unphysical.

##  5  Summary and conclusion

As the present work is rather unconventional, it may be useful to provide an
organic review of it before concluding.

###  5.1  Summary

We have been dealing with the quantum description of the reversible processes
between two one-to-one correlated measurement outcomes that characterize both
the quantum speedup and quantum nonlocality. We have seen that the ordinary
quantum description of these processes describes the correlation between
corresponding parts of the two outcomes without specifying the direction of
causality, namely which is the cause and which the effect. This is an
incompleteness of the description for the following reason.

If the cause belongs to the initial (final) measurement outcome, this implies
that the information that specifies the pair of corresponding parts has been
selected by the initial (final) measurement. Since, for disjoint pairs of
corresponding parts one can freely and independently choose which is the cause
an which the effect, there is a number of ways exponential in outcome sizes in
which the information that specifies the sorted out pair of outcomes can share
between the initial and final measurements. All are compatible with the
ordinary quantum description but most of them are uneven, thus violate the
time-symmetry required from the description of a reversible process.

This says two things, that the ordinary quantum description is incomplete and
that it can be completed by imposing that the initial and final measurements
evenly contribute to selecting the sorted out pair of outcomes. Since this can
be done in a plurality of ways, we should take their quantum superposition.

This time-symmetrization of the ordinary quantum description leaves it
unaltered, as it should be, but at the same time shows that it is a quantum
superposition of unobservable time-symmetrization instances whose causality
structure is completely specified. The description of this superposition
completes the ordinary quantum description.

So completed, the quantum description acquires a superior explanatory power of
the phenomenon at stake. Any time-symmetrization instance immediately explains
the quantum speedup and quantum nonlocality. Both rely on causal loops
implicit in the time-symmetrization instances, a quantum measurement that
retrocausally changes the input state of the unitary evolution leading to the
state immediately before it.

In the case of the speedup, the quantum measurement is the final measurement
of the solution and the input state is the input state of the problem-solving
part of the quantum algorithm. It represents the initial knowledge of the
solution on the part of the problem solver. Complete ignorance of the solution
changes into knowledge of half of the information that specifies it. The
causal loop becomes the fact that the problem solver knows in advance half of
the information about the solution she will produce in the future and can use
this knowledge to produce the solution with fewer oracle queries.

In the case of nonlocality, the measurement on either subsystem, when the two
are space-separate, retrocausally and locally changes the state of both
subsystems when they were not space-separate. There are two causal loops, one
for each measurement. Together, they locally ensure the correlation between
the two measurement outcomes.

###  5.2  Conclusion

It is not inappropriate to conclude by addressing the unconventional character
of the present work. Its challenging points can be summarized as follows:

(i) Opening to retrocausality.

(ii) Resuming an apparently forgotten problem, that of the incompleteness of
the quantum description raised by Einstein, Podolsky and Rosen in their famous
EPR paper. According to them, the ordinary quantum description would be
incomplete because it mathematically describes the action at a distance that
characterizes quantum nonlocality but does not explain it physically.

(iii) Tackling the same problem in the quantum speedup, the fact that the
ordinary quantum description describes it mathematically, quantum algorithm by
quantum algorithm, but not physically.

(iv) Deriving a technical result – the rule for computing the number of oracle
queries needed to solve an oracle problem in an optimal quantum way – in an
axiomatic way from physical principles.

(v) Showing that the quantum capability of performing tasks that cannot be
performed classically essentially relies on causal loops.

Any of the above points can be puzzling. We defend our choices as follows:

Point (i). The fact that retrocausality can change the past gives rise to
well-known paradoxes. However, the present form of quantum retrocausality has
a justification and a remedy. The justification is that it is generated by a
legitimate operation: the time-symmetrization of the ordinary quantum
description of a process that is reversible from the initial to the final
measurement outcome. The remedy is that it resides in each unobservable time-
symmetrization instance and vanishes in their quantum superposition, namely in
the ordinary quantum description. In other words, the form of retrocausality
generated by the TS formalism does not change the past described by the
ordinary quantum description.

With hindsight, the TS formalism provides a very simple argument in favor of
the existence of retrocausality. Consider the four drawer case of Grover
algorithm. Always locating a ball hidden in one of four drawers by opening
only one drawer implies that all is as if Alice, the problem solver, all the
times knew that the ball is in a pair of drawers comprising the one that hosts
it. There is no other way. However, the only possible source of that
information is the number of the drawer with the ball that Alice will produce
and read in the future; she has no access to other sources. This implies that
Alice knows in advance half of that information. It implies precognition, i.e.
retrocausality. The logic in question would seem to be inescapeble. Of course,
if it had no correspondence with quantum mechanics there would be a problem.
However, the opposite is true. That logic just expresses in words what the
time-symmetrization of Grover algorithm to Alice does – see table (4).

Points (ii) and (iii). With hindsight, it is clear that the ordinary quantum
description describes nonlocality and the speedup in an incomplete way. As it
ignores the direction of causality, it cannot describe the causal loops on
which they both rely.

Point (iv). The number of oracle queries needed to solve an oracle problem in
an optimal quantum way has been axiomatically derived from the principle that
the quantum description of a reversible process must be symmetric in time.
This derivation solves in a synthetic way the so called quantum query
complexity problem, which is central to quantum computer science and still
unsolved in the general case $\left[23,24\right]$. The synthetic character of
the derivation contrasts with the analytical (entirely mathematical) character
of the derivations typical of the latter discipline. Our defense is that the
two kinds of derivation should be equivalent if one assumes the consistency of
quantum mechanics.

Of course we know that a synthetic, rather than analytic, solution of the
quantum query complexity problem can meet distrust. It is therefore important
to mention the fact that we have nothing less than Grover’s authority on our
side. In 2001 $\left[25\right]$, he called for a synthetic demonstration of
the optimality of his famous quantum algorithm. He wrote: It has been proved
that the quantum search algorithm cannot be improved at all, i.e. any quantum
mechanical algorithm will need at least  $\operatorname*{O}\sqrt{N}$ steps to
carry out an exhaustive search of  $N$ items. Why is it not possible to search
in fewer than  $\operatorname*{O}\sqrt{N}$ steps? The argument used to prove
this are very subtle and mathematical. What is lacking is a simple and
convincing two line argument that shows why one would expect this to be the
case.

Due to its reversibility, the quantum description of the process of setting
and solving Grover’s problem can always be time-symmetrized. This means evenly
sharing the selection of the information that specifies the number of the
drawer with the ball between the initial measurement (that selects the
problem-setting) and the final measurement (that selects the solution). Our
“two line” argument is that this reduces the computational complexity of the
problem to be solved from $\operatorname*{O}\left(N\right)$ to
$\operatorname*{O}\sqrt{N}$. Further time-symmetrizing the time-symmetrized
process would leave it unaltered – without further reducing the problem’s
computational complexity.

Point (v). We have shown that, in the two known cases, the quantum ability to
perform tasks that cannot be performed classically relies on causal loops.
Accepting the idea that (non-relativistic) quantum mechanics can host causal
loops might be difficult. However, the fact that such loops reside in the
unobservable time-symmetrization instances and vanish in their quantum
superposition, namely in the ordinary quantum description, should make the
difficulty more acceptable.

In conclusion, we have found that the ordinary quantum description of the
processes between two one-to-one correlated measurement outcomes, which
describes the correlation but not the causal structure that ensures it, is the
quantum superposition of unobservable time-symmetrization instances whose
causal structure is completely defined. These instances have a greater
explanatory power than their superposition. They exactly explain the quantum
speedup and quantum nonlocality by showing that they rely on causal loops
whose existence in non-relativistic quantum mechanics was until now
unsuspected. The work is inevitably a paradigm shift in the way of describing
quantum processes.

Future work, at the fundamental level, could be to further compare the TS
formalism with time-symmetric and relational quantum mechanics and to look for
the possibility of extending this formalism to more general quantum
descriptions. One could also look for causal loops in any task that is
quantumly possible and classically impossible. At the technical level, one
could see if the present axiomatic derivation of the rule for finding the
number of queries needed to solve an oracle problem in an optimal quantum way
might suggest a corresponding analytic derivation. About the possibility of
cross fertilization between the foundations of physics and quantum computer
science, see $\left[26\right]$.

##  Acknowledgments

Thanks are due to Eliahu Cohen, Artur Ekert, Avshalom Elitzur, David
Finkelstein, and Ken Wharton for useful suggestions and Daniel Sheehan for
organizing the San Diego AAAS-Pacific Division Congresses on Retrocausalty, a
forum of discussion that has been important for the development of the present
line of research.

##  References

$\left[1\right]$ Einstein, A., Podolsky, B., and Rosen, N.. Can Quantum-
Mechanical Description of Physical Reality Be Considered Complete? Phys. Rev.
47 (1935), 777-780.

$\left[2\right]$ Costa de Beauregard, O.. Mechanique quantique. Compte Rendus
Academie des Siences, 236 (1953), 1632-34.

$\left[3\right]$ Bell, J. S.. On the Einstein Podolsky Rosen Paradox. Physics
Publishing Co. Printed in the United States (1964), 195-290

$\left[4\right]$ Wheeler, J. A., Feynman, R. P.. Interaction with the Absorber
as the Mechanism of Radiation. Rev. Mod. Phys., vol 17, 2-3 (1945), 157-161.

$\left[5\right]$ Aharonov, Y., Bergman, P. G., and Lebowitz, J. L.. Time
Symmetry in the Quantum Process of Measurement. Phys. Rev. 134 (1964),
1410-1416.

$\left[6\right]$ Dolev, S. and Elitzur, A. C.. Non-sequential behavior of the
wave function. arXiv:quant-ph/0102109 v1 (2001).

$\left[7\right]$ Aharonov, Y. and Vaidman, L.. The Two-State Vector Formalism:
An Updated Review. Lect. Notes Phys. 734 (2008), 399-447.

$\left[8\right]$ Aharonov, Y., Cohen, E., and Elitzur, A. C.. Can a future
choice affect a past measurement outcome? Ann. Phys. 355 (2015), 258-268.

$\left[9\right]$ Aharonov, Y., Cohen E., and Tollaksen, J.. Completely top-
down hierarchical structure in quantum mechanics. Proc. Natl. Acad. Sci. USA
115 (2018), 11730-11735.

$\left[10\right]$ Cramer, J. G.. The Transactional Interpretation of Quantum
Mechanics. Rev. Mod. Phys. 58 (3) (1986), 647-688.

$\left[11\right]$ Rovelli, C.. Relational Quantum Mechanics. Int. J. Theor.
Phys. 35 (1996), 637-658.

$\left[12\right]$ Fuchs, C. A.. On Participatory Realism. arXiv:1601.04360v3
[quant-ph] (2016).

$\left[13\right]$ Deutsch, D.. Quantum theory, the Church Turing principle and
the universal quantum computer. Proc. Roy. Soc. A 400 (1985) 97-117

$\left[14\right]$ Castagnoli, G. and Finkelstein D. R.. Theory of the quantum
speedup. Proc. Roy. Soc. Lon., 457 (2001), 1799-1807.

$\left[15\right]$ Castagnoli, G.. The quantum correlation between the
selection of the problem and that of the solution sheds light on the mechanism
of the quantum speed up. Phys. Rev. A 82 (2010), 052334.

$\left[16\right]$ Castagnoli, G.. Completing the Physical Representation of
Quantum Algorithms Provides a Quantitative Explanation of Their Computational
Speedup. Found. Phys. 48 (2018), 333-354.

$\left[17\right]$ Castagnoli, G., Cohen, E., Ekert, A. K., and Elitzur, A. C..
A Relational Time-Symmetric Framework for Analyzing the Quantum Computational
Speedup. Found Phys., 49, 10 (2019), 1200-1230.

$\left[18\right]$ Grover, L. K.. A fast quantum mechanical algorithm for
database search. Proc. 28th Annual ACM Symposium on the Theory of Computing.
ACM press New York (1996), 212-219.

$\left[19\right]$ Long, G. L.. Grover algorithm with zero theoretical failure
rate. Phys. Rev. A 64 (2001), 022307-022314.

$\left[20\right]$ Toyama, F. M., van Dijk, W., and Nogami Y.. Quantum search
with certainty based on modified Grover algorithms: optimum choice of
parameters. Quant. Inf. Proc. 12 (2013), 1897-1914.

$\left[21\right]$ Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani,
U.. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing
26 (1997), 1510-1523.

$\left[22\right]$ Price, H. and Wharton, K.. Disentangling the Quantum World.
arxiv:1508.01140 (2015).

$\left[23\right]$ Aaronson S., Ambainis, A., Iraids, J., Kokainis, M.,
Smotrovs, J.. Polynomials, Quantum Query Complexity, and Grothendieck’s
Inequality. CCC’16: Proceedings of the 31st Conference on Computation and
Complexity, May 2016 and arXiv:1511.08682v3 [quant-ph] (2016)

$\left[24\right]$ Ambainis, A.. Understanding Quantum Algorithms via Query
Complexity. arXiv:1712.06349 (2017).

$\left[25\right]$ Grover, L. K.. From Schrodinger equation to quantum search
algorithm. arXiv: quant-ph/0109116 (2001).

$\left[26\right]$ Aaronson, S.. NP-complete problems and physical reality. ACM
SIGACT News, 36(1) (2005), 30-52.