NON-BOOLEAN QUANTUM AMPLITUDE AMPLIFICATION AND QUANTUM MEAN ESTIMATION SYSTEMS AND METHODS
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 φ 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 |ψ 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 ψ 0 |U φ |ψ 0 (i.e., the expected value of exp(iφ(x)) for a random x sampled by making a measurement on |ψ 0 ). The quantum mean estimation algorithm offers a quadratic speedup over its counterpart boolean algorithm known in the art.
1 . A method of performing quantum calculation on an oracle U φ for a non-boolean function φ, comprising:
initializing an input qubit in a |ψ 0 superposition state of a plurality of eigenstates |x to define a single-register state |ψ 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 of the plurality K of iterations, acting on the input basis state using a single-register unitary operator circuit S ψ 0 and a single-register controlled unitary operator circuit U φ , and
for even iterations of the plurality K of iterations, acting on the input basis state using the single-register unitary operator circuit S ψ 0 and a single-register controlled inverse unitary operator circuit U φ † .
2 . The method according to claim 1 , wherein the single-register controlled unitary operator circuit U φ and the single-register controlled inverse unitary operator circuit U φ † act on the input basis state as:
❘
"\[LeftBracketingBar]"
α
′
〉
≡
U
φ
❘
"\[LeftBracketingBar]"
ψ
0
〉
=
∑
x
=
0
N
-
1
e
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
,
❘
"\[LeftBracketingBar]"
β
′
〉
≡
U
φ
†
❘
"\[LeftBracketingBar]"
ψ
0
〉
=
∑
x
=
0
N
-
1
e
-
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
.
3 . The method according to claim 2 , further comprising a parameter θ′∈[0,π/2] and an independent phase shift δ∈[0,2π) defined by:
cos
(
θ
′
)
e
i
δ
≡
〈
ψ
0
❘
"\[LeftBracketingBar]"
α
′
〉
=
∑
x
=
0
N
-
1
❘
"\[LeftBracketingBar]"
a
0
(
x
)
❘
"\[RightBracketingBar]"
2
e
i
φ
(
x
)
;
wherein φ′(x) is defined by φ′(x)=φ(x)−δ;
wherein the cos (θ′) is a magnitude of an initial expected value of the e iφ and the independent phase shift δ is a phase for the initial expected value of the e iφ ; and
wherein the x is sampled from the input qubit in the single-register state |ψ 0 .
4 . The method according to claim 3 , wherein the cos (θ′) is of a non-negative value type.
5 . The method according to claim 4 , wherein the cos (θ′) is defined by the
cos
(
θ
′
)
=
∑
x
=
0
N
-
1
❘
"\[LeftBracketingBar]"
a
0
(
x
)
❘
"\[RightBracketingBar]"
2
e
i
φ
′
(
x
)
.
6 . The method according to claim 5 , wherein a state |ψ′ k after k≥0 iterations is defined by:
❘
"\[LeftBracketingBar]"
ψ
k
′
〉
=
{
e
i
δ
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
α
′
〉
]
,
if
the
k
is
odd
,
1
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
β
′
〉
]
,
if
the
k
is
even
.
7 . The method according to claim 6 , wherein p′ k (x) is a probability of measuring the input qubit in state x after the plurality K iterations, and:
p
K
′
(
x
)
=
p
0
(
x
)
{
1
-
λ
K
′
[
cos
(
φ
(
x
)
-
δ
)
-
cos
(
θ
′
)
]
}
,
wherein the λ′ K is defined by the
λ
K
′
=
2
sin
(
K
θ
′
)
sin
(
(
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
=
cos
(
θ
′
)
-
cos
(
(
2
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
;
and
wherein a probability amplification factor p′ K /p 0 is of a linear type in cos (φ−δ).
8 . A quantum computing device for performing quantum calculation on an oracle U φ for a non-boolean function φ, comprising:
a single-register quantum system comprising
an input qubit; and
a non-boolean quantum oracle comprising
a single-register unitary operator circuit S ψ 0 ,
a single-register controlled unitary operator circuit U φ , and
a single-register controlled inverse unitary operator circuit U φ † ;
wherein the quantum computing device is configured to
initialize the input qubit in a |ψ 0 superposition state of a plurality of eigenstates |x to define a single-register state |ψ 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 single-register unitary operator circuit S ψ 0 and the single-register controlled unitary operator circuit U φ , and
for even iterations of the plurality K of iterations, act on the input basis state using the single-register unitary operator circuit S ψ 0 and the single-register controlled inverse unitary operator circuit U φ † .
9 . The quantum computing device according to claim 8 , wherein the single-register controlled unitary operator circuit U φ and the single-register controlled inverse unitary operator circuit U φ † act on the input basis state as:
❘
"\[LeftBracketingBar]"
α
′
〉
≡
U
φ
|
ψ
0
〉
=
∑
x
=
0
N
-
1
e
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
,
❘
"\[LeftBracketingBar]"
β
′
〉
≡
U
φ
†
|
ψ
0
〉
=
∑
x
=
0
N
-
1
e
-
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
.
10 . The quantum computing device according to claim 9 , further comprising a parameter θ′∈[0,π/2] and an independent phase shift δ∈[0,2π) defined by:
cos
(
θ
′
)
e
i
δ
≡
〈
ψ
0
❘
"\[LeftBracketingBar]"
α
′
〉
=
∑
x
=
0
N
-
1
❘
"\[LeftBracketingBar]"
a
0
(
x
)
❘
"\[RightBracketingBar]"
2
e
i
φ
(
x
)
;
wherein φ′(x) is defined by the φ′(x)≡φ(x)−δ;
wherein the cos (θ′) is a magnitude of an initial expected value of the e iφ and the independent phase shift δ is a phase for the independent expected value of the e iφ ; and
wherein the x is sampled from the input qubit in the single-register state |ψ 0 .
11 . The quantum computing device according to claim 10 , wherein the cos (θ′) is of a non-negative value type.
12 . The quantum computing device according to claim 11 , wherein the cos (θ′) is defined by the cos (θ′)=Σ x=0 N-1 |α 0 (x)| 2 e iφ′ (x).
13 . The quantum computing device according to claim 12 , wherein a state |ψ′ k after k≥0 iterations is defined by:
❘
"\[LeftBracketingBar]"
ψ
k
′
〉
=
{
e
i
δ
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
α
′
〉
]
,
if
the
k
is
odd
,
1
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
β
′
〉
]
,
if
the
k
is
even
.
14 . The quantum computing device according to claim 13 , wherein p′ K (x) is a probability of measuring the input qubit in state x after the plurality K iterations, and:
p
K
′
(
x
)
=
p
0
(
x
)
{
1
-
λ
K
′
[
cos
(
φ
(
x
)
-
δ
)
-
cos
(
θ
′
)
]
}
;
wherein the λ′ K is defined by the
λ
K
′
=
2
sin
(
K
θ
′
)
sin
(
(
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
=
cos
(
θ
′
)
-
cos
(
(
2
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
;
and
wherein a probability amplification factor p′ K /p 0 is of a linear type in cos(φ−δ).
15 . A system of quantum circuits for implementing an oracle U φ for a non-boolean function φ, the system configured to:
initialize an input qubit in a |ψ 0 superposition state of a plurality of eigenstates [x to define a single-register state |ψ 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 single-register unitary operator circuit S ψ 0 and a single-register controlled unitary operator circuit U φ , and
for even iterations of the plurality K of iterations, act on the input basis state using the single-register unitary operator circuit S ψ 0 and a single-register controlled inverse unitary operator circuit U φ † .
16 . The system of quantum circuits according to claim 15 , wherein the single-register controlled unitary operator circuit S ψ 0 and the single-register controlled inverse unitary operator circuit U φ † act on the input basis state as:
❘
"\[LeftBracketingBar]"
α
′
〉
≡
U
φ
|
ψ
0
〉
=
∑
x
=
0
N
-
1
e
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
,
❘
"\[LeftBracketingBar]"
β
′
〉
≡
U
φ
†
❘
"\[LeftBracketingBar]"
ψ
0
〉
=
∑
x
=
0
N
-
1
e
-
i
φ
(
x
)
a
0
(
x
)
❘
"\[LeftBracketingBar]"
x
〉
.
17 . The system of quantum circuits according to claim 16 , further comprising a parameter θ′∈[0,π/2] and an independent phase shift δ∈[0,2π) defined by:
cos
(
θ
′
)
e
i
δ
≡
〈
ψ
0
❘
"\[LeftBracketingBar]"
α
′
〉
=
∑
x
=
0
N
-
1
❘
"\[LeftBracketingBar]"
a
0
(
x
)
❘
"\[RightBracketingBar]"
2
e
i
φ
(
x
)
.
wherein φ′(x) is defined by the φ′(x)≡φ(x)−δ;
wherein the cos (θ′) is a magnitude of an initial expected value of the e iφ and the independent phase shift δ is a phase for the initial expected value of the e iφ ; and
wherein the x is sampled from the input qubit in the single-register state |ψ 0 .
18 . The system of quantum circuits according to claim 17 , wherein the cos (θ′) is of a non-negative type.
19 . The system of quantum circuits according to claim 18 , wherein the cos (θ′) is defined by the:
cos
(
θ
′
)
=
∑
x
=
0
N
-
1
❘
"\[LeftBracketingBar]"
a
0
(
x
)
❘
"\[RightBracketingBar]"
2
e
i
φ
′
(
x
)
.
20 . The quantum computing device according to claim 19 , wherein a state |ψ′ k after k≥0 iterations is defined by the:
❘
"\[LeftBracketingBar]"
ψ
k
′
〉
=
{
e
i
δ
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
α
′
〉
]
,
if
the
k
is
odd
,
1
sin
(
θ
′
)
[
sin
(
(
k
+
1
)
θ
′
)
❘
"\[LeftBracketingBar]"
ψ
0
〉
-
sin
(
k
θ
′
)
e
-
i
δ
❘
"\[LeftBracketingBar]"
β
′
〉
]
,
if
the
k
is
even
;
and
wherein p′ K (x) is a probability of measuring the input qubit in state x after the plurality K iterations, and:
p
K
′
(
x
)
=
p
0
(
x
)
{
1
-
λ
K
′
[
cos
(
φ
(
x
)
-
δ
)
-
cos
(
θ
′
)
]
}
;
wherein the λ′ K is defined by the
λ
K
′
=
2
sin
(
K
θ
′
)
sin
(
(
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
=
cos
(
θ
′
)
-
cos
(
(
2
K
+
1
)
θ
′
)
sin
2
(
θ
′
)
;
and
wherein a probability amplification factor p′ K /p 0 is of a linear type in cos (φ−δ).