Vol.12
No.5&6, May 1, 2012
Research Articles:
Constantoptimized quantum circuits for modular multiplication and
exponentiation
(pp03610394)
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
numberfactoring 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
bottomup fashion, starting with most convenient $C$ values. When
zeroinitialized ancilla registers are available, we reduce the search
for compact circuits to a shortestpath problem. Some of our
modularmultiplication circuits are asymptotically smaller than previous
constructions, but worstcase bounds and average sizes remain $\Theta(n^2)$.
In the context of modular exponentiation, we offer several
constantfactor improvements, as well as an improvement by a constant
additive term that is significant for fewqubit circuits arising in
ongoing laboratory experiments with Shor's algorithm.
Encryption with weakly random keys using quantum ciphertext
(pp03950403)
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{McInnesPinkasImpossibilityofPrivate1991} 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 McInnesPinkas 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/minentropy is
nonzero). 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
(pp04040431)
D.
Markus Appleby, Ingemar Bengtsson, Stephen Brierley, Markus Grassl,
David Gross, and JanAke Larsson
We show that the Clifford groupthe normaliser of the WeylHeisenberg
groupcan be represented by monomial phasepermutation 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
(pp04320441)
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 minentropy 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 minentropy by using the
quantum asymptotic equipartition property (QAEP). We provide a short
proof of the QAEP and therefore obtain a selfcontained proof of the DPI
for the von Neumann entropy.
Optimal estimation of quantum processes using incomplete
information: variational quantum process tomography
(pp04420447)
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[quantph] \cite{VQT}.
Long distance twoparty quantum crypto made simple
(pp04480460)
Iordanis
Kerenidis and Stephanie Wehner
Any twoparty 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 classicalwitness quantum
MerlinArthur proof systems
(pp04610471)
Stephen
P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura
This paper proves that classicalwitness quantum MerlinArthur 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
(pp04720489)
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 multistate correlations in
relation to the Holevo quantity.
Semilosstolerant strong coin
flipping protocol using EPR pairs
(pp04900501)
JiaJun
Ma, FenZhuo Guo, Qian Yang, YanBing Li, and QiaoYan 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 semilosstolerant. 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
losstolerant 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 qubitbased
losstolerant SCF protocols, we introduce the EPR pair to keep our
protocol losstolerant 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
losstolerant 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 bipartite
fullrank mixed states
(pp05020534)
G John
Lapeyre Jr., Sébastien Perseguers, Maciej Lewenstein, and Antonio Acín
We study quantum entanglement distribution on networks with fullrank
bipartite 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\"osR\'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
