|
Vol.12
No.5&6, May 1, 2012
Research Articles:
Constant-optimized quantum circuits for modular multiplication and
exponentiation
(pp0361-0394)
Igor
L. Markov and Mehdi Saeedi
Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise
as components of modular exponentiation in Shor's quantum
number-factoring algorithm. However, existing generic constructions
focus on asymptotic gate count and circuit depth rather than actual
values, producing fairly large circuits not optimized for specific $C$
and $M$ values. In this work, we develop such optimizations in a
bottom-up fashion, starting with most convenient $C$ values. When
zero-initialized ancilla registers are available, we reduce the search
for compact circuits to a shortest-path problem. Some of our
modular-multiplication circuits are asymptotically smaller than previous
constructions, but worst-case bounds and average sizes remain $\Theta(n^2)$.
In the context of modular exponentiation, we offer several
constant-factor improvements, as well as an improvement by a constant
additive term that is significant for few-qubit circuits arising in
ongoing laboratory experiments with Shor's algorithm.
Encryption with weakly random keys using quantum ciphertext
(pp0395-0403)
Jan
Bouda, Matej Pivoluska, and Martin Plesch
The lack of perfect
randomness can cause significant problems in securing communication
between two parties. McInnes and Pinkas
\cite{McInnesPinkas-ImpossibilityofPrivate-1991} proved that
unconditionally secure encryption is impossible when the key is sampled
from a weak random source. The adversary can always gain some
information about the plaintext, regardless of the cryptosystem design.
Most notably, the adversary can obtain full information about the
plaintext if he has access to just two bits of information about the
source (irrespective on length of the key). In this paper we show that
for every weak random source there is a cryptosystem with a classical
plaintext, a classical key, and a quantum ciphertext that bounds the
adversary's probability $p$ to guess correctly the plaintext strictly
under the McInnes-Pinkas bound, except for a single case, where it
coincides with the bound. In addition, regardless of the source of
randomness, the adversary's probability $p$ is strictly smaller than $1$
as long as there is some uncertainty in the key (Shannon/min-entropy is
non-zero). These results are another demonstration that quantum
information processing can solve cryptographic tasks with strictly
higher security than classical information processing.
The monomial representations of the Clifford group
(pp0404-0431)
D.
Markus Appleby, Ingemar Bengtsson, Stephen Brierley, Markus Grassl,
David Gross, and Jan-Ake Larsson
We show that the Clifford group---the normaliser of the Weyl-Heisenberg
group---can be represented by monomial phase-permutation matrices if and
only if the dimension is a square number. This simplifies expressions
for SIC vectors, and has other applications to SICs and to Mutually
Unbiased Bases. Exact solutions for SICs in dimension 16 are presented
for the first time.
An intuitive proof of the data processing inequality
(pp0432-0441)
Normand
J. Beaudry and Renato Renner
The data processing inequality (DPI) is a fundamental feature of
information theory. Informally it states that you cannot increase the
information content of a quantum system by acting on it with a local
physical operation. When the smooth min-entropy is used as the relevant
information measure, then the DPI follows immediately from the
definition of the entropy. The DPI for the von Neumann entropy is then
obtained by specializing the DPI for the smooth min-entropy by using the
quantum asymptotic equipartition property (QAEP). We provide a short
proof of the QAEP and therefore obtain a self-contained proof of the DPI
for the von Neumann entropy.
Optimal estimation of quantum processes using incomplete
information: variational quantum process tomography
(pp0442-0447)
Thiago
O. Maciel and Reinaldo O. Vianna
We develop a quantum process tomography method, which variationally
reconstruct the map of a process, using noisy and incomplete information
about the dynamics. The new method encompasses the most common quantum
process tomography schemes. It is based on the variational quantum
tomography method (VQT) proposed by Maciel \emph{et al.} in
arXiv:1001.1793[quant-ph] \cite{VQT}.
Long distance two-party quantum crypto made simple
(pp0448-0460)
Iordanis
Kerenidis and Stephanie Wehner
Any two-party cryptographic primitive can be implemented using quantum
communication under the assumption that it is difficult to store a large
number of quantum states perfectly. However, achieving reliable quantum
communication over long distances remains a difficult problem. Here, we
consider a large network of nodes with only neighboring quantum links.
We exploit properties of this cloud of nodes to enable any two nodes to
achieve security even if they are not directly connected. Our results
are based on techniques from classical cryptography and do not resort to
technologically difficult procedures like entanglement swapping. More
precisely, we show that oblivious transfer can be achieved in such a
network if and only if there exists a path in the network between the
sender and the receiver along which all nodes are honest. Finally, we
show that useful notions of security can still be achieved when we relax
the assumption of an honest path. For example, we show that we can
combine our protocol for oblivious transfer with computational
assumptions such that we obtain security if either there exists an
honest path, or, as a backup, at least the adversary cannot solve a
computational problem.
Achieving perfect completeness in classical-witness quantum
Merlin-Arthur proof systems
(pp0461-0471)
Stephen
P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura
This paper proves that classical-witness quantum Merlin-Arthur proof
systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$.
This holds under any gate set with which the Hadamard and arbitrary
classical reversible transformations can be exactly implemented, \emph{e.g.},
${\{\textrm{Hadamard, Toffoli, NOT}\}}$. The proof is quantumly
nonrelativizing, and uses a simple but novel quantum technique that
\emph{additively} adjusts the success probability, which may be of
independent interest.
Matrices of fidelities for ensembles of
quantum states and the Holevo quantity
(pp0472-0489)
Mark
Fannes, Fernando de Melo, Wojciech Roga, and Karol Zyczkowski
The entropy of the Gram matrix of a joint purification of an ensemble of
$K$ mixed states yields an upper bound for the Holevo information $\chi$
of the ensemble. In this work we combine geometrical and probabilistic
aspects of the ensemble in order to obtain meaningful bounds for $\chi$.
This is done by constructing various correlation matrices involving
fidelities between every pair of states from the ensemble. For $K=3$
quantum states we design a matrix of root fidelities that is positive
and the entropy of which is conjectured to upper bound $\chi$. Slightly
weaker bounds are established for arbitrary ensembles. Finally, we
investigate correlation matrices involving multi-state correlations in
relation to the Holevo quantity.
Semi-loss-tolerant strong coin
flipping protocol using EPR pairs
(pp0490-0501)
Jia-Jun
Ma, Fen-Zhuo Guo, Qian Yang, Yan-Bing Li, and Qiao-Yan Wen
In this paper, we present a quantum strong coin flipping protocol. In
this protocol, an EPR pair and a quantum memory storage are made use of,
and losses in the quantum communication channel and quantum memory
storage are all analyzed. We obtain the bias in the fair scenario as a
function of $p$, where $p$ is the probability that the particle in Bob's
quantum memory storage is lost, which means our bias varies as the
degree of losses in the quantum memory storage changes. Therefore we
call our protocol semi-loss-tolerant. We also show that the bias
decreases with decreasing $p$. When $p$ approaches $0$, the bias
approaches 0.3536, which is less than that of all the previous
loss-tolerant protocols. Details of both parties' optimal cheating
strategies are also given and analyzed. What's more, experimental
feasibility is discussed and demonstrated. Compared with previous qubit-based
loss-tolerant SCF protocols, we introduce the EPR pair to keep our
protocol loss-tolerant while trying to push down the bias. In addition,
a quantum memory storage is used and the losses in it has been taken
into account. We obtain the bias in the fair scenario as a function of
$p$, where $p$ is the probability that the particle in Bob's quantum
memory storage is lost, which means our bias varies as the degree of
losses in the quantum memory storage changes. We also show that the bias
decreases with decreasing $p$. When $p$ approaches $0$, the bias
approaches 0.3536, which is less than that of all the previous
loss-tolerant protocols. Details of both parties' optimal cheating
strategies are also given and analyzed. Besides, experimental
feasibility is discussed and demonstrated.
Distribution of entanglement in networks of bi-partite
full-rank mixed states
(pp0502-0534)
G John
Lapeyre Jr., Sébastien Perseguers, Maciej Lewenstein, and Antonio Acín
We study quantum entanglement distribution on networks with full-rank
bi-partite mixed states linking qubits on nodes. In particular, we use
entanglement swapping and purification to partially entangle widely
separated nodes. The simplest method consists of performing entanglement
swappings along the shortest chain of links connecting the two nodes.
However, we show that this method may be improved upon by choosing a
protocol with a specific ordering of swappings and purifications. A
priori, the design that produces optimal improvement is not clear.
However, we parameterize the choices and find that the optimal values
depend strongly on the desired measure of improvement. As an initial
application, we apply the new improved protocols to the Erd\"os--R\'enyi
network and obtain results including low density limits and an exact
calculation of the average entanglement gained at the critical point.
back to QIC online Front page
|
