Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Quantum and classical query complexities for generalized Deutsch–Jozsa problems
Ist Teil von
Quantum information processing, 2020-05, Vol.19 (5), Article 150
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2020
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
The Deutsch–Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. We generalize the Deutsch–Jozsa problem from the perspective of functional correlation, i.e., given two unknown
n
-bit Boolean functions
f
,
g
, the testing problem is to determine whether
|
C
(
f
,
g
)
|
=
0
or
|
C
(
f
,
g
)
|
=
ϵ
, where
1
/
2
(
n
-
1
)
≤
ϵ
≤
1
, promised that one of these is the case. Firstly, we propose two exact quantum algorithms for making distinction between
|
C
(
f
,
g
)
|
=
0
and
|
C
(
f
,
g
)
|
=
ϵ
using the Deutsch–Jozsa algorithm and also the amplitude amplification technique with query complexity of
O
(
1
/
ϵ
)
, where
C
(
f
,
g
) denotes the correlation between two Boolean functions
f
,
g
. Secondly, we present a lower bound
Ω
(
1
/
ϵ
)
on the above promised problem, which proves that our quantum algorithms are optimal. Thirdly, we can accurately distinguish
|
C
(
f
,
g
)
|
=
ε
from
|
C
(
f
,
g
)
|
=
1
using the similar methods mentioned above, where
0
≤
ε
≤
1
-
1
/
2
(
n
-
1
)
, promised that one of these is the case. We give a lower bound
Ω
(
1
/
1
-
ε
)
and an upper bound
O
(
4
/
1
-
ε
2
)
on this promised problem, which implies that the two bounds are almost tight. However, the query complexity of classical deterministic algorithms for two promised problems is
Θ
(
2
n
)
.