Theoretical analysis of a nearly optimal analog quantum search
Carlo Cafaro Paul M. Alsing



^1SUNY Polytechnic Institute, 12203 Albany, New York, USA
^2Air Force Research Laboratory, Information Directorate, 13441 Rome, New
York, USA


We analyze the possibility of modifying the original Farhi-Gutmann Hamiltonian
algorithm in order to speed up the procedure for producing a suitably
distributed unknown normalized quantum mechanical state. Such a modification
is feasible provided only a nearly optimal fidelity is sought. We propose to
select the lower bounds of the nearly optimal fidelity values such that their
deviations from unit fidelity are less than the minimum error probability
characterizing the optimum ambiguous discrimination scheme between the two
nonorthogonal quantum states yielding the chosen nearly optimal fidelity
values. Departing from the working assumptions of perfect state overlap and
uniform distribution of the target state on the unit sphere in N-dimensional
complex Hilbert space, we determine that the modified algorithm can indeed
outperform the original analog counterpart of a quantum search algorithm. This
performance enhancement occurs in terms of speed for a convenient choice of
both the ratio γ=E^'/E between the energy eigenvalues
E^' and E of the modified search Hamiltonian and the quantum
mechanical overlap x between the source and the target states. Finally, we
briefly discuss possible analytical improvements of our investigation together
with its potential relevance in practical quantum engineering applications.



Quantum computation (03.67.Lx), Quantum information (03.67.Ac).
Theoretical analysis of a nearly optimal analog quantum search
    Carlo Cafaro^1 and Paul M. Alsing^2
    December 30, 2023
==============================================================








§ INTRODUCTION


In 1997, Grover presented a quantum algorithm for solving very large database
search problems <cit.>, one of the outstanding problems in
computational science <cit.>. Grover's search algorithm enables
searching for an unknown marked item in an unstructured database of N items
by accessing the database a minimum number of times. From a classical
standpoint, one needs to test N/2 items, on average, before identifying the
correct item. With Grover's algorithm however, the same task can be completed
successfully with a complexity of order √(N), that is, with a quadratic
speed up. The original formulation of Grover's algorithm was presented in
terms of a discrete sequence of unitary logic gates (digital quantum
computation). Alternatively, Farhi and Gutmann proposed an analog version of
Grover's algorithm in Ref. <cit.> where the state of the quantum
register evolves continuously in time under the action of a suitably chosen
driving Hamiltonian (analog quantum computation). For recent discussions on
the transition from the digital to analog quantum computational setting for
Grover's algorithm, we refer to Ref. <cit.>. The
formulation of the analog algorithm proposed by Farhi and Gutmann can be
briefly described as follows. Consider N mutually orthonormal states and
assume that only one of them has non-zero energy (energetically marked state).
Starting from an equal superposition of the N states, the problem is to
determine how quickly the system can evolve under a given Hamiltonian so that
the energetically marked state is reached with certainty. Within the working
assumption of time-independent Hamiltonian evolutions, Farhi and Gutmann
showed that their algorithm required a minimum time of the order √(N),
thus yielding the same complexity as Grover's original algorithm.
Interestingly, the evolution time for the analog algorithm scaled like
√(N)/E, with E denoting the energy of the marked state, just as
demanded by the time-energy uncertainty principle <cit.>. In
Refs. <cit.>, it was shown that the minimum
time interval required for an isolated quantum system to evolve to an
orthogonal (that is, perfectly distinguishable) state is inversely
proportional to its constant energy spread. Such minimum time is also known as
orthogonalization time in the literature. In Ref. <cit.>, the
maximum speed of evolution of an isolated quantum system was interpreted in
terms of the maximum number of distinct states that the system can explore in
a fixed time interval. This fixed time interval was shown to be inversely
proportional to the system's quantum mechanical average energy minus its
ground state energy. For a unified tight bound on the rate of quantum
dynamical evolution based on both the average energy and the energy spread of
the system, we refer to Ref. <cit.>. The presence of a finite
non-orthogonality in the context of quantum limits to dynamical evolutions was
considered, for instance, in Ref. <cit.> and Ref.
<cit.>. In the former work, the expression of the states that
minimize the time necessary to evolve, under a time-independent Hamiltonian,
from an initial quantum state to a final state that is only approximately
orthogonal was found. It is worth noting that the final state is only
approximately orthogonal for a given upper bound on the mean energy of a
general closed system. In the latter work, on the contrary, an extension of
the concept of quantum speed limit to mixed states in the case where the
quantum system does not evolve from an initial state to an orthogonal state
(that is, the case of non-zero fidelity) was proposed.

In our paper, instead of allowing for a finite non-orthogonality between the
quantum states that leads to a non-zero fidelity, we consider a complementary
scenario. We allow for a finite non-parallelism that yields a non-unit
fidelity. The consideration of nearly optimal state searching is instructive
for various reasons. First, it is reasonable to take into account the fact
that actual measurements always involve a countable set of outcomes and thus,
any realistic measurement device has finite resolution <cit.>
. Second, finite resolution measurements can reveal more about the physical
properties of quantum systems than precise measurements <cit.>.
Third, it is known that a quantum measurement can enhance the transition
probability between two pure states <cit.> and, finally, it is
indisputable that quantum measurement cannot perfectly discriminate between
two nonorthogonal pure states <cit.>.

Motivated by these considerations, the questions we address in this paper can
be outlined as follows: First, what is the minimum time necessary to reach a
given nearly optimal fidelity value in a continuous time quantum search
algorithm? Second, is it possible to formulate a modified version of the
original Farhi-Gutmann search algorithm that leads to such a selected fidelity
value in a shorter time than the one required by the original Farhi-Gutmann
algorithm? Third, how can we reasonably justify the choice of a lower bound
for such a nearly optimal fidelity value? We demonstrate that it is possible
to extend the original work performed by Farhi and Gutmann in order to speed
up the procedure for producing a suitably distributed unknown normalized
quantum state with high non-unit fidelity. In particular, by modifying the
original working assumptions of perfect state overlap and uniform distribution
of the target state on the unit sphere in the N-dimensional complex Hilbert
space, the newly proposed algorithm can indeed outperform the original analog
counterpart of a quantum search algorithm. This is achieved for a convenient
choice of both the ratio γdef
=E^'/E between the eigenvalues E^' and E of the modified
search Hamiltonian and the quantum mechanical overlap x between the initial
and target states.

The layout of the remainder of this paper is as follows. In Section II, we
extend the Farhi-Gutmann optimality proof to the case of an imperfect quantum
state overlap. In Section III, we present the transition probability for the
modified version of the Farhi-Gutmann analog algorithm. In Section IV, we
explain how we choose the lower bounds of the nearly optimal fidelity values
by means of quantum discrimination techniques. Specifically, we impose that
deviations from unit fidelity are less than the minimum error probability
characterizing the optimum ambiguous discrimination scheme between the two
nonorthogonal quantum states yielding the selected nearly optimal fidelity
values. In Section V, we compare in terms of minimum run time the original and
the modified quantum search algorithms and identify a two-dimensional
parametric region where the modified algorithm outperforms the original one
under the working assumption of imperfect state transfer compatible with
finite precision quantum measurements. Our concluding remarks appear in
Section VI. Finally, technical details on the numerical values of the quantum
overlap x can be found in Appendix A.



§ THE MODIFIED OPTIMALITY PROOF


In this section, we modify the original optimality proof by Farhi and Gutmann
in Ref. <cit.> by relaxing the requirement of finding the desired
target state with certainty. In particular, we wish to determine how the
search time shortens if we only want to achieve a nearly optimal fidelity value.

The optimality proof provided by Farhi and Gutmann in Ref. <cit.> for
producing the target state | w⟩ relies on two key
working assumptions. First, the target state is produced with absolute
certainty. In other words, the modulus squared of the quantum state overlap,
that is, the transition probability or transition fidelity at the end of the
production procedure is equal to unity. Second, the target state |
w⟩ is an unknown element of a given orthonormal basis {| a⟩} with 1≤ a≤ N of an
N-dimensional complex Hilbert space ℋ_2^n with
Ndef=2^n. Our modified optimality proof for an
imperfect quantum state overlap follows closely the lines of the original
optimality proof presented in Ref. <cit.>. Consider a quantum system,
assumed to be initially in a state | i⟩ at time t=0
that does not depend on the target state | w⟩ and
evolves by means of a Hamiltonian ℋ given by,

    ℋdef=ℋ_w+ℋ_D,

where ℋ_wdef=E| w⟩⟨ w|. For the discussion that follows, it is
unnecessary to specify the explicit expression for the driving Hamiltonian
ℋ_D in Eq. (<ref>). The problem being investigated is that
of finding a lower bound t̃ on the time t for the |
w⟩-independent state | i⟩ to evolve into
the state | w⟩ given that its evolution is governed by
the time-independent Hamiltonian ℋ in Eq. (<ref>). Let us
consider the following two initial value problems,

    {[ iℏd/dt|ψ_w(  t)  ⟩
    =ℋ|ψ_w(  t)  ⟩;                |ψ_w(  0)  ⟩ =| i⟩ ].  , and {[ iℏd/dt|ψ(  t)  ⟩
    =ℋ_D|ψ(  t)  ⟩;                |ψ(  0)  ⟩ =| i⟩ ].  ,

where ℏ denotes the reduced Planck constant. In what follows, we
depart from Farhi and Gutmann original optimality proof. We do not require
achieving the absolute certainty of producing the target state at the end of
the evolution and assume that at time t̃ we have,

    |ψ_w(  t̃)  ⟩def=⟨ w|ψ_w(  t̃)  ⟩| w⟩ +⟨ w_|ψ_w(  t̃)  ⟩| w_⟩.

The normalization condition for |ψ_w(  t̃)  ⟩ requires that the probability amplitudes satisfy
the following constraint equation,

    |⟨ w|ψ_w(  t̃)  ⟩| ^2+|⟨ w_|ψ_w(  t̃)  ⟩| ^2=1.

The quantity | w_⟩ denotes a
(normalized) state orthogonal to the target state |
w⟩ contained in the two-dimensional subspace of the
full Hilbert space spanned by | w⟩ and
| w_⟩. A suitable choice for the
parametrization of the state |ψ_w(  t̃)  ⟩ in Eq. (<ref>) is given by,

    |ψ_w(  t̃)  ⟩ =cos(
    δ)  | w⟩ +e^-i(  θ_w
    -θ_w_)  sin(  δ)  | w_⟩,

where θ_w and θ_w_
are arbitrary real phases while δ is
assumed to be a small and positive real parameter. Finally, for
convenience and without loss of generality, we set θ_w-θ
_w_=π/2 so that |ψ_w(  t̃)
⟩ becomes

    |ψ_w(  t̃)  ⟩ =cos(
    δ)  | w⟩ -isin(  δ)
    | w_⟩,

where i denotes the complex imaginary unit. In what follows, we
assume 0≤δ≪1 so that cos^2(
δ)  =1-δ^2+𝒪(  δ^4)
and sin^2(  δ)  =δ^2+𝒪(
δ^4). For the sake of clarity, we point out that the
validity of this latter working assumption will be explicitly clarified by
means of Eq. (<ref>) and Fig. 2 in the next section.
Furthermore, we have

    cos(  δ)  =1-(1/2)δ^2+𝒪(  δ
    ^4)  , and sin(  δ)  =δ+𝒪
    (  δ^3)  .

To find a lower bound t̃ on the time t, we proceed as follows.
First, consider the following quantity

    ∑_w=1^N‖|ψ_w(  t̃)
    ⟩ -|ψ(  t̃)  ⟩‖ ^2.

By using Eqs. (<ref>) and (<ref>) in the expression for
‖|ψ_w(  t̃)  ⟩
-|ψ(  t̃)  ⟩‖ ^2
appearing in Eq. (<ref>), we obtain after some algebra,

    ‖|ψ_w(  t̃)  ⟩
    -|ψ(  t̃)  ⟩‖
    ^2=2-cos(  δ)  [  ⟨ψ(  t̃)  |w⟩ +⟨ w|ψ(  t̃)
    ⟩]  +isin(  δ)  [  ⟨ψ(  t̃)  |w_⊥⟩ -⟨ w_⊥|ψ(  t̃)  ⟩]  .

Substituting Eq. (<ref>) into Eq. (<ref>), we obtain

    ∑_w=1^N‖|ψ_w(  t̃)
    ⟩ -|ψ(  t̃)  ⟩‖ ^2=2N-cos(  δ)  ∑_w=1^N[
    ⟨ψ(  t̃)  |w⟩ +⟨
    w|ψ(  t̃)  ⟩]  +isin(
    δ)  ∑_w=1^N[  ⟨ψ(  t̃)  |w_⊥⟩ -⟨ w_⊥|ψ(
    t̃)  ⟩]  .

Observe that for a set of complex amplitude coefficients {
c_j} with 1≤ j≤ N, we find

    ∑_j=1^N| c_j| ^2=1⇒∑_j=1
    ^N| c_j|≤ N^1/2.

Therefore, by exploiting Eq. (<ref>), we observe that

    ∑_w=1^N‖|ψ_w(  t̃)
    ⟩ -|ψ(  t̃)  ⟩‖ ^2≥2N-2√(N)cos(  δ)  -2√(N)
    sin(  δ)  .

By using Eq. (<ref>) in Eq. (<ref>) and neglecting second
order terms in δ we arrive at,

    ∑_w=1^N‖|ψ_w(  t̃)
    ⟩ -|ψ(  t̃)  ⟩‖ ^2≥(  2N-2√(N))  (  1-δ)
    +2(  N-2√(N))  δ.

Observe that for N≥4, we have both 2N-2√(N)≥ N and N-2√(N)≥0. Finally, Eq. (<ref>) reduces to,

    ∑_w=1^N‖|ψ_w(  t̃)
    ⟩ -|ψ(  t̃)  ⟩‖ ^2≥ N(  1-δ)  .

Now, let us consider the following expression,

    d/dt‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2.

After some algebra and exploiting the normalization conditions ⟨ψ_w(  t)  |ψ_w(  t)  ⟩ =1 and
⟨ψ(  t)  |ψ(  t)  ⟩ =1,
we obtain

    ‖|ψ_w(  t)  ⟩ -|ψ(  t)  ⟩‖ ^2=2-⟨ψ
    _w(  t)  |ψ(  t)  ⟩ -⟨ψ(  t)  |ψ_w(  t)  ⟩.

Differentiating with respect to time the LHS (left-hand-side) and the RHS
(right-hand-side) of Eq. (<ref>) and recalling that z+z^∗=2Re(  z) for any z∈


ℂ where z^∗ denotes the complex conjugate of z, we find

    d/dt‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2
    =-2Re{d/dt[  ⟨ψ_w(
    t)  |ψ(  t)  ⟩]  },

that is,

    d/dt‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2
    =-2Re[  ⟨d|ψ_w(
    t)  ⟩/dt|ψ(  t)  ⟩
    +⟨ψ_w(  t)  |d|ψ(
    t)  ⟩/dt⟩]  .

Recalling that iℏd/dt|ψ_w(  t)
⟩ =ℋ|ψ_w(  t)  ⟩
and iℏd/dt|ψ(  t)  ⟩
=ℋ_D|ψ(  t)  ⟩ and observing
that Re(  iz)  =-Im(  z) for any z∈


ℂ, Eq. (<ref>) becomes

    d/dt‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2=2/ℏIm[  ⟨ψ_w(  t)
    |ℋ_w|ψ(  t)  ⟩]  .

Employing the Cauchy-Schwarz inequality and recalling that ⟨ψ_w(  t)  |ψ_w(  t)  ⟩ =1, we
obtain

    d/dt‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2     =2/ℏIm[  ⟨ψ_w(  t)
    |ℋ_w|ψ(  t)  ⟩] 
       
       ≤2/ℏ|⟨ψ_w(  t)
    |ℋ_w|ψ(  t)  ⟩|
       
       ≤2/ℏ‖|ψ_w(  t)
    ⟩‖·‖ℋ_w|ψ(  t)  ⟩‖ =2/ℏ‖ℋ_w|ψ(  t)  ⟩‖.

Summing over the index w in Eq. (<ref>), we have

    d/dt(  ∑_w=1^N‖|ψ_w(
    t)  ⟩ -|ψ(  t)  ⟩‖ ^2)  ≤2/ℏ∑_w=1^N‖ℋ_w|ψ(  t)  ⟩‖.

Since ℋ_wdef=E| w⟩⟨ w| and ⟨ w|w⟩ =1, and using
Eq. (<ref>), the RHS in the inequality written in Eq. (<ref>)
becomes

    2/ℏ∑_w=1^N‖ℋ_w|ψ(  t)  ⟩‖ =2E/ℏ∑
    _w=1^N|⟨ w|ψ(  t)  ⟩|≤2E/ℏ√(N).

Combining Eqs. (<ref>) and (<ref>), we obtain

    d/dt(  ∑_w=1^N‖|ψ_w(
    t)  ⟩ -|ψ(  t)  ⟩‖ ^2)  ≤2E/ℏ√(N).

Integrating Eq. (<ref>) with respect to time and recalling the initial
conditions |ψ_w(  0)  ⟩ =|ψ(  0)  ⟩ =| i⟩, we find

    ∑_w=1^N‖|ψ_w(  t)  ⟩
    -|ψ(  t)  ⟩‖ ^2≤2E/ℏ√(N)t.

Finally, by combining Eq. (<ref>) and Eq. (<ref>) evaluated at
t=t̃, we have

    N(  1-δ)  ≤∑_w=1^N‖|ψ
    _w(  t̃)  ⟩ -|ψ(  t̃)  ⟩‖ ^2≤2E/ℏ√(N)
    t̃,

that is,

    2E/ℏ√(N)t̃≥ N(  1-δ)  ,

or, equivalently,

    t̃≥ ℏ/2E(  1-δ)  √(N).

Equation (<ref>) is our first finding reported in this paper and
can be regarded as the analog of Eq. (23) in Ref. <cit.> obtained
in the context of finding states that minimize the evolution time to become an
almost orthogonal state. We point out that although it is expected
that t̃_min^(  approximate)  
≤t̃_min^(  exact), the scaling
behavior of t̃_min^(  exact) as a function of the angle δ with
0≤δ≪1 is not at all obvious. We emphasize that the
validity of Eq. (<ref>) is limited to the case in which the target
state | w⟩ is an unknown element of a given
orthonormal basis {| a⟩} with 1≤
a≤ N of an N-dimensional complex Hilbert space. We also recall that
δ is defined by the relation δdef=cos
^-1[  ⟨ w|ψ_w(  t̃)  ⟩] with |ψ_w(  t)  ⟩def=Û(  t, t_0)  |ψ_w(  t_0)  ⟩. The unitary operator Û(  t, t_0)  def=e^-i/ℏℋ(  t-t_0) is the usual quantum mechanical
evolution operator. Therefore in general, the quantity δ can depend on
certain characteristics of the chosen time-independent search Hamiltonian
ℋ.

For the sake of clarity, we point out that our proposed modified optimality
proof is not meant to be used to determine the optimality of a modified
continuous time quantum search algorithm. The lower bound in Eq.
(<ref>) is only useful for providing the optimality of the
scaling of the complexity of any algorithm specified by the Hamiltonian in Eq.
(<ref>). In particular, its purpose is to find out the behavior with
respect to the parameter δ of the minimum time necessary to achieve a
desired nearly optimal transition probability value (that is, cos^2(
δ) with 0≤δ≪1) when evolving from a source state
| i⟩ to an approximate target state |ψ_w(  t̃)  ⟩ under the Hamiltonian in Eq.
(<ref>). In other words, we have not compared the optimality of two
distinct algorithms that aim to solve the same identical task. Instead, we are
interested in finding out how the performance of a single algorithm,
quantified in terms of the minimum time necessary to accomplish the task, is
affected when two distinct tasks have to be completed. In our case, the first
task (that is, the original task) is to find the target state with certainty
(that is, success probability equal to one). The second task (that is, the
modified task), instead, is to search for an approximate target state that
corresponds to a success probability that is only nearly equal to one. In
summary, when considering the original task, we go from |
i⟩ to | w⟩ with success probability one
and t̃_min^(  exact)  def
=(ℏ/2E)√(N). In the modified task, we go from |
i⟩ to |ψ_w(  t̃)
⟩ with success probability cos^2(  δ)
where 0≤δ≪1 and t̃_min^(  approximate
)  def=(ℏ/2E)(  1-δ)  √(N). In both cases, the same algorithm described by the Hamiltonian in Eq.
(<ref>) is employed.

Our proposed modified optimality proof allowed us to formally introduce the
parameter δ in a general physical setting where it is not necessary to
specify the explicit expression of the driving Hamiltonian ℋ_D
in Eq. (<ref>). The following section, instead, includes a more specific
discussion on the functional form of the parameter δ for a specific
choice of the driving Hamiltonian.



§ THE MODIFIED FARHI-GUTMANN SEARCH HAMILTONIAN


In this section, we present the transition probability for the modified
version of the Farhi-Gutmann analog search algorithm. Assume that the
time-independent Hamiltonian ℋ in Eq. (<ref>) is given by,

    ℋdef=ℋ_w+ℋ_D=E|
    w⟩⟨ w| +E^'| s⟩⟨ s|,

where,

    ℋ_wdef=E| w⟩⟨
    w| and, ℋ_Ddef=E^'| s⟩⟨ s|.

Observe that when E^'=E, the Hamiltonian ℋ reduces to the
Hamiltonian as originally proposed by Farhi and Gutmann in Ref. <cit.>
. Furthermore, assume that | w⟩ is the normalized
target state while | s⟩ is the normalized initial
state with ⟨ s|w⟩ =x that evolves in an unitary
fashion according to Schrödinger's quantum mechanical evolution law,

    | s⟩↦ e^-i/ℏℋt|
    s⟩,

where the time-independent Hamiltonian ℋ is given in Eq.
(<ref>). We wish to compute the time t^∗ such that the
transition probability 𝒫(  t) defined as,

    𝒫(  t)  def=|⟨
    w|e^-i/ℏℋt|s⟩| ^2,

 assumes its maximum value 𝒫(  t^∗)  =𝒫_max. Introducing the orthonormal basis
{| w⟩, | r⟩} with | r⟩def=(
1-x^2)  ^-1/2(  | s⟩ -x|
w⟩) and | s⟩def
=x| w⟩ +√(1-x^2)| r⟩,
after some straightforward but tedious matrix algebra computations, the
explicit expression 𝒫(  t; x, E,
E^') of 𝒫(  t) in Eq. (<ref>) becomes

    𝒫(  t; x, E, E^')
    =x^2(  1+γ)  ^2/4x^2γ+(  1-γ)  ^2sin^2(  1/2ℏ√(4x^2EE^'+(  E^'-E)  ^2)t)  +x^2cos^2(  1/2ℏ√(4x^2EE^'+(  E^'-E)  ^2
    )t)  ,

where γdef=E^'/E in Eq. (<ref>). Observe
that for E=E^', we recover from the expression of 𝒫(
t; x, E, E^') in Eq. (<ref>) the
original fidelity expression as obtained by Farhi and Gutmann in Ref.
<cit.>,

    𝒫_Farhi-Gutmann(  t; x, E)
    =sin^2(  Ex/ℏt)  +x^2cos^2(  Ex/ℏt)  .

To find the instant t^∗ for which 𝒫(
t^∗; x, E, E^')  =𝒫_max,
we proceed as follows. First, from Eq. (<ref>), we observe that
𝒫_max equals

    𝒫_max(  x, γ)  =x^2(
    1+γ)  ^2/4x^2γ+(  1-γ)  ^2.

In Fig. 1, we present the contour plot that exhibits γ v.s. x with
1≤γ≤10 and 0≤ x<1. In particular, the level curves are
defined by the relation 𝒫_max(  x, γ)
=c (with 𝒫_max(  x, γ)  =𝒫
_g^max in Eq. (<ref>)) where c is a constant with numerical
values such that 0.1≤ c<1. As a side remark, notice that when
E=E^', that is γ=1, 𝒫_max=1 for any value of
x in agreement with what was reported in Ref. <cit.>.
Second, the instant t^∗ for which 𝒫(  t^∗;
x, E, E^')  =𝒫_max with
𝒫(  t; x, E, E^') and
𝒫_max in Eqs. (<ref>) and (<ref>), respectively,
satisfies the relation

    1/2ℏ√(4x^2EE^'+(  E^'-E)  ^2
    )t^∗=π/2,

that is, since E^'=γ E,

    t^∗(  x, γ)  def=πℏ/2E2/√(4x^2γ+(  1-γ)  ^2)
    .

Once again, observe that in the limiting case of γ=1, we recover the
original relation found in Ref. <cit.>,

    t_Farhi-Gutmann^∗(  x)  def=
    πℏ/2E1/x.

We recall that at the end of Section II, we stated that the quantity δ
can depend on specific properties of the Hamiltonian ℋ in
Eq. (<ref>). By using Eqs. (<ref>) and (<ref>), we can
finally obtain the explicit functional form of δ in terms of the two
parameters x and γ,

    δ=δ(  x, γ)  def=cos
    ^-1[  (  1+γ)  x/√((  1-γ)
    ^2+4γ x^2)]  .

Using Eq. (<ref>), we present in Fig. 2 a plot of δ(
x) versus x for a number of fixed values of γ greater than
one. Finally, observe that for γ=1, δ(  x, 
γ)  =0 for any choice of x and we recover the limiting case
discussed in Ref. <cit.>.





§ LOWER BOUNDS ON THE FIDELITY VALUES


Having introduced the parameter δ in a general setting in Section II
(see Eq. (<ref>)) and in a more specific framework in Section III
(see Eq. (<ref>)), we would like to address in Section IV the
following question: How big can δ be chosen? In principle, we could
arbitrarily choose a nearly optimal threshold value of the error probability
for quantum search. However, in what follows, we propose a way to justify to a
certain extent this arbitrariness with some plausible line of reasoning.
First, at the end of the search, we expect that the approximate and the exact
target states will be very close. Therefore, the error probability for quantum
search (that is, its deviation from the unit fidelity) will be very
small. Second, since these target states have a large overlap, it will be
difficult to distinguish them. Therefore, we also expect that the error
probability for quantum state discrimination will be large. Given these two
considerations, it is intuitive that in our working conditions the error
probability for quantum search will be smaller than the error probability for
quantum state discrimination. However, even in the presence of large overlaps
between quantum states, it is possible to device highly successful quantum
state discrimination protocols where the minimum error probability can be made
arbitrarily small. We propose to select the minimum success probability values
for quantum search by imposing that the deviation from the unit fidelity is
smaller than the smallest (compatible with realistic finite-precision quantum
measurements) minimum error probability achievable in highly successful
quantum state discrimination protocols for quantum states with very large overlaps.

If we desire to consider a very small departure Δℱ(  δ) from the unit fidelity,

    Δℱ(  δ)  def=ℱ
    _optimal-ℱ_nearly-optimal(  δ)
    =1-cos^2(  δ)  ,

we expect 0≤1-cos^2(  δ)  ≤ε
with 0≤ε≪1, that is 

    0≤δ≤δ_max(  ε)  def
    =cos^-1(  √(1-ε))  .

Therefore, the question becomes: How small should the real
 parameter ε in Eq. (<ref>) be
chosen? How do we select this value? Can we physically motivate such a choice
for ε? In what follows, motivated by theoretical quantum state
discrimination principles <cit.> and acknowledging the
presence of imperfections in actual quantum measurement settings that limit
the precision of the measurement of angles <cit.>, we propose
a way to select the numerical upper (lower) bounds for δ (
ℱ_nearly-optimal(  δ)). 

We recall that the goal in a quantum state discrimination problem is to
identify the actual state of a quantum system that is prepared, with a fixed
prior probability, in a specific but unknown state that belongs to a
finite set of given possible states <cit.>. An essential
property of quantum mechanics is that two pure states cannot be distinguished
perfectly, if they are not orthogonal. Therefore, there are fundamental
limitations in quantum state discrimination protocols on the success with
which one can determine the actual state. Specifically, when the possible
states are not mutually orthogonal, it is not possible to develop a
state-distinguishing protocol that can discriminate between them perfectly.
Relevant state-distinguishing techniques are the unambiguous
<cit.> and the ambiguous
<cit.> state discrimination schemes. Unambiguous
state discrimination requires that, whenever a definite (that is, conclusive)
outcome is recorded after the measurement, the result must be error free
(that is, unambiguous). When the measurement fails to provide a definite
outcome, a nonzero probability of inconclusive outcomes has to be taken into
consideration. Then, the optimum unambiguous discrimination scheme is realized
when the failure probability (that is, the probability of inconclusive
outcomes) is minimum. On the contrary, ambiguous state discrimination requires
that a conclusive outcome has to be recorded in each single measurement. This
in turn implies that the discrimination is ambiguous since errors in the
conclusive result are unavoidable. Based on the measurement outcome, a guess
is made as to what the actual state of the quantum system was. Then, the
optimum ambiguous discrimination scheme is obtained when the error probability
(that is, the probability of making a wrong guess) is minimum. For a very
instructive discussion on how to interpret the original Farhi-Gutmann analog
quantum search algorithm as a method for improving the distinguishability of a
set of Hamiltonians by adding a controlled driving term, we refer to Ref.
<cit.>.

Being in the framework of ambiguous quantum state discrimination, assume that
we are given one of two normalized quantum states |ψ
_1⟩ =| w⟩ and |ψ
_2⟩ =|w̃⟩, not necessarily
orthogonal, with prior probabilities p_1=p_w and p_2
def=1-p_1=p_w̃, respectively. Furthermore,
assume we have been asked to optimally determine which state we have actually
been given. It happens that the minimum error probability
p_E(  δ) is given by <cit.>,

    p_E(  δ)  =1/2(  1-√(1-4p_wp_w̃
    cos^2(  δ)  ))  .

From Eq. (<ref>), we note that the minimum error probability p_E is a
monotonic increasing function of the quantum mechanical overlap ⟨
w|w̃⟩def=cos(  δ).
In particular, when δ approaches zero (that is, very large quantum
overlap) and p_w=p_w̃, it can become quite challenging to
distinguish the state |ω̃⟩ from the state
|ω⟩ since the probability of making an incorrect
guess approaches 50%. Alternatively, we point out that in the
presence of large asymmetry between the prior probabilities p_w and
p_w̃, the success of the discrimination protocol increases and, as
a consequence, it becomes less difficult to discriminate between |
w⟩ and |w̃⟩. For instance, when
p_w̃=10^-2p_w, the minimum error probability p_E approaches
the liming value 10^-2 as the angle δ approaches zero. We observe
that the quantum mechanical overlap ⟨ w|w̃⟩
plays a key role in both quantum state discrimination and nearly optimal
analog quantum search. In the former case, it is the essential quantity that
sets a bound to the effectiveness of the discrimination scheme. In the latter
case, it quantifies the departure from the perfect unit fidelity. In
view of the above mentioned considerations, it becomes useful to define an
approximate target state |w̃⟩ as a quantum
state with a nearly optimal fidelity ℱ_nearly-optimal
(  δ)  def=cos^2(  δ) that departs from the unit perfect fidelity ℱ_optimal
def=1 by an amount Δℱ(
δ)  def=ℱ_optimal
-ℱ_nearly-optimal(  δ). We impose that
the quantity Δℱ(  δ) is smaller than the
minimum error probability p_E(  δ) in Eq. (<ref>),

    0≤Δℱ(  δ)  def
    =ℱ_optimal-ℱ_nearly-optimal(
    δ)  ≤ p_E(  δ)  .

Eq. (<ref>) implies that we choose to select the lower bounds
of the nearly optimal fidelity values {ℱ
_nearly-optimal(  δ)  } in such a manner
that their deviations {Δℱ(  δ)
} from the unit fidelity ℱ_optimal are less
than the minimum error probability p_E(  δ)
characterizing the optimum ambiguous discrimination scheme between the two
nonorthogonal quantum states {|ω̃⟩, |ω⟩} (that is, the approximate
and the exact target states, respectively) yielding the chosen nearly optimal
fidelity values. A plot of p_E(  δ) as a function of the
angle δ for a variety of sets of a priori probabilities appears
in Fig. 3.  We point out that the proposed inequality in Eq.
(<ref>) is reminiscent of the (sandwich) Fuchs-van de Graaf inequalities
relating the trace norm distance and the fidelity as suitable measures of
closeness for quantum states <cit.>. Indeed, the trace norm distance
appears in the expression for the minimum error probability while the fidelity
appears in the equation for the transition probability in our discussion. For
the sake of completeness, we also remark that while Fuchs and van de Graaf
were only concerned with the problem of distinguishing between two quantum
states with equal a priori probabilities, an
extension of their analysis to the case of arbitrary a priori
probabilities can be found in Ref. <cit.>. As a final consideration, we
emphasize that in the limiting case of equal a priori
probabilities together with the conditions 0≤δ≪
1, it is straightforward to verify that our inequality in Eq.
(<ref>) can be obtained from the Fuchs-van de Graaf inequalities. In
particular, as explained below, the sharpness of the bounds that we propose in
Eq. (<ref>) can be tuned by means of the degree of asymmetry that
specifies the a priori probabilities of the two quantum states being distinguished.

Recalling Eq. (<ref>), the problem was the determination of how small
the real parameter ε in Eq. (<ref>) should be. We
are now in the condition to provide an answer to this issue. We note that,
after some straightforward algebra and using Eq. (<ref>), the inequality
constraint in Eq. (<ref>) yields

    0≤δ≤δ_max(  p̅_w)  def=cos^-1[  √(1-p̅_w(  1-p̅
    _w)  )]  .

The quantity p̅_w in Eq. (<ref>) denotes a fixed value of the
prior probability p_w. Knowing that p̅_w̃+ p̅_w=1
and setting p̅_w̃=αp̅_w with α being the
degree of asymmetry between the two a priori probabilities p̅_w̃ and p̅_w, Eq. (<ref>) becomes

    0≤δ≤δ_max(  α)  def
    =cos^-1[  √(1-α(  1+α)  ^-2)]
    .

We observe that in the maximally symmetric scenario, we have (  p̅_w, p̅_w̃)  =(  1/2, 1/2)
(that is, α=1). Instead, in the maximally asymmetric scenario, we have
(  p̅_w, p̅_w̃)  =(  1,
0) (that is, α≪1) or (  p̅_w, p̅_w̃)  =(  0, 1) (that is, α≫
1). Equating Eqs. (<ref>) and (<ref>), we obtain a formal
expression for ε in terms of the degree of asymmetry coefficient
α,

    ε(  α)  def=α(
    1+α)  ^-2.

From Eq. (<ref>), we note that to get an ε of the order
of 10^-2 ≪1, one needs to have α of the order of 10^2. As previously mentioned, highly successful discrimination
protocols characterized by very small minimum error probability values can be
obtained when strong asymmetries between the prior probabilities p_w and
p_w̃ occur. In such cases, the values of δ_max
(  p̅_w) can be rather small. For instance, when
p_w=10^3p_w̃, δ_max≃3.16×10^-2 and
ℱ_nearly-optimal≥0.999. We point out that this order
of magnitude of angles is quite small. Indeed, in real world settings one
necessarily deals with imperfect measurements where intrinsic uncertainties
yielding non-negligible systematic errors may be present. For instance, the
intrinsic uncertainty of a polarization rotor, typically of the order of
2^o-4^o on the Bloch sphere (where 1^o
≃1.75×10^-2 rad.), limits the precision of the measurement on a
polarization qubit <cit.>.

For the sake of clarity, we point out that in our numerical calculations that
appear into the next section, the two a priori probabilities
p_w and p_w̃ will not be arbitrarily chosen. They will be
chosen in such a manner to yield highly successful discrimination protocols in
which it is not difficult to discriminate between the exact and approximate
quantum states despite their high degree of overlap. Such protocols are
characterized by very low minimum error probability, which, in turn, is
achievable when there is a sufficient degree of asymmetry α between the
two a priori probabilities corresponding to the two
states that we wish to distinguish (see Fig. 3). Then, to a larger
α there corresponds a smaller ε. Specifically, we shall be
considering asymmetries of the order of 10^2 since they yield minimum
error probability values of the order of 10^-2 which are low enough for
high degree of overlaps specified by angles of the order of 10^-2 rad.
Then, being in the framework of highly successful quantum discrimination
protocols, we choose the accuracy the search has to achieve by imposing that
the departure Δℱ of the unit
fidelity ℱ_optimal from the nearly
optimal desired fidelity value ℱ_nearly-optimal
must be smaller than the already small minimum error probability p_E.
Imposing that δ_max is of the order of the maximum achievable
angular resolution in a typical quantum mechanical experiment <cit.>,
we find how asymmetric the two a priori probabilities must be chosen in
order to guarantee the required accuracy the search should achieve.

In what follows, we compare the performances of the original and the modified
Farhi-Gutmann analog quantum search algorithms. Clearly, both algorithms are
stopped when they reach the same chosen lower bound.



§ COMPARISON OF THE TWO SEARCH ALGORITHMS


In this section, we identify a two-dimensional parametric region
where the original algorithm is outperformed by the modified one provided one
focuses on nearly optimal fidelity values compatible with the maximum
resolution of the previously mentioned quantum discrimination protocol. For
the sake of convenience, we shall refer to the original Farhi-Gutmann
algorithm (γ=1) as the special algorithm while the
general algorithm denotes the modified version of the Farhi-Gutmann
algorithm where E^'=γ E with γ≥1. The transition
probability 𝒫(  t; x, E, E^') with E^'=γ E obtained for the general scenario
in Eq. (<ref>) is denoted as,

    𝒫_g(  t)  =x^2(  1+γ)
    ^2/4x^2γ+(  1-γ)  ^2sin^2(  E/2ℏ√(4x^2γ+(  1-γ)  ^2)t)
    +x^2cos^2(  E/2ℏ√(4x^2γ+(
    1-γ)  ^2)t)  .

The maximum value of 𝒫_g(  t) in Eq.
(<ref>) is obtained at the time t̅_g,

    t̅_gdef=h/4E2/√(4x^2γ+(  1-γ)  ^2),

and, furthermore,

    𝒫_g^maxdef=𝒫_g
    (  t̅_g)  =x^2(  1+γ)  ^2
    /4x^2γ+(  1-γ)  ^2.

Setting γ=1, we recover the main findings of Farhi and Gutmann.
Specifically, the transition probability 𝒫_g(
t) in Eq. (<ref>) reduces to 𝒫_s(
t)  def=𝒫_Farhi-Gutmann(
t; x, E) in Eq. (<ref>). The maximum value of
𝒫_s(  t) is obtained at the time t̅_s,

    t̅_sdef=h/4Ex,

and, furthermore,

    𝒫_s^maxdef=𝒫_s
    (  t̅_s)  =1.

We propose to rank the performance of the two algorithms in two different ways
given that Eq. (<ref>) is satisfied: i) rank the two algorithms by
comparing the two transitions probabilities evaluated at an identical
fixed-value of the travel time; ii) rank the two algorithms by comparing the
two minimum travel times needed to arrive at an identical fixed-value of the
transition probability.In the first scenario, since t̅_g≤t̅_s, we wish to determine whether or not there is, for a fixed
value of t̅_g less than t̅_s, a
two-dimensional parametric region ℛ_t(  x, 
γ),

    ℛ_t(  x, γ)  def
    ={(  x, γ)  ∈(  0, 1)
    ×[  1, ∞)  :𝒫_g^max-𝒫_s(  t̅_g)  >0},

where the general algorithm outperforms the special algorithm in terms of
transition probability values in the working assumption of accepting
transition probability values less than one.

In the second scenario, since 𝒫_g^max≤𝒫_s^max, we wish to determine whether or not there is,
for a fixed value of 𝒫_g^max less than one, a
two-dimensional parametric region ℛ_𝒫(  x,
γ),

    ℛ_𝒫(  x, γ)  def
    ={(  x, γ)  ∈(  0, 1)
    ×[  1, ∞)  :t̅_g/t̃_s<1},

where the general algorithm outperforms the special algorithm in terms of
minimum travel times at fixed nearly optimal transition probability values.

Note that t̃_s in Eq. (<ref>) is such that,

    𝒫_s(  t̃_s)  =𝒫
    _g^max,

where, after some algebraic manipulations, we find

    t̃_sdef=h/2π Excos^-1[
    (  1-x^2(  1+γ)  ^2/4x^2γ+(
    1-γ)  ^2/1-x^2)  ^1/2]  .

We emphasize that both two-dimensional parametric regions ℛ
_t(  x, γ) and ℛ_𝒫(
x, γ) in Eqs. (<ref>) and (<ref>), respectively,
are non-empty sets and in addition, it can be numerically verified that they
are identical. Moreover, for the sake of completeness we also point out that
one can investigate whether or not the general algorithm outperforms the
special one for a given transition probability threshold 𝒫
_threshold given that Eq. (<ref>) is satisfied. For this
reason, we consider the following sub-region r_𝒫(  x,
γ) of ℛ_𝒫(  x, 
γ) in Eq. (<ref>),

    r_𝒫(  x, γ)  def
    ={(  x, γ)  ∈(  0, 1)
    ×[  1, ∞)  :t̅_g/t̃_s<1, and 𝒫_g^max>𝒫
    _threshold}.

A plot of the two-dimensional parametric region r_P(  x, 
γ) in Eq. (<ref>) where the general algorithm
outperforms the special algorithm when assuming 𝒫_threshold
=99.5% and p_w=10^2p_w̃ appears in Fig. 4.

Finally, for the sake of clarity, we also present in Table I illustrative
numerical estimates of t̅_gdef=t_FG
^(  general) in Eq. (<ref>) and t̃_sdef=t_FG^(  special
) in Eq. (<ref>) for a number of selected values of the threshold
probability 𝒫_g^max in Eq. (<ref>) under the
working assumptions that γ=1.1 and h=E=1. Given the chosen values of
the angle δ in Table I, the numerical estimates of the minimum error
probability p_E are calculated by assuming p_w=10^2p_w̃
which yields a maximum value of δ that equals δ_max
≃9.92×10^-2.

As a further clarifying remark, we point out that the numerical values
(originated from our proposed comparison of the two algorithms and reported in
Table I) were computed by considering the minimum time such that the desired
success probability values were obtained. We have simply chosen the desired
success probability values to be equal to the maximal success probability
values of the modified algorithm in our analysis. However, as evident from
Fig. 5, we could have chosen different threshold values (leading to
shorter minimum times) and still outperform the original algorithm (provided
that only a nearly optimal search is considered). As a side remark, we
emphasize that this line of reasoning extends naturally to any desired success
probability value taken as the maximal success probability
𝒫_threshold=𝒫_g^max
with 𝒫_g^max=𝒫_g^max(  x, γ) in Eq. (<ref>) and where the
points {(  x, γ)  }
can be chosen to belong to the black-colored region in Fig. 4.
Specifically, in Fig. 5 we plot 𝒫_g(  t)
(dashed line) and 𝒫_s(  t) (solid
line) as a function of time t. For the sake of reasoning,
we set h=1, E=1, x=0.80, and
γ=1.1. The two horizontal lines in Fig. 5 denote two
selected success probability values, 𝒫_threshold
^max=0.9987 (dotted line) and 𝒫
_threshold=0.9 (dotted-dashed line). The threshold
value 0.9987 was taken from the fourth line in Table
I. We note that the minimum time such that the two desired success
probability values are obtained is smaller in the case of the modified
algorithm for both selected thresholds. Specifically, in the first and second
scenarios, we have 1.93×10^-1 ≤2.02×
10^-1 and 2.97×10^-1 ≤3.01×10^-1, respectively. Note that in the MKSA unit system, [
t]  _MKSA=[  h]  _MKSA[  E]
_MKSA^-1. Since we have considered E=1=h in
our numerical computations, time t is assumed to be dimensionless.

Finally, for a more detailed discussion on the probability of
small and large numerical values of the quantum overlap x, we refer to
Appendix A.



§ CONCLUDING REMARKS


In this paper, we focused on the problem of nearly optimal state searching and
we demonstrated that it is possible to modify the original Farhi-Gutmann
search Hamiltonian (see Eq. (<ref>)) in order to speed up the
procedure for finding a suitably distributed unknown normalized quantum state
| w⟩ under the working assumption that only a nearly
optimal fidelity is achieved,

    𝒫_max(  δ)  def=cos
    ^2(  δ)  ,

with 0≤ δdef=cos^-1[
⟨ w|w̃⟩]  ≪1 where
| w⟩ and |w̃⟩ denote the exact and the approximate target
states, respectively. More specifically, upon relaxing the working
assumptions of exact state overlap and uniform distribution of the target
state on the unit sphere in the N-dimensional complex Hilbert space,
we showed that the proposed algorithm (see Eq. (<ref>)) can indeed
outperform the original analog counterpart of a quantum search algorithm. This
enhanced performance occurs for a convenient choice of both the ratio
γdef=E^'/E between the eigenvalues of the
modified search Hamiltonian and the quantum mechanical overlap xdef=⟨ w|s⟩ between the initial (
| s⟩) and the target (  |
w⟩) states.

In summary, the main results of our work can be described as follows. First,
we extended the optimality proof presented in Ref. <cit.> to the case
of nearly optimal state searching and determined that the minimum time
interval to find the target state with probability 𝒫_max(
δ)  def=cos^2(  δ) is
given by (see Eq. (<ref>)),

    t̃_min^(  approximate)  def
    =ℏ/2E(  1-δ)  √(N).

Second, we computed the transition probability 𝒫(  t;
x, E, E^') (see Eq. (<ref>)) that arises
from our proposed search algorithm and determined its maximum value
𝒫_max(  x, γ) (see Eq. (<ref>) and
Fig. 1) together with the instant t^∗(  x, γ) (see Eq. (<ref>)) at which this maximum is achieved. Third,
from the formal introduction of the quantity δ in Eq. (<ref>)
and the expression of 𝒫_max(  x, γ) in
Eq. (<ref>), we found an explicit expression for the quantity
δ=δ(  x, γ) (see Eq. (<ref>
) and Fig. 2) responsible for our imperfect state search in terms of the two
parameters x and γ that characterize our search Hamiltonian,

    δ(  x, γ)  def=cos^-1[
    (  1+γ)  x/√((  1-γ)  ^2+4γ
    x^2)]  .

Fourth, we introduced the notion of approximate target state |w̃⟩. Such a quantum state |w̃⟩ is characterized by a sufficiently large overlap with the
exact target state | w⟩ so that, as we proposed, the
deviation Δℱ(  δ) from the unit fidelity
ℱ=1 is smaller than the minimum error probability p_E(
δ) achievable in an optimal quantum state discrimination
protocol (see Fig. 3) for the set of quantum states {|
w⟩, |w̃⟩},

    0≤Δℱ(  δ)  =1-cos^2(  δ)
    ≤ p_E(  δ)  ,

with p_E(  δ) defined in Eq. (<ref>). Finally, using
numerical methods, we showed that for a fixed transition probability threshold
0≤𝒫_threshold<1 and suitably chosen non-uniform
probability distribution functions of the target state on the unit sphere (see
Eq. (<ref>)), there exist two-dimensional parametric regions r_P(
x, γ) (see Eq. (<ref>)) in which the proposed
algorithm outperforms the original one in terms of speed (see Fig. 4, Table
I, and Fig. 5) for the special task (namely, finding the approximate target
state) it sets out to solve.

We believe that our analysis presented in this paper can serve as a relevant
starting point for a more rigorous investigation that would include both
theoretical and experimental aspects of the tradeoff between fidelity and run
time of quantum search algorithms. For instance, it is known that to mitigate
the effect of decoherence originating from the interaction of a quantum system
with the environment, it is helpful to decrease the control time of the
control fields employed to generate a target quantum state or a target quantum
gate. Simultaneously, to enhance the fidelity of generating such targets and
reach values arbitrarily close to the maximum ℱ=1, it may be
convenient to increase the control time beyond a certain critical value. When
the control time reaches a certain value that may be close to the just
mentioned critical value however, decoherence can become a dominant effect.
Therefore, investigating the tradeoff between fidelity and time control can be
of great practical importance in quantum computing
<cit.>. For instance, one can design
algorithms seeking suboptimal control solutions for much reduced computational
effort, since it is very challenging to find a rigorous optimal time control
and in many cases the control is only required to be sufficiently precise and
short. For example, the fidelity of tomography experiments is rarely above
99% due to the limited control precision of the tomographic experimental
techniques as pointed out in Ref. <cit.>. Under such conditions, it
is unnecessary to prolong the control time since the departure from the
optimal scenario is essentially negligible. Hence, it can certainly prove
worthwhile to design slightly suboptimal algorithms that can be much cheaper
computationally. Our analysis can be improved in a number of ways. First, our
work can be strengthened by explicitly considering the quantum measurement
process in our analysis. For instance, it is known that quantum measurement
can be regarded as a decoherence process that potentially enhance or reduce a
transition probability between two quantum states <cit.>. Second, as a
starting point of our investigation, we could consider a more general
time-independent search Hamiltonian where the probability of obtaining the
target state can be very large and nearly one <cit.>. Furthermore, in
order to work in a more realistic setting, nearly optimal time-dependent
search Hamiltonians specified in terms of the so-called schedule function of
the search algorithm could also be considered <cit.>. Finally, from a
more ambitious perspective, we could explore the manner in which recent
investigations on intelligent forms of quantum searching algorithms in the
presence of imperfections, with the help of techniques borrowed from quantum
machine learning <cit.>, would connect to our nearly optimal quantum
search problem.

In conclusion, we hope to pursue a more rigorous and realistic
analysis that includes these intriguing theoretical and experimental aspects
in forthcoming scientific efforts.


C. C. is grateful to the United States Air Force Research Laboratory (AFRL)
Summer Faculty Fellowship Program for providing support for this work. Any
opinions, findings and conclusions or recommendations expressed in this paper
are those of the authors and do not necessarily reflect the views of AFRL.
Finally, constructive criticism from two anonymous referees leading to an
improved version of this manuscript are sincerely acknowledged by the authors.


99                                                                                               


grover97L. K. Grover, Quantum mechanics helps in searching
for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997).

knuth75D. E. Knuth, The Art of Computer Programming, Vol.
3: Sorting and Searching, Addison-Wesley, Reading, MA (1975).

farhi98E. Farhi and S. Gutmann, Analog analogue of a digital
quantum computation, Phys. Rev. A57, 2403 (1998).

carlo1C. Cafaro and S. Mancini, An information geometric
viewpoint of algorithms in quantum computing, in Bayesian Inference and
Maximum Entropy Methods in Science and Engineering, AIP Conf. Proc.
1443, 374 (2012).

carlo2C. Cafaro and S. Mancini, On Grover's search algorithm
from a quantum information geometry viewpoint, Physica A391, 1610 (2012).

cafaro2017C. Cafaro, Geometric algebra and information
geometry for quantum computational software, Physica A470, 154 (2017).

mandelstam45L. Mandelstam and I. Tamm, The uncertainty
relation between energy and time in non-relativistic quantum mechanics, J.
Phys. USSR 9, 249 (1945).

vaidman92L. Vaidman, Minimum time for the evolution to an
orthogonal quantum state, Am. J. Phys. 60, 182 (1992).

uffink93J. Uffink, The rate of evolution of a quantum state,
Am. J. Phys. 61, 935 (1993).

margolus98N. Margolus and L. B. Levitin, The maximum speed of
dynamical evolution, Physica D120, 188 (1998).

levitin09L. B. Levitin and T. Toffoli, Fundamental limit on
the rate of quantum dynamics: The unified bound is tight, Phys. Rev. Lett.
103, 160502 (2009).

trifonov99J. Soderholm, G. Bjork, T. Tsegaye, and A. Trifonov,
States that minimize the evolution time to become an orthogonal state,
Phys. Rev. A59, 1788 (1999).

giovannetti03V. Giovannetti, S. Lloyd, and L. Maccone,
Quantum limits to dynamical evolution, Phys. Rev. A67, 052109 (2003).

partoviM. H. Partovi, Entropic formulation of uncertainty for
quantum measurements, Phys. Rev. Lett. 50, 1883 (1983).

furusawaH. F. Hofmann, T. Kobayashi, and A. Furusawa,
Correlations of measurement information and noise in quantum
measurements with finite resolution, arXiv:quant-ph/0003067 (2000).

fritz10T. Fritz, Transition probabilities and measurement
statistics of postselected ensembles, J. Math. Phys. 51, 082105 (2010).

chefles00A. Chefles, Quantum state discrimination,
Contemporary Physics 41, 401 (2000).

croke09S. M. Barnett and S. Croke, Quantum state
discrimination, Advances in Optics and Photonics 1, 238 (2009).

gisin12D. Rosset, R. Ferretti-Schöbitz, J.-D. Bancal, N. Gisin,
and Y.-C. Liang, Imperfect measurement settings: Implication for quantum
state tomography and entanglement witnesses, Phys. Rev. A86, 062325 (2012).

mario18M. T. Di Mario and F. E. Becerra, Robust measurement
for the discrimination of binary coherent states, Phys. Rev. Lett.
121, 023603 (2018).

ivanovic87I. D. Ivanovic, How to differentiate between
non-orthogonal states, Phys. Lett. A123, 257 (1987).

dieks88D. Dieks, Overlap and distinguishability of quantum
states, Phys. Lett. A126, 303 (1988).

peres88A. Peres, How to differentiate between non-orthogonal
states, Phys. Lett. A128, 19 (1988).

holevo73A. S. Holevo, Statistical decision theory for quantum
systems, J. Multivariate Analysis 3, 377 (1973).

yuen75H. P. Yuen, R. S. Kennedy, and M. Lax, Optimum testing
of multiple hypotheses in quantum detection theory, IEEE Trans. Inf. Theory
IT-21, 125 (1975).

helstrom76C. W. Helstrom, Quantum Detection and Estimation
Theory, Academic Press, New York (1976).

childs00A. M. Childs, J. Preskill, and J. Renes, Quantum
information and precision measurement, J. Mod. Optics 47, 155 (2000).

fuchs99C. A. Fuchs and J. van de Graaf, Cryptographic
distinguishability measures for quantum-mechanical states, IEEE Trans. Inf.
Theor. 45, 1216 (1999).

mr14K. M. R. Audenaert, Comparisons between quantum state
distinguishability measures, Quantum Information and Computation 14,
31 (2014).

rabitz12K. W. Moore Tibbetts, C. Brif, M. D. Grace, A. Donovan, D.
L. Hocker, T.-S. Ho, R.-B. Wu, and H. Rabitz, Exploring the tradeoff
between fidelity and time optimal control of quantum unitary transformations,
Phys. Rev. A86, 062309 (2012).

rabitz15Q.-M. Chen, R.-B. Wu, T.-M. Zhang, and H. Rabitz,
Near-time-optimal control for quantum systems, Phys. Rev. A92,
063415 (2015).

cappellaro18M. Hirose and P. Cappellaro, Time-optimal control
with finite bandwidth, Quantum Information Processing 17, 88 (2018).

kwon02J. Bae and Y. Kwon, Generalized quantum search
Hamiltonian, Phys. Rev. A66, 012314 (2002).

chuang17A. M. Dalzell, T. J. Yoder, and I. L. Chuang,
Fixed-point adiabatic quantum search, Phys. Rev. A95, 012311 (2017).

lloyd17J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N.
Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).

paris18L. Ghirardi, I. Siloi, P. Bordone, F. Troiani, and M. G. A.
Paris, Quantum metrology at level anticrossing, Phys. Rev.
A97, 012120 (2018).

karol10K. Bartkiewicz and A. Miranowicz, Optimal cloning of
qubits given by an arbitrary axisymmetric distribution on the Bloch sphere,
Phys. Rev. A82, 042330 (2010).

kang16P. Kang, H.-Y. Dai, J.-H. Wei, and M. Zhang, Optimal
quantum cloning based on the maximin principle by using a priori information,
Phys. Rev. A94, 042304 (2016).

cafaropreC. Cafaro and S. A. Ali, Maximum caliber inference
and the stochastic Ising model, Phys. Rev. E94, 052145 (2016).

fletcher07A. S. Fletcher, P. Shor, and M. Z. Win,
Channel-adapted quantum error correction for the amplitude damping
channel, IEEE Trans. Inf. Theor. 54, 5705 (2008).

cafaro14C. Cafaro and P. van Loock, Approximate quantum error
correction for generalized amplitude-damping errors, Phys. Rev. A89,
022316 (2014).

cafaroosidC. Cafaro and P. van Loock, A simple comparative
analysis of exact and approximate quantum error correction, Open Systems &
Information Dynamics 21, 1450002 (2014).

briegel15M. Tiersch, E. J. Ganahl, and H. J. Briegel,
Adaptive quantum computation in changing environments using projective
simulation, Scientific Reports 5, 12874 (2015).

briegel16V. Dunjko, J. M. Taylor, and H. J. Briegel,
Quantum-enhanced machine learning, Phys. Rev. Lett. 117,
130501 (2016).









§ NUMERICAL VALUES OF THE QUANTUM OVERLAP


In this Appendix, we present a more in depth discussion on the probability of
small and large numerical values of the quantum overlap x.

In general, one may argue that large values of the overlap x are not very
typical or particularly realistic since they occur when the source state is
essentially already the desired target state. This objection has its merit
when one assumes that the realistic scenario is the one in which no a
priori information on the target state is available and, in particular, the
target state is assumed to be a normalized vector in a list of N possible
orthonormal states. Indeed, within these working assumptions, x=N^-1/2 and the largest value of x that would be considered realistic is
obtained for N=4 and equals x=1/2. However, one can envision a
circumstance in which a priori relevant knowledge is available
so that the target state is a suitably chosen non-uniformly distributed
normalized vector in a N-dimensional vector space. In such a scenario, the
probability of occurrence of large values of x can begin to be
non-negligible. Thus, large values of x can become realistic in these new
working conditions. We point out that a priori knowledge happens to be
useful in both quantum metrology and imperfect (optimal) quantum cloning. In
the former case, in order to design the best parameter estimation scheme, some
form of a priori knowledge of such a parameter is required
<cit.>. In the latter case, instead, knowledge of the distribution of
qubits on the Bloch sphere that encodes some a priori information on a
given quantum state that one desires to clone is taken advantage of in order
to achieve the highest fidelity <cit.>. For instance, in the
specific framework of phase-independent quantum cloning, one assumes to clone
qubits that are a priori known to be symmetrically distributed around
the Bloch vector <cit.>.

As pointed out in Section II, the optimality proof by Farhi and Gutmann occurs
under the special working assumption that the target state |
w⟩ is an unknown element of a given orthonormal basis {| a⟩} with 1≤ a≤ N of an
N-dimensional complex Hilbert space ℋ_2^n with
Ndef=2^n. As pointed out earlier, in this scenario it
is rather unlikely that x=N^-1/2 assumes values close to one. In
their more general setting however, Farhi and Gutmann assume that the target
state | w⟩ is an arbitrary normalized vector in a
N-dimensional complex Hilbert space which is uniformly distributed on
the unit sphere <cit.>.

We briefly recall that the space enclosed by a (  2N-1)-dimensional unit sphere 𝒮^2N-1 is a (2N)-ball whose
infinitesimal volume element in spherical coordinates is given by,

    dV_2N-ball^(  spherical)  def
    =r^2N-1sin^2N-2(  θ_1)  sin^2N-3(  θ
    _2)  ...sin(  θ_2N-2)  drdθ_1dθ
    _2...dθ_2N-2dθ_2N-1,

where θ_i∈[  0, π) for any 1≤ i≤2N-2
and θ_2N-1∈[  0, 2π). Furthermore, the volume
element of the (  2N-1)-dimensional unit sphere generalizes the
concept of the area element of a two-dimensional unit sphere and, from Eq.
(<ref>), is given by

    dV_𝒮^2N-1^(  spherical)  def=sin^2N-2(  θ_1)  sin^2N-3(
    θ_2)  ...sin(  θ_2N-2)  drdθ_1
    dθ_2...dθ_2N-2dθ_2N-1.

Returning to our discussion, we assume that the probability density function
ρ_w(  θ) that describes the distribution of the
states | w⟩ on the (  2N-1)-dimensional
unit sphere depends on the coordinate θ_1, denoted as θ, which
is uniform with respect to the remaining coordinates. Therefore, by
marginalizing over all the unimportant integration variables but θ
with xdef=|⟨ s|w⟩| =cos(  θ) where 0≤θ≤π/2, we
find that the probability that x is greater than a given value x̅ is
given by <cit.>,

    Prob(  x≥x̅)  def=
    ∫_0^cos^-1(  x̅)  ρ_w(
    θ)  [  sin(  θ)  ]  ^2N-2dθ/∫_0^π/2ρ_w(  θ)  [  sin(
    θ)  ]  ^2N-2dθ.

The quantity ρ_w(  θ) in Eq. (<ref>) denotes a
well-defined probability density function (pdf), that is to say, a pdf that is
positive and normalized to one. For the sake of reasoning, we select
| s⟩ to be at the north pole. Generalizations to less
peculiar scenarios are straightforward. In what follows, we provide some
rationale for our choice of ρ_w(  θ). The functional
form of ρ_w(  θ) is essentially that of a Gaussian
with mean μ_θ and variance σ_θ^2 multiplied by a
suitably chosen oscillatory function. The mean is set equal zero, while any
value of μ_θ between 0 and π/2 can be chosen provided that
the variance σ_θ^2 is not too small. Furthermore, the
multiplying factor in the proposed expression of ρ_w(
θ) is chosen in such a manner as to substantially
mitigate the oscillatory behavior of [  sin(  θ)
]  ^2N-2 in Eq. (<ref>) and leads when multiplied with it, to an
approximately constant function over the selected domain of integration.
Practically, one can consider a narrowly distributed Gaussian peaked nearby
the location of the initial state or, for a Gaussian peaked far away from such
a location, the width of the Gaussian has to be suitably larger. Under this
assumption, a convenient choice for our analysis is given by the following
pdf,

    ρ_w(  θ)  def=𝒩exp(  -θ^2/2σ_θ^2)  /1+[
    10sin(  θ)  ]  ^2N-2.

In Eq. (<ref>), 𝒩=𝒩(  N, σ_θ^2) is a normalization factor that depends on the choice of N
and σ_θ^2. For instance, for N=16, σ_θ^2=1,
and x̅=0.95, by means of numerical integration, we find Prob
(  x≥0.95)  ≃21%. We note that with a smaller
σ_θ^2, the probability of x being greater than a selected
value x̅ increases and asymptotically approaches unity. For instance,
for σ_θ^2=10^-1 and σ_θ^2=10^-2, we
observe that Prob(  x≥0.95)  ≃58% and
Prob(  x≥0.95)  ≃99%, respectively. We point
out that if N=16 and ρ_w(  θ) is uniform as
selected in Ref. <cit.>, Prob(  x≥0.95)
≃3.2×10^-17. Therefore, although the probability is not exactly
zero, it is very unlikely that x is close to 1 when assuming uniformity
for ρ_w(  θ). For this reason, we considered here
nearly optimal (imperfect) state searches where the target state is not
uniformly distributed on the unit sphere. As a final remark, we point out that
the assumption that the target state | w⟩ is selected
at random means that we assume absolute ignorance (that is, maximum entropy)
about the location of the target. If we somehow learn an important piece of
information about the location of the target however, one can think of
updating his/her state of knowledge (see Ref. <cit.>, for instance)
about the target with a new probability density function of the state on the
(  2N-1)-dimensional space. As a consequence, the search
algorithm can be adapted to the target in order to improve the efficiency of
the searching scheme. We emphasize that these considerations are reminiscent
of what happens in channel-adapted quantum error correction
<cit.> and adaptive quantum computing
<cit.> where classical learning techniques can be used to enhance
the performance of certain quantum tasks <cit.>. We leave the
exploration of these intriguing ideas to future investigations.
