Distributed quantum computation has been considered an alternative and beneficial application in the noisy intermediate-scale quantum (NISQ) era, which needs fewer qubits and quantum gates. In this ...paper, we consider the Bernstein–Vazirani (BV) problem that needs to identify the hidden string s∈{0,1}n of Boolean function fs(x)=〈s⋅x〉=∑i=0n−1si⋅ximod2:{0,1}n→{0,1}. In the first instance, we subtly generate t subfunctions fSnj(mj)=〈Snj⋅mj〉:{0,1}nj→{0,1} according to fs(x), where Snj∈{0,1}nj, ∑j=0t−1nj=n, and j∈{0,1,…,t−1}. After that, we propose a distributed Bernstein–Vazirani algorithm (DBVA) with 2≤t≤n computing nodes, which will exactly acquire s=Sn0Sn1⋯Snt−1∈{0,1}n. To be more specific, (1) the query complexity of DBVA is O(1) rather than O(n); (2) the circuit depth of DBVA is 2max(n0,n1,…,nt−1)+3 less than the circuit depth of the BV algorithm 2n+3; (3) we request neither auxiliary qubits nor further classical queries; (4) we explicate how DBVA decomposes a 6-qubit BV algorithm into two 3-qubit or three 2-qubit BV algorithms on MindQuantum (a quantum software), which validates the correctness and practicable of DBVA. Eventually, by simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithms have the superiority of resisting noise.
This paper introduces a novel entanglement-based QKD protocol, that makes use of a modified symmetric version of the Bernstein-Vazirani algorithm, in order to achieve secure and efficient key ...distribution. Two variants of the protocol, one fully symmetric and one semi-symmetric, are presented. In both cases, the spatially separated Alice and Bob share multiple EPR pairs, each one qubit of the pair. The fully symmetric version allows both parties to input their tentative secret key from their respective location and acquire in the end a totally new and original key, an idea which was inspired by the Diffie-Hellman key exchange protocol. In the semi-symmetric version, Alice sends her chosen secret key to Bob (or vice versa). The performance of both protocols against an eavesdroppers attack is analyzed. Finally, in order to illustrate the operation of the protocols in practice, two small scale but detailed examples are given.
In this paper, we propose a novel quantum algorithm, based on the Bernstein–Vazirani algorithm, for finding
a
if the function
f
x
=
a
·
π
x
, where
a
,
x
∈
0
,
1
2
and
π
x
is a 2-bit permutation ...function. Note that the Bernstein–Vazirani algorithm cannot find
a
when we select the function
f
x
=
a
·
π
x
, where
π
x
=
0
1
2
3
2
0
1
3
. Our algorithm can be further applied to Nagata et al.’s problem. Our algorithm will output
g
A
1
and
g
A
0
if the function
f
x
=
g
A
1
g
A
0
2
·
π
x
, where
A
1
,
A
0
∈
0
,
1
m
,
x
∈
0
,
1
2
and
g
:
0
,
1
m
→
0
,
1
.
This study modifies Chen’s algorithm, the first exact quantum algorithm for testing 2-junta, and proposes an exact quantum learning algorithm for finding four dependent variables of the Boolean ...function
f
: {0, 1}
n
→ {0, 1} with one uncomplemented product of four variables. Typically, the dependent variables are obtained by evaluating the function 2
n
times in the worst-case. However, our proposed quantum algorithm only requires 8
log
2
n
function operations in the worst-case. Additionally, we analyze the average-case of our algorithms. Our algorithm requires on the average 10.16 function operations at the most. Furthermore, we propose an exact quantum learning algorithm for finding
k
dependent variables of the Boolean function with one uncomplemented product of
k
variables, where
k
> 4. Based on our analysis, the proposed quantum algorithm only requires 4
klog
2
n
function operations in the worst-case, provided that
k
is given. Additionally, in the average-case, the proposed algorithm requires
16
5
k
function operations at the most to find
k
dependent variables.
The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post-quantum world. At Asiacrypt 2017, Leander and May ...combined Grover’s and Simon’s quantum algorithms to break the FX-based block ciphers. Technically this result is based on the combination of the quantum algorithms of Grover’s and Simon’s for the first time in the cryptographic setting. In this study, we using Bernstein–Vazirani’s and Grover’s algorithms to generate a new quantum key-recovery attacks on different rounds of Feistel constructions. An advantage of our attack is the keys can be divided into multiple blocks to enter the S-box and realize the process of recovery; this method greatly reduces the complexity of key recovery. Hence, it has strong practicability for key recovery (e.g., DES, Camellia, etc.). In order to show that, a detailed process has been provided in this paper.
This paper proposes a novel quantum learning algorithm based on Bernstein and Vazirani’s quantum circuit to find the dependent variables of the 2-junta problem. Typically, for a given Boolean ...function
f
: {0, 1}
n
→ {0, 1} that depends on only 2 out of
n
variables, the dependent variables are obtained by evaluating the function 4
n
times in the worst-case. However, the proposed quantum algorithm only requires
O
(
log
2
n
) function operations in the worst-case. Moreover, the algorithm requires an average of 5.3 function operations at the most when
n
≥ 8.
In this paper, we propose a novel quantum learning algorithm, based on Younes’ quantum circuit, to find dependent variables of the Boolean function
f
:
0
,
1
n
→
0
,
1
with one uncomplemented product ...of two variables. Typically, in the worst-case scenario, two dependent variables are found by evaluating the function
O
n
times. However, our proposed quantum algorithm only requires
O
log
2
n
function operations in the worst-case. Additionally, we evaluate the average number to perform the function. In the average case, our algorithm requires
O
1
function operations.
The growth of data-driven technologies, 5G, and the Internet place enormous pressure on underlying information infrastructure. There exist numerous proposals on how to deal with the possible capacity ...crunch. However, the security of both optical and wireless networks lags behind reliable and spectrally efficient transmission. Significant achievements have been made recently in the quantum computing arena. Because most conventional cryptography systems rely on computational security, which guarantees the security against an efficient eavesdropper for a limited time, with the advancement in quantum computing this security can be compromised. To solve these problems, various schemes providing perfect/unconditional security have been proposed including physical-layer security (PLS), quantum key distribution (QKD), and post-quantum cryptography. Unfortunately, it is still not clear how to integrate those different proposals with higher level cryptography schemes. So the purpose of the Special Issue entitled “Physical-Layer Security, Quantum Key Distribution and Post-quantum Cryptography” was to integrate these various approaches and enable the next generation of cryptography systems whose security cannot be broken by quantum computers. This book represents the reprint of the papers accepted for publication in the Special Issue.
On a poset of quantum exact promise problems Combarro, Elías F.; Vallecorsa, Sofia; Meglio, Alberto Di ...
Quantum information processing,
06/2021, Volume:
20, Issue:
6
Journal Article
Peer reviewed
Open access
Two of the most well-known quantum algorithms, those introduced by Deutsch–Jozsa and Bernstein–Vazirani, can solve promise problems with just one function query, showing an oracular separation with ...deterministic classical algorithms. In this work, we generalise those methods to study a family of quantum algorithms that can, with just one query, exactly solve promise problems stated over Boolean functions. We also show that these problems can be naturally ordered, inducing a partially ordered set of promise problems. We study the properties of such a poset, showing that the Deutsch–Jozsa and Bernstein–Vazirani problems are, in a certain sense, extremal problems in it, determining some of its automorphisms and proving that it is connected. We also prove that, for the problems in the poset, the corresponding classical query complexities can take any value between 1 and
2
n
-
1
+
1
.
PDF
