Non-Boolean Quantum Amplitude Ampification and Quantum Mean Estimation Systems and Methods

Abstract

Generalizations of quantum amplitude amplification and amplitude estimation algorithms work with non-boolean oracles (by way of definition, the action of a non-boolean oracle U.sub.φ on an eigenstate |x is to apply a state-dependent phase-shift φ(x); unlike boolean oracles, the eigenvalues exp(iφ(x)) of a non-boolean oracle are not restricted to be ±1). The non-boolean amplitude amplification algorithm preferentially amplifies the amplitudes of the eigenstates based on the value of φ(x). Starting from a given initial superposition state |ψ.sub.0, the basis states with lower values of cos(φ) are amplified at the expense of the basis states with higher values of cos(φ). The non-boolean quantum mean estimation algorithm uses quantum phase estimation to estimate the expectation ψ.sub.0|U.sub.φ|ψ.sub.0 (i.e., the expected value of exp(iφ(x)) for a random x sampled by making a measurement on |ψ.sub.0). The quantum mean estimation algorithm offers a quadratic speedup over its counterpart boolean algorithm known in the art.

Claims

1. A method of performing quantum calculation on an oracle U.sub.φ for a non-boolean function φ, comprising: initializing an ancilla qubit in a |+ state and an input qubit in a |ψ.sub.0 state of a plurality of eigenstates |x to define a two-register state |Ψ.sub.0≡|+,ψ.sub.0; for each of a plurality K of iterations receiving, using the input qubit, a respective one of the plurality of eigenstates |x defining an input basis state, for odd iterations, acting on the input basis state using a selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and a controlled unitary operator circuit U.sub.φ, and for even iterations, acting on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and a controlled inverse unitary operator circuit U.sub.φ.sup.†.

2. The method according to claim 1, further comprising measuring, after the plurality K of iterations, the ancilla qubit in a 0/1 basis.

3. The method according to claim 1, wherein the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 further comprises: a Hadamard transform H, a unitary operator A.sub.0, a unitary operator I, and an inverse unitary operator A.sub.0.sup.†; wherein the selective phase-flip unitary operator S.sub.Ψ.sub.0=[H.Math.A.sub.0][2|0,00,0|−I][H.Math.A.sub.0.sup.†].

4. The method according to claim 1, wherein the acting on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and the controlled unitary operator circuit U.sub.φ further comprises, for the ancilla qubit in a state |0, acting on the input qubit as U.sub.φ|0,x=e.sup.+iφ(x)|0,x, U.sub.φ|1,x=e.sup.−iφ(x)|1,x.

5. The method according to claim 1, wherein the acting on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and the controlled inverse unitary operator circuit U.sub.φ.sup.† further comprises, for the ancilla qubit in a state |1, acting on the input qubit as U.sub.φ.sup.†|0,x=e.sup.+iφ(x)|0,x, U.sub.φ.sup.†|1,x=e.sup.−iφ(x)|1,x.

6. The method according to claim 1, further comprising: receiving, using the input qubit, the |ψ.sub.0 state defining an input random state; acting on the input random state using a controlled estimation unitary operator circuit U.sub.φ−π/2.

7. The method according to claim 6, wherein the controlled estimation unitary operator circuit U.sub.φ−π/2 further comprises: the controlled unitary operator circuit U.sub.φ, at least one bit-flip operator X, and at least one phase-shift operator R.sub.ϕ; wherein the controlled estimation unitary operator circuit U.sub.φ−π/2=e.sup.−iπ/2|00|.Math.U.sub.φ+e.sup.iπ/2|11|.Math.U.sub.φ.sup.†.

8. A quantum computing device for performing quantum calculation on an oracle U.sub.φ for a non-boolean function φ, comprising: a two-register quantum system comprising an ancilla qubit, and an input qubit; and a non-boolean quantum oracle comprising a selective phase-flip unitary operator circuit S.sub.Ψ.sub.0, a controlled unitary operator circuit U.sub.φ, and a controlled inverse unitary operator circuit U.sub.φ.sup.†; wherein the quantum computing device is configured to initialize the ancilla qubit in a |+ state and the input qubit in a |ψ.sub.0 state of a plurality of eigenstates |x to define a two-register state |Ψ.sub.0≡|+,ψ.sub.0; for each of a plurality K of iterations receive, using the input qubit, a respective one of the plurality of eigenstates |x defining an input basis state, for odd iterations of the plurality K of iterations, act on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and the controlled unitary operator circuit U.sub.φ, and for even iterations of the plurality K of iterations, act on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and the controlled inverse unitary operator circuit U.sub.φ.sup.†.

9. The quantum computing device according to claim 8, further configured to measure, after the plurality K of iterations, the ancilla qubit in a 0/1 basis.

10. The quantum computing device according to claim 8, wherein the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 further comprises: a Hadamard transform H, a unitary operator A.sub.0, a unitary operator I, and an inverse unitary operator A.sub.0.sup.†; wherein the selective phase-flip unitary operator S.sub.Ψ.sub.0=[H.Math.A.sub.0][2|0,00,0|−I][H.Math.A.sub.0.sup.†].

11. The quantum computing device according to claim 8, further configured, for the ancilla qubit in a state |0, to act on the input qubit as U.sub.φ|0,x=e.sup.+iφ(x)|0,x, U.sub.φ|1,x=e.sup.−iφ(x)|1,x.

12. The quantum computing device according to claim 8, further configured, for the ancilla qubit in a state |1, to act on the input qubit as U.sub.φ.sup.†|0,x=e.sup.+iφ(x)|0,x, U.sub.φ.sup.†|1,x=e.sup.−iφ(x)|1,x.

13. The quantum computing device according to claim 8, further comprising a controlled estimation unitary operator circuit U.sub.φ−π/2, and configured to: receive, using the input qubit, the |ψ.sub.0 state defining an input random state; and act on the input random state using the controlled estimation unitary operator circuit U.sub.φ−π/2.

14. The quantum computing device according to claim 13, wherein the controlled estimation unitary operator circuit U.sub.φ−π/2 further comprises: the controlled unitary operator circuit U.sub.φ, at least one bit-flip operator X, and at least one phase-shift operator R.sub.ϕ; wherein the controlled estimation unitary operator circuit U.sub.φ−π/2=e.sup.−iπ/2|00|.Math.U.sub.φ+e.sup.iπ/2|11|.Math.U.sub.φ.sup.†.

15. A system of quantum circuits for implementing an oracle U q for a non-boolean function φ, the system configured to: initialize an ancilla qubit in a |+ state and an input qubit in a |ψ.sub.0 state of a plurality of eigenstates |x to define a two-register state |Ψ.sub.0≡|+,ψ.sub.0; for each of a plurality K of iterations receive, using the input qubit, a respective one of the plurality of eigenstates |x defining an input basis state, for odd iterations of the plurality K of iterations, act on the input basis state using a selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and a controlled unitary operator circuit U.sub.φ, and for even iterations of the plurality K of iterations, act on the input basis state using the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 and a controlled inverse unitary operator circuit U.sub.φ.sup.†.

16. The system according to claim 15, further configured to measure, after the plurality K of iterations, the ancilla qubit in a 0/1 basis.

17. The system according to claim 15, wherein the selective phase-flip unitary operator circuit S.sub.Ψ.sub.0 further comprises: a Hadamard transform H, a unitary operator A.sub.0, a unitary operator I, and an inverse unitary operator A.sub.0.sup.†; wherein the selective phase-flip unitary operator S.sub.Ψ.sub.0=[H.Math.A.sub.0][2|0,00,0|−I][H.Math.A.sub.0.sup.†].

18. The system according to claim 15, further configured, for the ancilla qubit in a state |0, to act on the input qubit as U.sub.φ|0,x=e.sup.+iφ(x)|0,x, U.sub.φ|1,x=e.sup.−iφ(x)|1,x.

19. The system according to claim 15, further configured, for the ancilla qubit in a state |1, to act on the input qubit as U.sub.φ.sup.†|0,x=e.sup.+iφ(x)|0,x, U.sub.φ.sup.†|1,x=e.sup.−iφ(x)|1,x.

20. The system according to claim 15, further configured to: receive, using the input qubit, the |ψ.sub.0 state defining an input random state; and act on the input random state using a controlled estimation unitary operator circuit U.sub.φ−π/2 comprising: the controlled unitary operator circuit U.sub.φ, at least one bit-flip operator X, and at least one phase-shift operator R.sub.ϕ; wherein the controlled estimation unitary operator circuit U.sub.φ−π/2=e.sup.−iπ/2|00|.Math.U.sub.φ+e.sup.iπ/2|11|.Math.U.sub.φ.sup.†.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0023] The preferred embodiments of the invention will hereinafter be described in conjunction with the appended drawings provided to illustrate and not to limit the invention, where like designations denote like elements, and in which:

[0024] FIG. 1 is a schematic diagram depicting an exemplary quantum circuit implementing a selective phase-flip unitary operator for non-boolean amplitude amplification according to an embodiment of the present invention;

[0025] FIG. 2 is a schematic diagram depicting an exemplary quantum circuit implementing a first conditional oracle call unitary operator for a non-boolean amplitude amplification algorithm according to an embodiment of the present invention;

[0026] FIG. 3 is a schematic diagram depicting an exemplary quantum circuit implementing a second conditional oracle call unitary operator for a non-boolean amplitude amplification algorithm according to an embodiment of the present invention;

[0027] FIG. 4 is schematic diagram depicting a quantum circuit for a first exemplary non-boolean amplification algorithm according to an embodiment of the present invention;

[0028] FIG. 5 is pseudocode for a non-boolean amplification algorithm according to FIG. 4;

[0029] FIG. 6 is a state diagram depicting stage evolution of a two-register system through iterations of the non-boolean amplitude amplification algorithm of FIG. 5;

[0030] FIG. 7 is schematic diagram depicting a quantum circuit for a second exemplary non-boolean amplification algorithm according to an embodiment of the present invention;

[0031] FIG. 8 is a non-boolean amplification algorithm according to FIG. 7;

[0032] FIG. 9 is a schematic diagram depicting a quantum circuit for a non-boolean mean estimation algorithm according to an embodiment of the present invention;

[0033] FIG. 10 depicts a graph of oracle function and initial state of a toy example for quantum simulation;

[0034] FIG. 11 depicts a graph of quantum simulation results from application of the non-boolean amplitude amplification algorithm of FIG. 4 to the toy example of FIG. 10; and

[0035] FIG. 12 depicts graphs of quantum simulation results from application of the non-boolean mean estimation algorithm of FIG. 9 to the toy example of FIG. 10.

[0036] Like reference numerals refer to like parts throughout the several views of the drawings.

DETAILED DESCRIPTION OF THE INVENTION

[0037] The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.

[0038] Although the following detailed description contains many specifics for the purposes of illustration, anyone of ordinary skill in the art will appreciate that many variations and alterations to the following details are within the scope of the invention. Accordingly, the following embodiments of the invention are set forth without any loss of generality to, and without imposing limitations upon, the claimed invention.

[0039] As used herein, the word “exemplary” or “illustrative” means “serving as an example, instance, or illustration.” Any implementation described herein as “exemplary” or “illustrative” is not necessarily to be construed as preferred or advantageous over other implementations. All of the implementations described below are exemplary implementations provided to enable persons skilled in the art to make or use the embodiments of the disclosure and are not intended to limit the scope of the disclosure, which is defined by the claims.

[0040] Furthermore, in this detailed description, a person skilled in the art should note that quantitative qualifying terms such as “generally,” “substantially,” “mostly,” and other terms are used, in general, to mean that the referred to object, characteristic, or quality constitutes a majority of the subject of the reference. The meaning of any of these terms is dependent upon the context within which it is used, and the meaning may be expressly modified.

[0041] Referring initially to FIGS. 1-9, a non-boolean quantum amplitude amplification algorithm, as also a quantum mean estimation algorithm based in the non-boolean quantum amplitude amplification algorithm, both according to embodiments of the present invention are now described in detail. Throughout this disclosure, the present invention may be referred to as a family of non-boolean quantum amplitude amplification algorithms, a family of non-boolean quantum algorithms, a non-boolean quantum algorithm, a non-boolean quantum method, a non-boolean quantum oracle, a non-boolean quantum system, a method, an oracle, and/or a system. Those skilled in the art will appreciate that this terminology is only illustrative and does not affect the scope of the invention. For instance, the present invention may just as easily relate to an instantiation of an object from a library of non-boolean quantum oracles.

[0042] Generally speaking, the present invention is a generalization of amplitude amplification and estimation algorithms to work with quantum oracles for non-boolean functions. Hereinafter, the qualifiers “boolean” and “non-boolean” will be used to distinguish embodiments of the present invention from known boolean versions of the amplitude amplification algorithm and their related applications.

[0043] Oracle for a Non-Boolean Function:

[0044] The behavior of the boolean quantum oracle .Math..sub.ƒ.sub.bool of Equation (2) may be generalized to non-boolean functions by allowing the oracle to perform arbitrary phase-shifts on the different basis states. More concretely, let φ: {0, 1, . . . , N−1} .fwdarw. be a real-valued function, and let U.sub.φ be a quantum oracle given by Equation (5), as follows:

[00003]$\begin{array}{cc}{U}_{\phi }\equiv \underset{x=0}{\overset{N-1}{.Math.}}{e}^{i\phi \left(x\right)}.Math.x.Math..Math.x.Math..& \left(5\right)\end{array}$

[0045] The actions of the oracle U.sub.φ and its inverse U.sub.φ.sup.† on the basis states |0, . . . , |N−1 may be given by Equations (6) and (7), as follows:

U.sub.φ|x)=e.sup.+iφ(x)|x=[cos(φ(x))+i sin(φ(x))]|x,  (6)

U.sub.φ.sup.†|x)=e.sup.−iφ(x)|x=[cos(φ(x))−i sin(φ(x))]|x.  (7)

[0046] Goal of the Non-Boolean Amplitude Amplification Algorithm:

[0047] Given an oracle U.sub.φ and an initial state |ψ.sub.0, a goal of the non-boolean amplitude amplification algorithm of the present invention may be to preferentially amplify the amplitudes of the basis states |x with lower values of cos(φ(x)), at the expense of the amplitude of states with higher values of cos(φ(x)). Depending on the context in which the algorithm is to be used, a different function of interest ƒ (which is intended to guide the amplification) may be appropriately mapped onto the function cp. For example, and without limitation, if the range of ƒ is [0,1] and one intends to amplify the states with higher values of ƒ, then options for formulating the problem in terms of co include the following:

φ(x)=πƒ(x) or φ(x)=arccos(1−2ƒ(x)).  (8)

In both cases of Equations (8), cos(φ) is monotonically decreasing in ƒ.

[0048] The connection between the boolean and non-boolean amplitude amplification algorithms may be seen as follows: If either of the two options in Equations (8) is used to map a boolean function ƒ.sub.bool onto φ.sub.bool, then

[00004]$\begin{array}{cc}{\phi }_{\mathrm{bool}}\left(x\right)=\{\begin{array}{cc}\pi ,& \mathrm{if}{f}_{\mathrm{bool}}\left(x\right)=1,\\ 0,& \mathrm{if}{f}_{\mathrm{bool}}\left(x\right)=0.\end{array}& \left(9\right)\end{array}$

[0049] In the case of Equation (9), the oracle U.sub.φ and its inverse U.sub.φ.sup.† both reduce to a boolean oracle as follows (Equation 10):

U.sub.φ.sub.bool=U.sub.φ.sub.bool.sup.†=.Math..sub.ƒ.sub.bool.  (10)

[0050] Congruently, the task of amplifying (the amplitude of) the states with lower values of cos(φ) may align with the task of amplifying the winning states |x with ƒ.sub.bool(x)=1.

[0051] Goal of the Quantum Mean Estimation Algorithm:

[0052] Given a generic unitary operator U and a state |ψ.sub.0, a goal of the quantum mean estimation algorithm may be to estimate the quantity of Equation (11):

ψ.sub.0|U|ψ.sub.0.  (11)

[0053] The task of estimating the quantity of Equation (11) may be phrased in terms of the oracle U.sub.φ, as estimating the expectation of the eigenvalue e.sup.iφ(x) for a state |x chosen randomly by making a measurement on the superposition state |ψ.sub.0. The connection between the two tasks may be seen in Equation (12), as follows:

[00005]$\begin{array}{cc}.Math.{\psi }_0.Math.U_{\phi }.Math.{\psi }_0.Math.=\underset{x=0}{\overset{N-1}{.Math.}}.Math.{\psi }_0.Math.e^{i\phi \left(x\right)}.Math.x.Math..Math.x.Math.{\psi }_0.Math.=\underset{x=0}{\overset{N-1}{.Math.}}.Math..Math.x.Math.{\psi }_0.Math.{.Math.}^2{e}^{i\phi \left(x\right)},& \left(12\right)\end{array}$

wherein |x|ψ.sub.0|.sup.2 is the probability for a measurement on |ψ.sub.0 to yield x.

[0054] The only difference between (a) estimating ψ.sub.0|U.sub.φ|ψ.sub.0 for an oracle U.sub.φ, and (b) estimating ψ.sub.0|U|ψ.sub.0 for a generic unitary operator U is that {|ψ.sub.0|U.sub.φ|ψ.sub.0, . . . , |N−1)} is known beforehand to be an eigenbasis of U.sub.φ. On the other hand, the eigenstates of a generic unitary operator U may be a priori unknown. However, as described in detail hereinbelow, the mean estimation algorithm does not use the knowledge of the eigenstates and, therefore, may be applicable for generic unitary operators U as well.

[0055] As described hereinabove, the mean estimation algorithm of the present invention is a generalization of known boolean amplitude estimation algorithm(s). Regarding the connection between the respective tasks of these algorithms, note that the eigenvalues of a boolean oracle may be either +1 or −1, and the expectation of the eigenvalue under |ψ.sub.0 is directly related to the probability of a measurement yielding a winning state with eigenvalue −1. This probability is precisely the quantity estimated by the non-boolean amplitude estimation algorithm of the present invention.

[0056] Non-Boolean Amplitude Amplification Algorithm:

[0057] Setup and Notation: Various embodiments of a non-boolean amplitude amplification algorithm as described herein may include not only a quantum system, or qubit(s), as input to a quantum oracle, but also may employ one extra ancilla qubit. For example, and without limitation, let a quantum system used in certain embodiments of the present algorithm comprise two quantum registers. The first register may contain the lone ancilla qubit, and the second register (input qubit) may be acted upon by the quantum oracle.

[0058] The notations |a.Math.|b and |a,b may both refer to a state where the two registers are unentangled, with the first register in state |a and the second register in state |b. The tensor product notation .Math. may also be used to combine operators that act on the individual registers into operators that simultaneously act on both registers. Such two-register operators may be represented by boldface symbols (e.g., S.sub.Ψ.sub.0, U.sub.φ, I). Likewise, boldface symbols may be used to represent the states of the two-register system in the bra-ket notation (e.g., |Ψ.sub.0). As used herein, any state written in the bra-ket notation (e.g., |ψ) will be unit normalized (i.e., normalized to 1). The dagger notation (†) may be used to denote the Hermitian conjugate of an operator, which is also the inverse for a unitary operator.

[0059] Unless otherwise specified herein, {|0, |1, . . . , |N−1} may be used as the basis for (that is, as the state space of) the second register. Any measurement of the second register may refer to measurement in this basis. Likewise, unless otherwise specified,

{|0,0,|0,1, . . . ,|0,N−1}∪{|1,0,|1,1, . . . ,|1,N−1}  (13)

may be used as the basis for the two-register system.

[0060] In Equation (14) below, let |ψ.sub.0 be the initial state of the second register from which the amplification process is to begin, and let A.sub.0 be the unitary operator that changes the state of the second register from |0 to |ψ.sub.0 (Note: Assumed here, only for notational convenience, is that there exists a state |0| which is simultaneously an eigenstate of U.sub.φ, as well as a special, easy-to-prepare state of the second register; a person of skill in the art will immediately recognize the algorithms described herein may be modified to work even without this assumption):

[00006]$\begin{array}{cc}|{\psi }_0.Math.\equiv A_0.Math.0.Math.\equiv \underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right).Math.x.Math.,& \left(14\right)\end{array}$$\mathrm{such}\mathrm{that}$$\underset{x=0}{\overset{N-1}{.Math.}}|a_0\left(x\right){|}^2=1,$

where a.sub.0(x) is the initial amplitude of the basis state |x.

[0061] The algorithm introduced hereinbelow may initialize the ancilla (i.e., first register) in the |+ state given by Equation (15), as follows:

[00007]$\begin{array}{cc}.Math.+.Math.=\frac{.Math.0.Math.+.Math.1.Math.}{\sqrt{2}}.& \left(15\right)\end{array}$

[0062] Anticipating this initialization, let the two-register state |Ψ.sub.0 be defined as in Equation (16), as follows:

[00008]$\begin{array}{cc}\begin{array}{c}.Math.{\Psi }_0.Math.\equiv .Math.+,{\psi }_0.Math.=\frac{.Math.0,{\psi }_0.Math.+.Math.1,{\psi }_0.Math.}{\sqrt{2}}\\ =\frac{1}{\sqrt{2}}\underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right)[.Math.0,x.Math.+.Math.1,x.Math.]\end{array}.& \left(16\right)\end{array}$

[0063] Required Unitary Operations: The following unitary operations may be used in certain embodiments of a generalized amplitude amplification algorithm of the present invention:

[0064] Selective Phase-Flip Operator. Let the two-register unitary operator S.sub.Ψ.sub.0 be defined as in Equation (17):

[00009]$\begin{array}{cc}\begin{array}{c}{S}_{{\Psi }_0}\equiv 2.Math.{\Psi }_0.Math..Math.{\Psi }_0.Math.-I\\ =2.Math.+,{\psi }_0.Math..Math.+,{\psi }_0.Math.-I\end{array},& \left(17\right)\end{array}$

where I is the two-register identity operator. S.sub.Ψ.sub.0 may leave the state |Ψ.sub.0 unchanged and may flip the phase of any state orthogonal to |Ψ.sub.0. S.sub.Ψ.sub.0 may be the two-register generalization of S.sub.ψ.sub.0 used in counterpart boolean amplitude amplification algorithm(s). From Equations (14) and (16), it follows (in Equation (18)) that

|Ψ.sub.0=[H.Math.A.sub.0]|0,0,  (18)

where H is the Hadamard transform. Thus, S.sub.Ψ.sub.0 may be expressed as in Equation (19):

S.sub.Ψ.sub.0=[H.Math.A.sub.0][2|0,00,0|−I][H.Math.A.sub.0.sup.†].  (19)

[0065] Referring initially to FIG. 1, an exemplary quantum circuit 100 implementing non-boolean amplitude amplification according to an embodiment of the present invention will now be described in detail. A quantum system of circuit 100 may comprise a first register (ancilla qubit) 110 and a second register (input qubit) 120. The second register 120 may be configured to be acted upon by a quantum oracle 130. As illustrated, Equation (19) is used to drive an implementation of circuit 130 for S.sub.Ψ.sub.0, provided one has access to the quantum circuits that implement A.sub.0 (unitary operator 142) and A.sub.0.sup.† (inverse unitary operator 144). Hadamard transforms 150 are denoted as H.

[0066] Conditional Oracle Calls: Let the two-register unitary operator U be defined as in Equation (20):

U.sub.φ≡|0|.Math.U.sub.φ+|11|.Math.U.sub.φ.sup.†.  (20)

[0067] This operator's action on the basis states of the two-register system is given by Equations (21) and (22):

U.sub.φ|0,x)=e.sup.+iφ(x)|0,x,  (21)

U.sub.φ|1,x)=e.sup.−iφ(x)|1,x.  (22)

[0068] If the ancilla is in state |0, U.sub.φ acts U.sub.φ on the second register. On the other hand, if the ancilla is in state |1, U.sub.φ acts U.sub.φ.sup.† on the second register. The inverse of U.sub.φ is given by Equation (23):

U.sub.φ.sup.†=|00|.Math.U.sub.φ.sup.†+|11|.Math.U.sub.φ,  (23)

and the action of U.sub.φ.sup.† on the basis states is given by Equations (24) and (25):

U.sub.φ.sup.†|0,x=e.sup.−iφ(x)|0,x,  (24)

U.sub.φ.sup.†|1,x=e.sup.+iφ(x)|1,x.  (25)

[0069] The amplitude amplification algorithm for non-boolean functions may involve calls to both U.sub.φ and U.sub.φ.sup.†.

[0070] Referring now to FIGS. 2 and 3, exemplary quantum circuits 200 and 300 each implementing non-boolean amplitude amplification according to an embodiment of the present invention will now be described in detail. FIG. 2 depicts a circuit implementation 200 of U.sub.φ using a) ancilla 210 serving as a control qubit, b) bit-flip (or Pauli-X) gates 240 denoted as X, and c) second register 220 acted upon by controlled U.sub.φ and U.sub.φ.sup.† operations (i.e., oracles) 232, 234, respectively. FIG. 3 depicts a circuit implementation 330 of U.sub.φ.sup.† using a) ancilla 310 serving as a control qubit, b) bit-flip (or Pauli-X) gates 340 denoted as X, and c) second register 320 acted upon by controlled U.sub.φ and U.sub.φ.sup.† operations 332, 334, respectively.

[0071] Algorithm Description:

[0072] Referring now to FIGS. 4 and 5, an exemplary quantum circuit 400 and pseudocode 500 implementing a non-boolean amplitude amplification quantum algorithm according to an embodiment of the present invention will now be described in detail. For example, and without limitation, the amplitude amplification algorithm for non-boolean functions is iterative and may comprise the following steps:

[0073] (1) Initialize a two-register system in the |Ψ.sub.0 state;

[0074] (2) Perform K iterations: During odd iterations 402, apply operations 430, 432 denoted S.sub.Ψ.sub.0 U.sub.φ on the system. During even iterations 404, apply operations 430, 434 denoted S.sub.Ψ.sub.0 U.sub.φ.sup.† on the system; and

[0075] (3) After the K iterations, measure 440 the ancilla (first register 410) in the 0/1 basis.

[0076] Up to a certain number of iterations, the iterative steps 402, 404 may be designed to amplify the amplitude of the basis states |0,x and |1,x with lower values of cos(φ(x)). The measurement 440 of the ancilla 410 at the end of the algorithm may be performed simply to ensure that the two registers 410, 420 are not entangled in the final state 450 of the system. The specification of K (i.e., the number of iterations to perform) is included in an analysis of the present algorithm described hereinbelow.

[0077] Connection to Known Boolean Amplitude Amplification Algorithm:

[0078] From Equations (20) and (23), a person of skill in the art will immediately recognize that for the boolean oracle case given by φ(x)=πƒ.sub.bool(x), U.sub.φ and U.sub.φ.sup.† both reduce to I.Math..Math..sub.ƒ.sub.bool, where .Math..sub.ƒ.sub.bool is the oracle used in known boolean amplitude amplification algorithm(s). Furthermore, if a first register is in the |+ state, from Equations (3) and (17), the action of S.sub.Ψ.sub.0 is given by Equation (26):

S.sub.Ψ.sub.0[|+.Math.|ψ]=|+.Math.[S.sub.ψ.sub.0|ψ].  (26)

[0079] Note that the first register is unaffected here. Thus, for the boolean oracle case, the algorithm 400, 500 of FIGS. 4 and 5 may reduce to simply acting S.sub.ψ.sub.0 .Math..sub.ƒ.sub.bool on the second register 420 during each iteration 402, 404; the ancilla qubit 410 remains untouched and unentangled from the second register 420. In this way, algorithm 400, 500 is a generalization of known boolean amplitude amplification algorithm(s) described hereinabove.

[0080] The two key differences of the generalized algorithm from the boolean algorithm, apart from the usage of a non-boolean oracle, may be as follows:

[0081] (1) The addition of the ancilla 410, which doubles the dimension of the state space of the system, and

[0082] (2) Alternating between using U.sub.φ and U.sub.φ.sup.† (operations 432 and 434, respectively) during the odd iterations 402 and even iterations 404.

[0083] Analysis of the Non-Boolean Amplitude Amplification Algorithm:

[0084] Still referring to FIGS. 4 and 5, let |Ψ.sub.k be the state of the two-register system after k=0, 1, . . . , K iterations of the amplitude amplification algorithm 400 (but before the measurement 440 of the ancilla 410). For k>0, |Ψ.sub.k may be recursively written as in Equation (27):

[00010]$\begin{array}{cc}.Math.{\Psi }_k.Math.\equiv \{\begin{array}{cc}{S}_{{\Psi }_0}{U}_{\phi }.Math.{\Psi }_{k-1}.Math.,& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ S_{{\Psi }_0}{U}_{\phi }^{†}.Math.{\Psi }_{k-1}.Math.,& \mathrm{if}k\mathrm{is}\mathrm{even}\end{array}.& \left(27\right)\end{array}$

[0085] Let ã.sub.k (0,x) and ã.sub.k(1,x) be the normalized amplitudes of the basis states |0,x and |1,x, respectively, in the superposition |Ψ.sub.k.

[00011]$\begin{array}{cc}.Math.{\Psi }_k.Math.\equiv \underset{x=0}{\overset{N}{.Math.}}[{\tilde{a}}_k\left(0,x\right).Math.0,x.Math.+{\tilde{a}}_k\left(1,x\right).Math.1,x.Math.].& \left(28\right)\end{array}$

[0086] In the initial state |Ψ.sub.0, the amplitudes ã.sub.0(0,x) and ã.sub.0(1,x) are both given, from Equation (16), by the following (Equation (29)):

[00012]$\begin{array}{cc}{\tilde{a}}_0\left(0,x\right)={\tilde{a}}_0\left(1,x\right)=\frac{a_0\left(x\right)}{\sqrt{2}}.& \left(29\right)\end{array}$

[0087] Let the parameter θ∈[0,π] be implicitly defined by Equation (30):

[00013]$\begin{array}{cc}\cos \left(\theta \right)\equiv \underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2\cos \left(\phi \left(x\right)\right).& \left(30\right)\end{array}$

[0088] cos(θ) is the expected value of cos(φ(x)) over bitstrings x sampled by measuring the state |ψ.sub.0.

[0089] Let the two-register states |αand |β be defined as follows (Equations (31) and (32)):

|α≡U.sub.φ|Ψ.sub.0,  (31)

|β≡U.sub.φ.sup.†|Ψ.sub.0.  (32)

[0090] These register states may be used to track the evolution of the system through the iterative steps 402, 404 of algorithm 400, 500. Using Equations (16), (20), and (23), |α and |0 may be written as follows (Equations (33) and (34)):

[00014]$\begin{array}{cc}.Math.\alpha .Math.=\frac{1}{\sqrt{2}}\underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right)[e^{i\phi \left(x\right)}.Math.0,x.Math.+e^{-i\phi \left(x\right)}.Math.1,x.Math.],& \left(33\right)\end{array}$$\begin{array}{cc}.Math.\beta .Math.=\frac{1}{\sqrt{2}}\underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right)[e^{-i\phi \left(x\right)}.Math.0,x.Math.+e^{i\phi \left(x\right)}.Math.1,x.Math.].& \left(34\right)\end{array}$

[0091] Note that θ, |α, and |β are all implicitly dependent on the function φ and the initial state |ψ.sub.0. For notational convenience, these dependencies are not explicitly indicated.

[0092] The First Iteration:

[0093] After one iterative step, the system may be in state |Ψ.sub.1 given by Equation (35):

|Ψ.sub.1=S.sub.Ψ.sub.0U.sub.φ|Ψ.sub.0.  (35)

[0094] Using Equations (17) and (31), this state may be written as follows (Equation (36)):

|Ψ.sub.1=S.sub.Ψ.sub.0|α=2Ψ.sub.0|αΨ.sub.0−|α.  (36)

[0095] From Equations (16), (30), and (33), it follows that

[00015]$\begin{array}{cc}\begin{array}{c}.Math.{\Psi }_0.Math.\alpha .Math.=\frac{1}{2}\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2\left[e^{i\phi \left(x\right)}.Math.0,x.Math.0,x.Math.+e^{-i\phi \left(x\right)}.Math.1,x.Math.1,x.Math.\right]\\ =\frac{1}{2}\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2\left[e^{i\phi \left(x\right)}+e^{-i\phi \left(x\right)}\right]\\ =\frac{1}{2}\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^{2}2\cos \left(\phi \left(x\right)\right)=\cos \left(\theta \right)\end{array}.& \left(37\right)\end{array}$

[0096] Note from Equation (37) that Ψ.sub.0|α is real-valued. Key to the functioning of the algorithm 400, 500, the motivation behind adding an ancilla qubit 410 (effectively doubling the number of basis states) is precisely to make Ψ.sub.0|α real-valued.

[0097] From Equations (36) and (37), |Ψ.sub.1 may be written as follows (Equation (38)):

|Ψ.sub.1=2 cos(θ)|Ψ.sub.0−|α.  (38)

[0098] From Equations (16) and (33), the amplitude ã.sub.1(0,x) of the basis state |0,x in the superposition |Ψ.sub.1 may be written as follows (Equation (39)):

[00016]$\begin{array}{cc}{\tilde{a}}_1\left(0,x\right)=.Math.0,x.Math.{\Psi }_1.Math.=\frac{a_0\left(x\right)}{\sqrt{2}}\left[2\cos \left(\theta \right)-e^{i\phi \left(x\right)}\right].& \left(39\right)\end{array}$

[0099] Likewise, the amplitude ã.sub.1(1,x) of the basis state |1,x may be written as follows (Equation (40)):

[00017]$\begin{array}{cc}{\tilde{a}}_1\left(1,x\right)=.Math.1,x.Math.{\Psi }_1.Math.=\frac{a_0\left(x\right)}{\sqrt{2}}\left[2\cos \left(\theta \right)-e^{-i\phi \left(x\right)}\right].& \left(40\right)\end{array}$

[0100] Equations (39) and (40) show that, after one iterative step, the amplitudes of |0,x and |1,x have acquired factors of [2 cos(θ)−e.sup.iφ(x)] and [2 cos(θ)−e.sup.−iφ(x)], respectively. Now, Equation (41) shows that, if cos(θ) is positive, the magnitude of the “amplitude amplification factor” after one iteration is monotonically decreasing in cos(φ):

[00018]$\begin{array}{cc}\frac{{.Math.{\tilde{a}}_1\left(0,x\right).Math.}^2}{{.Math.{\tilde{a}}_0\left(0,x\right).Math.}^2}=\frac{{.Math.{\tilde{a}}_1\left(1,x\right).Math.}^2}{{.Math.{\tilde{a}}_0\left(1,x\right).Math.}^2}=4{\cos }^2\left(\theta \right)+1-4\cos \left(\theta \right)\cos \left(\phi \left(x\right)\right).& \left(41\right)\end{array}$

[0101] Such preferential amplification of states with lower values of cos(φ) is precisely what the algorithm 400, 500 set out to do.

[0102] Note that this monotonicity property relies on Ψ.sub.0|α being real valued in Equation (36). If Ψ.sub.0|α is complex, with a phase δ.Math.{0,π}, then the amplification will be monotonic in cos(φ−δ), which does not meet the present goal of the algorithm 400, 500. The case where Ψ.sub.0|α is not real-valued is explored further hereinbelow.

[0103] Identities to Track the Subsequent Iterations:

[0104] Equations (16), (17), (20), (23), (31), and (32) may be used to derive the identities of Equations (42), which capture the actions of the operators S.sub.Ψ.sub.0, U.sub.φ, and U.sub.φ.sup.† on the states IWO), |α, and |β:

[00019]$\begin{array}{cc}{S}_{{\Psi }_0}.Math.{\Psi }_0.Math.=.Math.{\Psi }_0.Math.,& \left(42\right)\end{array}$$S_{{\Psi }_0}.Math.\alpha .Math.=2\cos \left(\theta \right).Math.{\Psi }_0.Math.-.Math.\alpha .Math.,$$S_{{\Psi }_0}.Math.\beta .Math.=2\cos \left(\theta \right).Math.{\Psi }_0.Math.-.Math.\beta .Math.,$$U_{\phi }.Math.{\Psi }_0.Math.=.Math.\alpha .Math.,$$U_{\phi }.Math.\alpha .Math.=\frac{1}{\sqrt{2}}\underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right)[e^{2i\phi \left(x\right)}.Math.0,x.Math.+e^{-2i\phi \left(x\right)}.Math.1,x.Math.],$$U_{\phi }.Math.\beta .Math.=.Math.{\Psi }_0.Math.,$$U_{\phi }^{†}.Math.{\Psi }_0.Math.=.Math.\beta .Math.,$$U_{\phi }^{†}.Math.\alpha .Math.=.Math.{\Psi }_0.Math.,$$U_{\phi }^{†}.Math.\beta .Math.=\frac{1}{\sqrt{2}}\underset{x=0}{\overset{N-1}{.Math.}}{a}_0\left(x\right)[e^{-2i\phi \left(x\right)}.Math.0,x.Math.+e^{2i\phi \left(x\right)}.Math.1,x.Math.].$

[0105] A person of skill in the art will immediately recognize that the subspace spanned by the states |Ψ.sub.0, |α, and |β is almost stable under the action of S.sub.Ψ.sub.0, U.sub.φ, and U.sub.φ.sup.†. Only the actions of U.sub.φ on |α and |β may take the state of the system out of this subspace. Continuing to refer to FIGS. 4 and 5, the motivation behind alternating between using U.sub.φ, and U.sub.φ.sup.† during the odd iterations 402 and the even iterations 404 is to keep the state of the system within the subspace spanned by |Ψ.sub.0, |α, and |β.

[0106] From the identities above, the expressions of Equations (43) may be written capturing the relevant actions of the odd iteration operator 430, 432 denoted S.sub.Ψ.sub.0 U.sub.φ and the even iteration operator 430, 434 denoted S.sub.Ψ.sub.0 U.sub.φ.sup.†:

S.sub.Ψ.sub.0U.sub.φ|Ψ.sub.0)=2 cos(θ)|Ψ.sub.0−|α,

S.sub.Ψ.sub.0U.sub.φ|β)=|Ψ.sub.0,

S.sub.Ψ.sub.0U.sub.φ.sup.†|Ψ.sub.0)=2 cos(θ)|Ψ.sub.0−|β,

S.sub.Ψ.sub.0U.sub.φ.sup.†|α)=|Ψ.sub.0.  (43)

[0107] Referring now to FIG. 6, and continuing to refer to FIGS. 4 and 5, state diagram 600 illustrates how, from the expressions of Equation (43), the odd iteration operator 430, 432 denoted S.sub.Ψ.sub.0 U.sub.φ may map any (first) state 610 in the space spanned by |Ψ.sub.0 and |β to a (second) state 620 in the space spanned by |Ψ.sub.0 and |α. Conversely, the even iteration operator 430, 434 denoted S.sub.Ψ.sub.0 U.sub.φ.sup.† may map any state 620 in the space spanned by |Ψ.sub.0 and |α to a state 610 in the space spanned by |Ψ.sub.0 and |β. Because the algorithm 400, 500 begins with the system initialized in the state |Ψ.sub.0, the state of the system may oscillate between the two subspaces 610, 620 during the odd and even iterations 402, 404.

[0108] State After k Iterations:

[0109] Using Equations (27) and (43), the state |Ψ.sub.k of the two-register system after k≥0 iterations may be written, in matrix multiplication notation, as shown in Equation (44):

[00020]$\begin{array}{cc}.Math.{\Psi }_k.Math.=\{\begin{array}{cc}{[.Math.{\Psi }_0.Math..Math.\alpha .Math.]\left[\begin{array}{cc}2\cos \left(\theta \right)& 1\\ -1& 0\end{array}\right]}^k\left[\begin{array}{c}1\\ 0\end{array}\right],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ {[.Math.{\Psi }_0.Math..Math.\beta .Math.]\left[\begin{array}{cc}2\cos \left(\theta \right)& 1\\ -1& 0\end{array}\right]}^k\left[\begin{array}{c}1\\ 0\end{array}\right],& \mathrm{if}k\mathrm{is}\mathrm{even}\end{array}.& \left(44\right)\end{array}$

[0110] To simplify Equation (44), let the matrix M.sub.θ be defined as follows (Equation (45)):

[00021]$\begin{array}{cc}{M}_{\theta }\equiv \left[\begin{array}{cc}2\cos \left(\theta \right)& 1\\ -1& 0\end{array}\right].& \left(45\right)\end{array}$

[0111] Substituting Equation (45) into Equation (44) yields Equation (46), as follows:

[00022]$\begin{array}{cc}.Math.{\Psi }_k.Math.=\{\begin{array}{cc}{\left[\begin{array}{c}.Math.{\Psi }_0.Math.\\ .Math.\alpha .Math.\end{array}\right]}^T{M}_{\theta }^k\left[\begin{array}{c}1\\ 0\end{array}\right],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ {\left[\begin{array}{c}.Math.{\Psi }_0.Math.\\ .Math.\beta .Math.\end{array}\right]}^T{M}_{\theta }^k\left[\begin{array}{c}1\\ 0\end{array}\right],& \mathrm{if}k\mathrm{is}\mathrm{even}\end{array}.& \left(46\right)\end{array}$

where the superscript T denotes transposition. M.sub.θ may be diagonalized as

[00023]$\begin{array}{cc}{M}_{\theta }=S_{\theta }\left[\begin{array}{cc}{e}^{-i\theta }& 0\\ 0& e^{i\theta }\end{array}\right]S_{\theta }^{-1},& \left(47\right)\end{array}$

and where the matrix S.sub.θ and its inverse S.sub.θ.sup.1 may be given by

[00024]$\begin{array}{cc}\begin{array}{cc}{S}_{\theta }=\frac{-i}{2\sin \left(\theta \right)}\left[\begin{array}{cc}{e}^{‐i\theta }& e^{i\theta }\\ -1& -1\end{array}\right],& S_{\theta }^{-1}=\left[\begin{array}{cc}-1& -e^{i\theta }\\ 1& e^{-i\theta }\end{array}\right].\end{array}& \left(48\right)\end{array}$

[0112] Now, M.sub.θ.sup.k may be written as follows (Equation (49)):

[00025]$\begin{array}{cc}{M}_{\theta }^k=S_{\theta }\left[\begin{array}{cc}{e}^{-i\theta }& 0\\ 0& e^{i\theta }\end{array}\right]S_{\theta }^{-1}=S_{\theta }\left[\begin{array}{cc}{e}^{-ik\theta }& 0\\ 0& e^{ik\theta }\end{array}\right]S_{\theta }^{-1}.& \left(49\right)\end{array}$

[0113] From Equation (48) and Equation (49), it follows that

[00026]$\begin{array}{cc}\begin{array}{c}{M}_{\theta }^k\left[\begin{array}{c}1\\ 0\end{array}\right]=S_{\theta }\left[\begin{array}{cc}{e}^{-ik\theta }& 0\\ 0& e^{ik\theta }\end{array}\right]\left[\begin{array}{c}-1\\ 1\end{array}\right]\\ =S_{\theta }\left[\begin{array}{c}-e^{-\mathrm{ik}\theta }\\ e^{ik\theta }\end{array}\right]=\frac{1}{\sin \left(\theta \right)}\left[\begin{array}{c}\sin (\left(k+1\right)\theta \\ -s\mathrm{in}\left(k\theta \right)\end{array}\right]\end{array}.& \left(50\right)\end{array}$

[0114] Plugging (50) back into (46) leads to the following (Equation (51)):

[00027]$\begin{array}{cc}.Math.{\Psi }_k.Math.=\{\begin{array}{cc}\frac{1}{\sin \left(\theta \right)}[\sin \left(\left(k+1\right)\theta \right).Math.{\Psi }_0.Math.-\sin \left(k\theta \right).Math.\alpha .Math.],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ \frac{1}{\sin \left(\theta \right)}[\sin \left(\left(k+1\right)\theta \right).Math.{\Psi }_0.Math.-\sin \left(k\theta \right).Math.\beta .Math.],& \mathrm{if}k\mathrm{is}\mathrm{even}.\end{array}& \left(51\right)\end{array}$

[0115] Basis State Amplitudes after k Iterations:

[0116] From Equations (16), (33), (34), and (51), the amplitudes ã.sub.k(0,x) of the basis states |0,x after k≥0 iterations may be written as follows (Equation (52)):

[00028]$\begin{array}{cc}{\tilde{a}}_k\left(0,x\right)=.Math.0,x.Math.{\Psi }_k.Math.=\{\begin{array}{cc}\frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{i\phi \left(x\right)}\right],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ \frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{-i\phi \left(x\right)}\right],& \mathrm{if}k\mathrm{is}\mathrm{even}.\end{array}& \left(52\right)\end{array}$

[0117] Similarly, the amplitudes ã.sub.k(1,x) of the basis states |1,x may be written as follows (Equation (53)):

[00029]$\begin{array}{cc}{\tilde{a}}_k\left(1,x\right)=.Math.1,x.Math.{\Psi }_k.Math.=\{\begin{array}{cc}\frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{i\phi \left(x\right)}\right],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ \frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{-i\phi \left(x\right)}\right],& \mathrm{if}k\mathrm{is}\mathrm{even}.\end{array}& \left(53\right)\end{array}$

[0118] These expressions may be summarized, for b∈{0,1}, as follows (Equation (54)):

[00030]$\begin{array}{cc}{\tilde{a}}_k\left(b,x\right)=\{\begin{array}{cc}\frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{i\phi \left(x\right)}\right],& \mathrm{if}k+b\mathrm{is}\mathrm{odd},\\ \frac{a_0\left(x\right)}{\sqrt{2}\sin \left(\theta \right)}\left[\sin \left(\left(k+1\right)\theta \right)-\sin \left(k\theta \right)e^{-i\phi \left(x\right)}\right],& \mathrm{if}k+b\mathrm{is}\mathrm{even}.\end{array}& \left(54\right)\end{array}$

[0119] Amplitudes After Ancilla Measurement. Note that the magnitudes of the amplitudes of the states |0,x and |1,x are equal; that is,

|ã.sub.1(0,x)|=|ã.sub.k(1,x)|,  (55)

for all k≥0 and x∈{0, 1, . . . , N−1}. Therefore, a measurement 440 of the ancilla qubit in the first register 410 after K iterations may yield a value of either 0 or 1 with equal probability. Let |ψ.sub.K,b be the normalized state of the second register 420 after performing K iterations, followed by a measurement 440 of the ancilla qubit 410, which may yield a value b∈{0,1}. |ψ.sub.K,b may be written as follows (Equation (56)):

[00031]$\begin{array}{cc}.Math.{\psi }_{K,b}.Math.=\underset{x=0}{\overset{N-1}{.Math.}}{a}_{K,b}\left(x\right).Math.x.Math.,& \left(56\right)\end{array}$

where a.sub.K,b(x) are the normalized amplitudes of the basis states of the second register 420 (after performing K iterations and the measurement 440 of the ancilla 410). a.sub.K,b(x) may simply be given by Equation (57):

a.sub.K,b(x)=√{square root over (2)}/ã.sub.K(b,x).  (57)

[0120] Much of the definition hereinbelow holds a) regardless of whether a measurement 440 is performed on the ancilla qubit 410 after the K iterations, and b) regardless of the value yielded by the ancilla measurement 440 (if performed). The primary goal of measuring 440 the ancilla 410 is to make the two registers 410, 420 unentangled from each other.

[0121] Basis State Probabilities After K Iterations:

[0122] Continuing to refer to FIGS. 4 and 5, let p.sub.K(x) be the probability for a measurement of the second register after K≥0 iterations to yield x. This probability may be written, in terms of the amplitudes in the “Basis State Amplitudes After K Iterations” section hereinabove, as follows (Equation (58)):

p.sub.K(x)=[|ã.sub.K(0,x)|.sup.2+|ã.sub.K(1,x)|.sup.2]=|a.sub.K,0(x)|.sup.2=|a.sub.K,1(x)|.sup.2.   (58)

[0123] This expression shows that the probability p.sub.K(x) depends neither on whether the ancilla was measured, nor on the result of the ancilla measurement (if performed). From Equation (54), p.sub.K(x) may be written as follows (Equation (59)):

[00032]$\begin{array}{cc}\begin{array}{c}{p}_K\left(x\right)=\frac{p_0\left(x\right)}{{\sin }^2\left(\theta \right)}{.Math.\sin \left(\left(K+1\right)\theta \right)-\sin \left(K\theta \right)e^{i\phi \left(x\right)}.Math.}^2\\ =\frac{p_0\left(x\right)}{{\sin }^2\left(\theta \right)}\left[{\sin }^2\left(K\theta \right)+{\sin }^2\left(\left(K+1\right)\theta \right)-2\sin \left(K\theta \right)\sin \left(\left(K+1\right)\theta \right)\cos \left(\phi \left(x\right)\right)\right].\end{array}& \left(59\right)\end{array}$

[0124] A person of skill in the art will immediately recognize that the probability amplification factor p.sub.K(x)/p.sub.0(x) is monotonic in cos(φ(x)) for all K≥0. The following trigonometric identities (Equation (60)) help elucidate the K dependence of this amplification factor:

sin.sup.2(C)+sin.sup.2(C+D)=sin.sup.2(D)+2 sin(C)sin(C+D)cos(D),

2 sin(C)sin(C+D)=cos(D)−cos(2C+D).  (60)

[0125] Setting C=Kθ and D=θ, these identities may be used to rewrite Equation (59) as follows (Equation (61)):

p.sub.K(x)=p.sub.0(x){1−λ.sub.K[cos(φ(x))−cos(θ)]},  (61)

where the K-dependent factor λ.sub.K is given by Equation (62):

[00033]$\begin{array}{cc}{\lambda }_K\equiv \frac{2\sin \left(K\theta \right)\sin \left(\left(K+1\right)\theta \right)}{{\sin }^2\left(\theta \right)}=\frac{\cos \left(\theta \right)-\cos \left(\left(2K+1\right)\theta \right)}{{\sin }^2\left(\theta \right)}.& \left(62\right)\end{array}$

[0126] For notational convenience, the fact that λ.sub.K depends on θ is not explicitly indicated. The result in Equation (61) may be summarized as follows:

[0127] (1) Applying K iterations of the non-boolean amplitude amplification algorithm changes the probability of measuring x by a factor that is a linear function of cos(φ(x)). If the second register is initially in an equiprobable state (i.e., if p.sub.0(x)=constant), then the probability p.sub.K(x) after K iterations is itself a linear function of cos(φ(x)).

[0128] (2) If cos(φ(x))=cos(θ) for some x, the probability of a measurement of the second register yielding that x is unaffected by the algorithm.

[0129] (3) The slope of the linear dependence is −λ.sub.K. If λ.sub.K is positive, the states with cos(φ)<cos(θ) are amplified. Conversely, if λ.sub.K is negative, states with cos(φ)>cos(θ) are amplified. The magnitude of λ.sub.K controls the degree to which the preferential amplification has been performed.

[0130] From Equation (62), λ.sub.K is an oscillatory function of K, centered around cos(θ)/sin.sup.2(θ) with an amplitude of 1/sin.sup.2(θ) and a period of π/θ. Recalling from Equation (30) that

[00034]$\begin{array}{cc}\underset{x=0}{\overset{N-1}{.Math.}}{p}_0\left(x\right)\cos \left(\phi \left(x\right)\right)=\cos \left(\theta \right)=\underset{x=0}{\overset{N-1}{.Math.}}{p}_0\left(x\right)\cos \left(\theta \right),& \left(63\right)\end{array}$

one can verify that for any K≥0, the probabilities p.sub.K(x) from Equation (61) add up to 1.

[0131] From the definition of λ.sub.K in Equation (62), for all K, λ.sub.K is bounded from above by λ.sub.optimal defined as follows (Equation (64)):

[00035]$\begin{array}{cc}{\lambda }_K\le {\lambda }_{\mathrm{optimal}}\equiv \frac{\cos \left(\theta \right)+1}{{\sin }^2\left(\theta \right)}=\frac{1}{1-\cos \left(\theta \right)}.& \left(64\right)\end{array}$

[0132] The λ.sub.K=λ.sub.optimal case represents the maximal preferential amplification of lower values of cos(φ) achievable by the algorithm. Let p.sub.optimal(x) be the state probability function corresponding to λ.sub.K=λ.sub.optimal. From Equation (61),

[00036]$\begin{array}{cc}{p}_{\mathrm{optimal}}\left(x\right)=p_0\left(x\right)\left[1-\frac{\cos \left(\phi \left(x\right)\right)-\cos \left(\theta \right)}{1-\cos \left(\theta \right)}\right].& \left(65\right)\end{array}$

[0133] Note that p.sub.optimal(x)=0 for inputs x with the highest possible value of cos(φ(x)), namely 1. In other words, p.sub.optimal reaches the limit set by the non-negativity of probabilities, in the context of the non-boolean amplitude amplification algorithm 400, 500 described hereinabove.

[0134] Number of Iterations to Perform:

[0135] In the non-boolean amplitude amplification algorithm 400, 500 described hereinabove, the number of iterations K to perform is left unspecified. Armed with Equation (62), this aspect of the algorithm 400, 500 will now be described in detail. Higher values of λ.sub.K are advantageous to preferentially amplify lower values of cos(φ). Equation (62) illustrates that λ.sub.K may be monotonically increasing for K=0, 1, . . . as long as 0≤(2K+1)θ≤π+θ or, equivalently, for

[00037]$\begin{array}{cc}0\le K\le .Math.\frac{\pi }{2\theta }.Math.,& \left(66\right)\end{array}$

where └v┘ denotes the floor of v. A good approach is to stop the algorithm 400, 500 just before the first iteration that, if performed, would cause value of λ.sub.K to decrease (that is, from its value after the previous iteration). This approach leads to the choice K for the number of iterations to perform, given by

[00038]$\begin{array}{cc}\tilde{K}=.Math.\frac{\pi }{2\theta }.Math..& \left(67\right)\end{array}$

[0136] The corresponding value of λ.sub.K for K={tilde over (K)} is given by Equation (68):

[00039]$\begin{array}{cc}{\lambda }_{\tilde{K}}=\frac{1}{{\sin }^2\left(\theta \right)}\left[\cos \left(\theta \right)-\cos \left(.Math.\frac{\pi }{2\theta }.Math.2\theta +\theta \right)\right].& \left(68\right)\end{array}$

[0137] The choice {tilde over (K)} in Equation (67) for the number of iterations offers an amplification iff π>2θ>0 or, equivalently, iff 0<cos(θ)<1. At one of the extremes, namely θ=π/2, one has λ.sub.{tilde over (K)}=0. The other extreme, namely cos(θ)=1, corresponds to every state x with a non zero amplitude in the initial state |ψ.sub.0 having cos(φ(x))=1. There is no scope for preferential amplification in this case.

[0138] Equation (68) illustrates that λ.sub.K exactly equals λ.sub.optimal defined in Equation (64) if π/(2θ) is a half-integer. In terms of θ, this condition may be written as follows (Equation (69)):

[00040]$\begin{array}{cc}\theta \in \left\{\frac{\pi }{3},\frac{\pi }{5},\frac{\pi }{7},.Math.\left(\mathrm{harmonic}\mathrm{progression}\right)\right\}.Math.{\lambda }_{\tilde{K}}={\lambda }_{\mathrm{optimal}}.& \left(69\right)\end{array}$

[0139] For generic values of θ, Equation (68) illustrates that AR satisfies the following (Equation 70)):

[00041]$\begin{array}{cc}\frac{2\cos \left(\theta \right)}{{\sin }^2\left(\theta \right)}\le {\lambda }_{\tilde{K}}\le {\lambda }_{\mathrm{optimal}}=\frac{\cos \left(\theta \right)+1}{{\sin }^2\left(\theta \right)}.& \left(70\right)\end{array}$

[0140] This equation may be rewritten as follows (Equation (71)):

λ.sub.optimal[1−tan.sup.2(θ/2)]≤λ.sub.{tilde over (K)}≤λ.sub.optimal,  (71)

using the following identity:

[00042]$\begin{array}{cc}\frac{2\cos \left(\theta \right)}{\cos \left(\theta \right)+1}=\frac{2\left[{\cos }^2\left(\theta /2\right)-{\sin }^2\left(\theta /2\right)\right]}{2{\cos }^2\left(\theta /2\right)-1+1}=1-{\tan }^2\left(\theta /2\right).& \left(72\right)\end{array}$

[0141] Equation (71) illustrates that for small θ, λ.sub.R is approximately equal to λ.sub.optimal, (θ.sup.2) relative error.

[0142] Mean and Higher Moments of Cos(φ) after K Iterations:

[0143] Let μ.sub.K.sup.(n) be the n-th raw moment of cos(φ(x)) for a random value of x sampled by measuring the second register after K iterations.

[00043]$\begin{array}{cc}{\mu }_K^{\left(n\right)}\equiv \underset{x=0}{\overset{N-1}{.Math.}}{p}_K\left(x\right){\cos }^n\left(\phi \left(x\right)\right).& \left(73\right)\end{array}$

[0144] Under the notation of Equation (73), μ.sub.0.sup.(1) is simply cos(θ). From Equation (61),μ.sub.K.sup.(n) may be written in terms of the initial moments (K=0) as follows (Equation (74)):

[00044]$\begin{array}{cc}\begin{array}{c}{\mu }_K^{\left(n\right)}=\underset{x=0}{\overset{N-1}{.Math.}}{p}_0\left(x\right){\cos }^n\left(\phi \left(x\right)\right)\left[1-{\lambda }_K\left[\cos \left(\phi \left(x\right)\right)-\cos \left(\theta \right)\right]\right]\\ ={\mu }_0^{\left(n\right)}-{\lambda }_K\left[{\mu }_0^{\left(n+1\right)}-{\mu }_0^{\left(n\right)}{\mu }_0^{\left(1\right)}\right]\end{array}.& \left(74\right)\end{array}$

[0145] In particular, let μ.sub.K and σ.sub.K.sup.2 represent the expected value and variance, respectively, of cos(φ(x)) after K iterations.

μ.sub.K≡μ.sub.K.sup.(1),

σ.sub.K.sup.2≡μ.sub.K.sup.(2)−[μ.sub.K.sup.(1)].sup.2.  (75)

[0146] Now, the result in Equation (74) for n=1 may be written as follows (Equation (76)):

μ.sub.K−μ.sub.0=−λ.sub.Kσ.sub.0.sup.2.  (76)

[0147] For λ.sub.K>0, Equation (76) captures the reduction in the expected value of cos(φ(x)) resulting from K iterations of the algorithm 400, 500.

[0148] Cumulative Distribution Function of Cos(φ) after K Iterations:

[0149] Let F.sub.K.sup.cos(y) be the probability that cos(φ(x))≤y for an x sampled as per the probability distribution p.sub.K. F.sub.K.sup.cos is the cumulative distribution function of cos(φ) for a measurement after K iterations, and may be written as follows (Equations (77) and (78)):

[00045]$\begin{array}{cc}{F}_K^{\cos }\left(y\right)=\underset{x=0}{\overset{N-1}{.Math.}}\left[p_K\left(x\right)1_{[0,\infty )}\left[y-\cos \left(\phi \left(x\right)\right)\right]\right],& \left(77\right)\end{array}$$\begin{array}{cc}1-F_K^{\cos }\left(y\right)=\underset{x=0}{\overset{N-1}{.Math.}}\left[p_K\left(x\right)\left(1-1_{[0,\infty )}\left[y-\cos \left(\phi \left(x\right)\right)\right]\right)\right],& \left(78\right)\end{array}$

where 1.sub.|0,∞) is the Heaviside step function, which equals 0 when its argument is negative and 1 when its argument is non-negative. Using the expression for p.sub.K in Equation (61), these equations may be written as follows (Equations (79) and (80)):

[00046]$\begin{array}{cc}{F}_K^{\cos }\left(y\right)=F_0^{\cos }\left(y\right)\left(1+{\lambda }_K{\mu }_0\right)-{\lambda }_K\underset{x=0}{\overset{N-1}{.Math.}}\left\{p_0\left(x\right)\cos \left(\phi \left(x\right)\right)1_{[0,\infty )}\left[y-\cos \left(\phi \left(x\right)\right)\right]\right\},& \left(79\right)\end{array}$$\begin{array}{cc}1-F_K^{\cos }\left(y\right)=\left(1-F_0^{\cos }\left(y\right)\right)\left(1+{\lambda }_K{\mu }_0\right)-{\lambda }_K\underset{x=0}{\overset{N-1}{.Math.}}\left\{p_0\left(x\right)\cos \left(\phi \left(x\right)\right)\left[1-1_{[0,\infty )}\left[y-\cos \left(\phi \left(x\right)\right)\right]\right]\right\}.& \left(80\right)\end{array}$

[0150] Every x that provides a non-zero contribution to the summation in Equation (79) satisfies cos(φ(x))≤y. This fact may be used to write Equation (81), as follows:

λ.sub.K≥0.Math.F.sub.K.sup.cos(y)≥F.sub.0.sup.cos(y)(1+λ.sub.K(μ.sub.0−y)).  (81)

[0151] Likewise, every x that provides a non-zero contribution to the summation in Equation (80) satisfies cos(φ(x))>y. This fact may be used to write Equation (82), as follows:

λ.sub.K≥0.Math.1−F.sub.K.sup.cos(y)≤(1−F.sub.0.sup.cos(y))(1+λ.sub.K(μ.sub.0−y)).  (82)

[0152] The inequalities in Equations (81) and (82) may be summarized as follows (Equation (83)):

λ.sub.K≥0.Math.F.sub.k.sup.cos(y)≥F.sub.0.sup.cos(y)+λ.sub.K max{F.sub.0.sup.cos(y)(μ.sub.0−y),(1−F.sub.0.sup.cos(y))(y−μ.sub.0)},   (83)

where the max function represents the maximum of its two arguments. This equation provides a lower bound on the probability that a measurement after K iterations yields a state whose cos(φ) value is no higher than y. Derivation of stronger bounds (or even the exact expression) for F.sub.K.sup.cos(y) may be possible if additional information is known about the initial distribution of cos(φ). For y≤μ.sub.0, the first argument of the max function in Equation (83) will be active, and for y≥μ.sub.0, the second argument will be active.

[0153] For the λ.sub.K≤0 case, it can similarly be shown that

λ.sub.K≤0.Math.F.sub.K.sup.cos(y)≤F.sub.0.sup.cos(y)+λ.sub.K min{F.sub.0.sup.cos(y)(μ.sub.0−y),(1−F.sub.0.sup.cos(y))(y−μ.sub.0)},   (84)

where the min function represents the minimum of its two arguments.

[0154] Boolean Oracle Case:

[0155] As described in the “Number of Iterations to Perform” section hereinabove, the heuristic choice for the number of iterations for the non-boolean amplitude amplification algorithm of the present invention (namely {tilde over (K)}=└π/(2θ)┘) is different from, but analogous to, the result for known boolean amplitude amplification algorithm of the prior art (namely └π/(4θ.sub.a)┘). Consider the parameter θ in the boolean oracle case, say θ.sub.bool. Let P.sub.0.sup.good be the probability for a measurement on the initial state |ψ.sub.0 to yield a winning state. From Equation (30),

[00047]$\begin{array}{cc}\cos \left({\theta }_{\mathrm{bool}}\right)=\left[-1\times P_0^{\mathrm{good}}\right]+\left[1\times \left(1-P_0^{\mathrm{good}}\right)\right]=1-2P_0^{\mathrm{good}},& \left(85\right)\end{array}$$\begin{array}{cc}.Math.{\sin }^2\left({\theta }_{\mathrm{bool}}/2\right)=P_0^{\mathrm{good}}.& \left(86\right)\end{array}$

[0156] Thus, in the boolean oracle case, sin.sup.2(θ/2) reduces to the initial probability of “success” (that is, measuring a winning state), which is captured by sin.sup.2(θ.sub.a) in known boolean amplitude amplification algorithm(s). The parameter θ used herein reduces to the parameter 2θ.sub.a used in known boolean amplitude amplification algorithm(s), and └π/(2θ)┘ reduces to └π/(4θ.sub.a)┘.

[0157] In this way, the results of the “Analysis of the Non-Boolean Amplitude Amplification Algorithm” section hereinabove in general, and the “Number of Iterations to perform” section hereinabove in particular, may be seen as generalizations of the corresponding results in known boolean amplitude amplification algorithm(s) as described hereinabove.

[0158] Alternative Formulation of the Algorithm:

[0159] Referring again to FIGS. 4 and 5, in the formulation of the non-boolean amplitude amplification algorithm 400, 500 of the present invention, an ancilla qubit (first register) 410 may be included for the purpose of making the quantity Ψ.sub.0|U.sub.φ|Ψ.sub.0=Ψ.sub.0|α real valued. If, in a particular use case, it is guaranteed that ψ.sub.0|U.sub.φ|ψ.sub.0 will be real-valued (or have a negligible imaginary part, for example, and without limitation, by replacing the function φ(x) with φ′(x)=r(x)φ(x), where r: {0, 1, . . . N−1}.fwdarw.{−1,+1} is a random function independent of φ(x), with mean 0 (for x sampled by measuring |ψ.sub.0) even without introducing the ancilla 410, then the algorithm 400, 500 described above may be used without the ancilla 410: that is, may alternate between applying operator 430, 432 denoted S.sub.ψ.sub.0 U.sub.φ during the odd iterations and applying operator 430, 434 denoted S.sub.ψ.sub.0 U.sub.φ.sup.† during the even iterations. In other words, the properties and structure of two-register system are not exploited in the algorithm description, beyond making Ψ.sub.0|U.sub.φ|Ψ.sub.0 real-valued.

[0160] However, Equations (33) and (34) illustrate that the states |α=U.sub.φ|Ψ.sub.0 and |β=U.sub.φ.sup.†|Ψ.sub.0 are related by

|β=[X.Math.I]|α,|α=[X.Math.I]|β,  (87)

where X is the bit-flip or the Pauli-X operator 340. This relation may be exploited to avoid having two separate cases—k being odd and even—in the final expression for |Ψ.sub.k in Equation (51). The expression for both cases may be made the same by acting the Pauli-X gate 340 on the ancilla 410, once at the end, if the total number of iterations is even.

[0161] More interestingly, the relationship between |α and |β may be used to avoid having two different operations in the first place, for the odd and even iterations. This leads to the following alternative formulation of the non-boolean amplitude amplification algorithm: During each iteration, odd or even, act the same operator Q.sub.iter defined by

Q.sub.iter≡S.sub.Ψ.sub.0U.sub.φ[X.Math.I].  (88)

[0162] This alternative formulation is depicted as a circuit 700 in FIG. 7 and as a pseudocode 800 in FIG. 8.

[0163] From Equations (43) and (87), the action of Q.sub.iter on and |α may be derived as follows (Equations (89) and (90)):

[00048]$\begin{array}{cc}{Q}_{iter}.Math.{\Psi }_0.Math.=S_{{\Psi }_0}{U}_{\phi }.Math.{\Psi }_0.Math.=2\cos \left(\theta \right).Math.{\Psi }_0.Math.-.Math.\alpha .Math.,& \left(89\right)\end{array}$$\begin{array}{cc}{Q}_{iter}.Math.\alpha .Math.=S_{{\Psi }_0}{U}_{\phi }.Math.\beta .Math.=.Math.{\Psi }_0.Math..& \left(90\right)\end{array}$

[0164] Let |Ψ.sub.k.sup.alt be the state of the two-register system after k iterations under this alternative formulation 700, 800 (before any measurement of the ancilla 410), as follows (Equation (91)):

|Ψ.sub.k.sup.alt)≡Q.sub.iter.sup.k|Ψ.sub.0.  (91)

[0165] Using similar manipulations as those leading to Equation (51) hereinabove, |Ψ.sub.k.sup.alt) may be expressed, for all k≥0, as follows (Equation (92)):

[00049]$\begin{array}{cc}.Math.{\Psi }_k^{\mathrm{alt}}.Math.=\frac{1}{\sin \left(\theta \right)}[\sin \left(\left(k+1\right)\theta \right).Math.{\Psi }_0.Math.-\sin \left(k\theta \right).Math.\alpha .Math.].& \left(92\right)\end{array}$

[0166] Note that this expression for |Ψ.sub.k.sup.alt) is almost identical to the expression for |Ψ.sub.k in Equation (51), but without two separate cases for the odd and even values of k. Much of the analysis of the original formulation of the non-boolean amplitude amplification algorithm 400, 500 described hereinabove holds for the alternative formulation 700, 800 described hereinabove as well, including the expressions for the state probabilities p.sub.K(x), mean μ.sub.K, raw moments λ.sub.K.sup.(n), and the cumulative distribution function F.sub.K.sup.cos.

[0167] In addition to simplifying the amplification algorithm (by using the same operation for every iteration), the Q.sub.iter operator used in algorithms 700, 800 allows for a clearer presentation of the quantum mean estimation algorithm, as described hereinbelow.

[0168] Quantum Mean Estimation Algorithm:

[0169] A quantum mean estimation algorithm according to certain embodiments of the present invention may operate to estimate the expected value of e.sup.iφ(x) for x sampled by measuring a given superposition state |ψ.sub.0. Let E.sub.ψ.sub.0[e.sup.iφ] denote this expected value, as follows (Equation (93)):

[00050]$\begin{array}{cc}{E}_{{\psi }_0}\left[e^{i\phi }\right]\equiv .Math.{\psi }_0.Math.U_{\phi }.Math.{\psi }_0.Math.=\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2{e}^{i\phi \left(x\right)}.& \left(93\right)\end{array}$

[0170] This equation may be written as follows (Equation (94)):

E.sub.ψ.sub.0[e.sup.iφ]=Re[E.sub.ψ.sub.0[e.sup.iφ]]+i Im[E.sub.ψ.sub.0[e.sup.iφ]],  (94)

where the real and imaginary parts are given by Equations (95) and (96), respectively, as follows:

[00051]$\begin{array}{cc}\mathrm{Re}\left[E_{{\psi }_0}\left[e^{i\phi }\right]\right]=\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2\cos \left(\phi \left(x\right)\right),& \left(95\right)\end{array}$$\begin{array}{cc}\mathrm{Im}\left[E_{{\psi }_0}\left[e^{i\phi }\right]\right]=\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2\sin \left(\phi \left(x\right)\right).& \left(96\right)\end{array}$

[0171] The mean estimation may therefore be performed in two parts: one for estimating the mean of cos(φ), and the other for estimating the mean of sin(φ). Note that the expectation of cos(φ) under the state |ψ.sub.0 is precisely cos(θ) defined in Equation (30).

[0172] Estimating the Mean of cos(φ):

[0173] The connection shown in the “Boolean Oracle Case” section hereinabove between the parameter θ and the parameter θ.sub.a serves as the intuition behind the quantum mean estimation algorithm of the present invention. In the known boolean amplitude estimation algorithm described hereinabove, the parameter θ.sub.a is estimated using QPE (Note: The estimation of θ.sub.Q is only (needed to be) performed up to a two-fold ambiguity of {θ.sub.a,π−θ.sub.a}). The estimate for θ.sub.a is then turned into an estimate for the initial winning probability. The non-boolean quantum mean estimation algorithm of the present invention may operate to estimate the parameter θ defined in Equation (30) using QPE (Note: The estimation of θ is only (needed to be) performed up to a two fold ambiguity of {θ,2π−θ}). The estimate for θ may then be translated into an estimate for the initial expected value of cos(φ(x)), namely cos(θ).

[0174] Toward the end of actualizing the abovementioned intuition into a working algorithm, a key observation is that |Ψ may be written as follows (Equation (97)):

[00052]$\begin{array}{cc}.Math.{\Psi }_0.Math.=\frac{.Math.{\eta }_{+}.Math.-.Math.{\eta }_{-}.Math.}{\sqrt{2}},& \left(97\right)\end{array}$

where |η.sub.+ and |η.sub.− are given by Equation (98):

[00053]$\begin{array}{cc}.Math.{\eta }_{\pm }.Math.=\frac{e^{\pm i\theta }.Math.{\Psi }_0.Math.-.Math.\alpha .Math.}{i\sqrt{2}\sin \left(\theta \right)}.& \left(98\right)\end{array}$

[0175] Note: The forms of the eigenstates |η.sub.+ and |η.sub.− in Equation (98) may be determined from the form of the matrix S.sub.θ in Equation (48). These forms may also be determined from Equation (92) by rewriting the sin functions in terms of complex exponential functions.

[0176] The expressions for |η.sub.+ and |η.sub.− in Equation (98) may be used to verify Equation (97). Crucially, |η.sub.+ and |η.sub.− are unit normalized eigenstates of the unitary operator Q.sub.iter, with eigenvalues e.sup.iθ and e.sup.−iθ, respectively.

Q.sub.iter|η.sub.±=e.sup.±iθ|η.sub.±,  (99)

η.sub.±|η.sub.±=1.  (100)

[0177] The properties of |η.sub.+ and |η.sub.− in Equation (99) and Equation (100) may be verified using Equation (89), Equation (90), and Equation (98). The observations in Equation (97) and Equation (99) lead to the following algorithm for estimating cos(θ):

[0178] (1) Perform the QPE algorithm with a) the two-register operator Q.sub.iter serving the role of the unitary operator under consideration, and b) the superposition state |Ψ.sub.0) in place of the eigenstate required by the QPE algorithm as input. Let the output of this step, appropriately scaled to be an estimate of the phase angle in the range [0,2π), be {circumflex over (ω)}.

[0179] (2) Return cos({circumflex over (ω)}) as the estimate for cos(θ) (i.e., the real part of E.sub.ψ.sub.0[e.sup.iφ]). Note: If the circuit implementation of Q.sub.iter is wrong by an overall (state independent) phase ϕ.sub.err, then the estimate for cos(θ) is cos({circumflex over (ω)}−ϕ.sub.err). This is important, for example, if the operation [2|0,00,0|−I] is only implemented up to a factor of −1 (i.e., with ϕ.sub.err=π). Note that the final state probabilities under the non-boolean amplitude amplification algorithm are unaffected by such an overall phase error.

[0180] Proof of correctness of the algorithm: |Ψ.sub.0 is a superposition of the eigenstates |η.sub.+ and |η.sub.− of the unitary operator Q.sub.iter. This implies that {circumflex over (ω)} may either be an estimate for the phase angle of |η.sub.+, namely θ, or an estimate for the phase angle of |η.sub.−, namely 2π−θ. (Note: If θ=0, the phase angle being estimated is 0 for both |η.sub.+ and |η.sub.−. For θ≠0, {circumflex over (ω)} will be an estimate for either θ or 2π−θ with equal probability. Since θ lies in [0,π] and 2π−θ lies in [π,2π], the output {circumflex over (ω)} can be converted into an estimate for θ alone (although doing so is not necessary)). Since, cos(2π−θ)=cos(θ), it follows that cos({circumflex over (ω)}) is an estimate for cos(θ).

[0181] Estimating the Mean of e.sup.iφ:

[0182] The algorithm for estimating the expected value of cos(φ) in the section hereinabove may be re-purposed to estimate the expected value of sin(φ) by using the fact that

sin(φ)=cos(φ−π/2).  (101)

[0183] In other words, the imaginary part of E.sub.ψ.sub.0[e.sup.iφ] is the real part of E.sub.ψ.sub.0[e.sup.i(φ−π/2)]. By using the oracle U.sub.φ−π/2 (for the function φ−π/2), instead of U.sub.φ, in the mean estimation algorithm of the preceding section, the imaginary part of E.sub.ψ.sub.0[e.sup.iφ] may also be estimated. This completes the estimation of E.sub.ψ.sub.0[e.sup.iφ].

[0184] For concreteness, U.sub.φ−π2 may be explicitly written as

U.sub.φ−π/2=e.sup.−iπ/2|00|.Math.U.sub.φ+e.sup.iπ/2|11|.Math.U.sub.φ.sup.†.  (102)

[0185] Referring now to FIG. 9, exemplary circuit 900 illustrates implementation of U.sub.φ−π/2 using the oracle 932 denoted U.sub.φ, the bit-flip operator 940 denoted X, and the phase-shift operator R.sub.ϕ (shown as elements 950, 952).

[0186] Note that the algorithm does not use the knowledge that {|0, . . . , |N−1} is an eigenbasis of U.sub.φ. Therefore, this algorithm may be used to estimate ψ.sub.0|U|ψ.sub.0 for any unitary operator U.

[0187] Quantum Speedup:

[0188] The speedup offered by the quantum mean estimation algorithm 900 over classical methods will now be discussed in detail, in the context of estimating the mean of cos(φ) alone. This discussion may be extended in a straightforward way to estimation of E.sub.ψ.sub.0[e.sup.iφ].

[0189] Classical Approaches to Estimating the Mean: For an arbitrary function φ and a known sampling distribution p.sub.0(x) for the inputs x, one classical approach to finding the mean of cos(φ(x)) is to sequentially query the value of φ(x) for all the inputs and use the query results to compute the mean. Let the permutation (x.sub.0, x.sub.1, . . . , x.sub.N-1) of the inputs (0, 1, . . . , N−1) be the order in which the inputs are queried. The range of allowed values of cos(θ), based only on results for the first q inputs, is given by the following (Equation (103)):

[00054]$\begin{array}{cc}\left[\underset{j=0}{\overset{q-1}{.Math.}}{p}_0\left(x\right)\cos \left(\phi \left(x_j\right)\right)-\underset{j=q}{\overset{N-1}{.Math.}}{p}_0\left(x\right)\right]\le \cos \left(\theta \right)\le \left[\underset{j=0}{\overset{q-1}{.Math.}}{p}_0\left(x\right)\cos \left(\phi \left(x_j\right)\right)+\underset{j=q}{\overset{N-1}{.Math.}}{p}_0\left(x\right)\right].& \left(103\right)\end{array}$

[0190] These bounds are derived by setting the values of cos(φ) for all the unqueried inputs to their highest and lowest possible values, namely +1 and −1. The range of allowed values of cos(θ) shrinks as more and more inputs are queried. In particular, if p.sub.0(x) is equal for all the inputs x, the width of the allowed range (based on q queries) is given by 2(N−q)/N. This strategy may take (N) queries before the width of the allowed range reduces to even, say, 1. Thus, this strategy will not be feasible for large values of N.

[0191] An alternative classical approach is to probabilistically estimate the expected value as follows:

[0192] (1) Independently sample q random inputs (x.sub.1, . . . x.sub.q) as per the distribution p.sub.0.

[0193] (2) Return the sample mean of cos(φ) over the random inputs as an estimate for cos(θ).

[0194] Under this approach, the standard deviation of the estimate scales as ˜σ.sub.0/√{square root over (q)}, where σ.sub.0 is the standard deviation of cos(φ) under the distribution p.sub.0.

[0195] Precision Vs Number of Queries for the Quantum Algorithm: Note that one call to the operator Q.sub.iter corresponds to (1) calls to A.sub.0 and U.sub.φ (and their inverses). Let q be the number of times the (controlled) Q.sub.iter operation is performed during the QPE subroutine. As q increases, the uncertainty on the estimate for the phase-angle θ (up to a two-fold ambiguity) falls at the rate of (1/q). Consequently, the uncertainty on cos(θ) also falls at the rate of (1/q). This represents a quadratic speedup over the classical, probabilistic approach, under which the error falls as (1/√{square root over (q)}).

[0196] Note that the variance of the estimate for cos(θ) is independent of a) the size of input space N, and b) the variance σ.sub.0.sup.2 of cos(φ(x)) under the distribution p.sub.0(x). It only depends on the true value of cos(θ) and the number of queries q performed during the QPE subroutine.

[0197] Demonstrating the Algorithms Using a Toy Example

[0198] Referring again to FIGS. 4, 5, and 9, the non-boolean amplitude amplification algorithm 400, 500 and the mean estimation algorithm 900 will both be demonstrated using a toy example. Let the input to the oracle U.sub.φ (i.e., the second register 420), contain 8 qubits. This leads to 2.sup.8=256 basis input states, namely |0, . . . , |255. Let the toy function φ(x) be

[00055]$\begin{array}{cc}\begin{array}{cc}\phi \left(x\right)=\frac{x}{255}\frac{\pi }{4},& \mathrm{for}x=0,1,.Math.,255.\end{array}& \left(104\right)\end{array}$

[0199] The largest phase-shift applied by the corresponding oracle 432 denoted U.sub.φ on any basis state is π/4, for the state |255. Since, cos(φ(x)) is monotonically decreasing in x, the goal of the amplitude amplification algorithm 400, 500 is to amplify the probabilities of higher values of x.

[0200] Let the initial state, from which the amplification is performed, be the uniform superposition state |s.

[00056]$\begin{array}{cc}.Math.{\psi }_0.Math.=.Math.s.Math.=\frac{1}{\sqrt{256}}\underset{x=0}{\overset{255}{.Math.}}.Math.x.Math..& \left(105\right)\end{array}$

[0201] Such simple forms for the oracle function and the initial state allow for a good demonstration of the algorithms of the present invention.

[0202] For this toy example, from Equation (30), cos(θ) and θ are given by

[00057]$\begin{array}{cc}\begin{array}{c}\cos \left(\theta \right)=\frac{1}{256}\underset{x=0}{\overset{255}{.Math.}}\cos \left(\frac{x}{255}\frac{\pi }{4}\right)\approx 0.9001,\\ \theta \approx 0.457.\end{array}& \left(106\right)\end{array}$

[0203] Referring now to FIG. 10, graph 1000 shows the value 1010 of λ.sub.K, from Equation (62), for the first few of a range 1020 of values of K (more specifically, for K=0, 1, . . . , 14). The dots 1030 (only a subset labeled, for clarity) correspond to the different integer values 1020 of K. The black solid curve 1040 depicts the sinusoidal dependence of the value 1010 of λ.sub.K on the range 1040 of K. The dotted lines 1050 indicate that the value 1010 of λ.sub.K oscillates around a reference 1060 of cos(θ)/sin.sup.2(θ) with an amplitude 1070 of 1/sin.sup.2(θ) and a period 1080 of π/θ (in K values). The heuristic choice for the total number of iterations {tilde over (K)}=[π/(2θ)] is 3 for this example.

[0204] Amplitude Amplification:

[0205] Continuing with the toy example, and referring now to chart 1100 of FIG. 11, the quantum circuit for the non-boolean amplitude amplification algorithm 400, 500 was implemented in a quantum computing framework for three different values of the total number of iterations K, namely K=1, 2, and 3. The solid histograms 1130, 1140, 1150 show the observed measurement frequencies 1110 of the different values 1120 of x∈{0, 1 . . . , 255} after performing the non-boolean amplitude amplification algorithm 400, 500. The solid histograms 1130, 1140, 1150 correspond to the total number of iterations K being 1, 2, and 3, respectively. In each case, the observed frequencies are based on simulating (and measuring) the circuit for the algorithm 10.sup.6 times (i.e., 10.sup.6 shots). The dashed curves 1132, 1142, 1152, in good agreement (almost coincident) with their corresponding solid histograms 1130, 1140, 1150, respectively, show the predictions p.sub.K(x) (for the measurement frequencies) computed using Equation (61). While p.sub.K(x) may be technically defined only for the integer values of x, in FIG. 11 the dashed curves 1132, 1142, 1152 are interpolated for non-integer values of x using Equation (61).

[0206] As can be seen from FIG. 11, in each case, the algorithm 400, 500 preferentially amplifies lower values of cos(φ(x)) or, equivalently, higher values of x. This result is expected from the fact that λ.sub.K>0 for all three values of K. Furthermore, as K increases from 0 to {tilde over (K)}=3, the preferential amplification grows stronger. Note that the probabilities of the x-s for which cos (Φ(x))≈cos(θ) are left approximately unchanged by the algorithm, as indicated by the dotted crosshair 1160.

[0207] Mean Estimation:

[0208] Continuing with the toy example, and referring now to graphs 1200, 1250 of FIG. 12, results of demonstrating the quantum circuit for the non-boolean mean estimation algorithm 900 will now be described in detail. Only the estimation of cos(θ) (i.e., the real part of E.sub.ψ.sub.0[e.sup.iφ]) is demonstrated herein. The imaginary part may also be estimated using the same technique, as described in “Estimating the Mean of e.sup.iφ” hereinabove.

[0209] Let M be the number of qubits used in the QPE subroutine of the mean estimation algorithm 900, to contain the phase information. This corresponds to performing the (controlled) Q.sub.iter operation 2.sup.M−1 times during the QPE subroutine. Note that the estimated phase {circumflex over (ω)} may only take the following discrete values:

[00058]$\begin{array}{cc}\hat{\omega }\in \left\{\frac{2\pi j}{2^M}.Math.j\in \left\{0,.Math.,2^M-1\right\}\right\}.& \left(107\right)\end{array}$

[0210] In this way, the value of M controls the precision of the estimated phase and, by extension, the precision of the estimate for cos(θ); the higher the value of M, the higher the precision.

[0211] For the demonstration, two different quantum circuits were implemented, again using a quantum computing framework, for the mean estimation algorithm 900; one with M=4 and the other with M=8. Each circuit was simulated (and measured) 10.sup.6 times, to get a sample of {circumflex over (ω)} values all in the range [0,2π).

[0212] The observed frequencies 1210 (scaled by 1/bin-width) of the different values 1220 of {circumflex over (ω)} are shown as histograms on a linear scale in top graph 1200, and on a logarithmic scale in the bottom graph 1250. Here the bin-width of the histograms is given by 2π/2.sup.M, which is the difference between neighboring allowed values of {circumflex over (ω)}.

[0213] The dashed histogram 1230 and solid histogram 1240 correspond to the circuits with 4 and 8 phase measurement qubits, respectively. The exact values of θ and 2π−θ for the toy example are indicated with vertical dotted lines 1232, 1242, respectively. In both cases (M=4 and M=8), the observed frequencies peak near the exact values of θ and 2π−θ, demonstrating that {circumflex over (ω)} is a good estimate for them, up to a two-fold ambiguity. (Note: The upward trends near the left (−1) and right (+1) edges of the plots in are artifacts caused by the Jacobian determinant for the map from {circumflex over (ω)} to cos({circumflex over (ω)})). Furthermore, as expected, using more qubits for estimating the phase leads to a more precise estimate.

[0214] Ancilla-Free Versions of the Algorithms:

[0215] Both algorithms introduced this in this paper so far, namely (1) the amplitude algorithm of FIGS. 4 and 5 and its alternative formulation in FIG. 8, and (2) the mean estimation algorithm of FIG. 9, use an ancilla qubit to make the quantity Ψ.sub.0|U.sub.φ|Ψ.sub.0 real valued. This is important for achieving the respective goals of the algorithms. However, the same algorithms may be performed without the ancilla, albeit to achieve different goals, which may be relevant in some use cases.

[0216] Ancilla-Free Non-Boolean Amplitude Amplification:

[0217] The ancilla-free version of the amplitude amplification algorithm is almost identical to the algorithm introduced hereinabove at FIGS. 4 and 5. The only difference is that, in the ancilla-free version, the single-register operators S.sub.ψ.sub.0, U.sub.φ, and U.sub.φ.sup.† are used in place of the two-register operators S.sub.Ψ.sub.0, U.sub.φ, and U.sub.φ.sup.†, respectively. For concreteness, the ancilla-free algorithm may proceed as follows:

[0218] (1) Initialize a system in the state |ψ.sub.0.

[0219] (2) Act the operation S.sub.ψ.sub.0U.sub.φ during the odd iterations and S.sub.ψ.sub.0U.sub.φ.sup.† during the even iterations.

[0220] Analogous to the two-register states |α and |β in Equations (31) and (32), let the single-register states |α′ and |β′ be defined as

[00059]$\begin{array}{cc}\begin{array}{cc}2.Math.{\alpha }^{\prime }.Math.\equiv U_{\phi }.Math.{\psi }_0.Math.& =\underset{x=0}{\overset{N-1}{.Math.}}{e}^{i\phi \left(x\right)}{a}_0\left(x\right).Math.x.Math.,\\ .Math.{\beta }^{\prime }.Math.\equiv U_{\phi }^{†}.Math.{\psi }_0.Math.& =\underset{x=0}{\overset{N-1}{.Math.}}{e}^{-i\phi \left(x\right)}{a}_0\left(x\right).Math.x.Math..\end{array}& \left(108\right)\end{array}$

[0221] Analogous to θ defined in Equation (30), let θ′∈[0,π/2] and δ∈[0,2π) be implicitly defined by

[00060]$\begin{array}{cc}\cos \left({\theta }^{\prime }\right)e^{i\delta }\equiv .Math.{\psi }_0.Math.{\alpha }^{\prime }.Math.=\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2{e}^{i\phi \left(x\right)}.& \left(109\right)\end{array}$

[0222] Variables cos(θ′) and δ are the magnitude and phase, respectively, of the initial (i.e., x sampled from |ψ.sub.0) expected value of e.sup.iφ. An important difference between θ′ and θ is that cos(θ′) is restricted to be non-negative, unlike cos(θ), which may be positive, negative, or zero.

[0223] Note that cos(θ′) may be written as

[00061]$\begin{array}{cc}\cos \left({\theta }^{\prime }\right)=\underset{x=0}{\overset{N-1}{.Math.}}{.Math.a_0\left(x\right).Math.}^2{e}^{i\mathrm{\phi \prime }\left(x\right)},& \left(110\right)\end{array}$

where φ′(x) is given by

φ′(x)≡φ(x)−δ.  (111)

[0224] Acting the oracle U.sub.φ for the function φ may be thought of as acting the oracle U.sub.φ′ for the function φ′, followed by performing a global, state independent phase-shift of δ. Furthermore, from Equation (120), it can be seen that ψ.sub.0|U.sub.φ′|ψ.sub.0 is real-valued. This observation may be used to re-purpose the analysis in the “Analysis of the Non-Boolean Amplitude Amplification Algorithm” section hereinabove for the ancilla-free version; the corresponding results are presented here without explicit proofs.

[0225] Let |ψ.sub.k be the state of the system of the after k≥0 iterations of the ancilla-free algorithm. Analogous to Equation (51), |ψ′.sub.k may be written as

[00062]$\begin{array}{cc}.Math.{\psi }_k^{\prime }.Math.=\{\begin{array}{cc}\frac{e^{i\delta }}{\sin \left(\theta \text{'}\right)}[\sin \left(\left(k+1\right){\theta }^{\prime }\right).Math.{\psi }_0.Math.-\sin \left(k{\theta }^{\prime }\right)e^{-i\delta }.Math.{\alpha }^{\prime }.Math.],& \mathrm{if}k\mathrm{is}\mathrm{odd},\\ \frac{1}{\sin \left({\theta }^{\prime }\right)}[\sin \left(\left(k+1\right){\theta }^{\prime }\right).Math.{\psi }_0.Math.-\sin \left(k{\theta }^{\prime }\right)e^{i\delta }.Math.{\beta }^{\prime }.Math.],& \mathrm{if}k\mathrm{is}\mathrm{even}.\end{array}& \left(112\right)\end{array}$