Vol.15
No.5&6,
April 1, 2015
Research Articles:
The Trotter step size required for accurate quantum
simulation of quantum chemistry 361
(pp0361-0384)
David
Poulin, M. B. Hastings, D. Wecker, N. Wiebe, Andrew C. Doberty, and M.
Troyer
The simulation of molecules is a widely anticipated application of
quantum computers. However, recent studies \cite{WBCH13a,HWBT14a} have
cast a shadow on this hope by revealing that the complexity in gate
count of such simulations increases with the number of spin orbitals $N$
as $N^8$, which becomes prohibitive even for molecules of modest size
$N\sim 100$. This study was partly based on a scaling analysis of the
Trotter step required for an ensemble of random artificial molecules.
Here, we revisit this analysis and find instead that the scaling is
closer to $N^6$ in worst case for real model molecules we have studied,
indicating that the random ensemble fails to accurately capture the
statistical properties of real-world molecules. Actual scaling may be
significantly better than this due to averaging effects. We then present
an alternative simulation scheme and show that it can sometimes
outperform existing schemes, but that this possibility depends crucially
on the details of the simulated molecule. We obtain further improvements
using a version of the coalescing scheme of \cite{WBCH13a}; this scheme
is based on using different Trotter steps for different terms. The
method we use to bound the complexity of simulating a given molecule is
efficient, in contrast to the approach of \cite{WBCH13a,HWBT14a} which
relied on exponentially costly classical exact simulation.
Some classes of concatenated quantum codes:
constructions and lower bounds
(pp0385-0405)
Hachiro
Fujita
In classical coding theory code
concatenation is successfully used to construct good error-correcting
codes and most of the asymptotically good codes known so far are based
on concatenation. In this paper we present some classes of
asymptotically good concatenated quantum codes, which are a quantum
analogue of classical concatenated codes, and derive lower bounds on the
minimum distance and the rate of the codes. Our bounds improve on the
best lower bound of Ashikhmin--Litsyn--Tsfasman and Matsumoto for rates
smaller than about one half. We also give a polynomial-time decoding
algorithm for the codes that can decode up to one fourth of the lower
bound on the minimum distance of the codes.
Limit theorems of a 3-state quantum walk and its
application for discrete uniform measures
(pp0406-0418)
Takuya
Machida
We present two long-time limit theorems of a 3-state quantum walk on
the line when the walker starts from the origin. One is a limit measure
which is obtained from the probability distribution of the walk at a
long-time limit, and the other is a convergence in distribution for the
walker's position in a rescaled space by time. In addition, as an
application of the walk, we obtain discrete uniform limit measures from
the 3-state walk with a delocalized initial state.
High performance information reconciliation for
QKD with CASCADE
(pp0419-0434)
Thomas
Brochmann Pedersen and Mustafa Toyran
It is widely accepted in the quantum cryptography community
that interactive information reconciliation protocols, such as
\cascade{}, are inefficient due to the communication overhead. Instead,
non-interactive information reconciliation protocols based on i.e. LDPC
codes or, more recently, polar codes have been proposed. In this work,
we argue that interactive protocols should be taken into consideration
in modern quantum key distribution systems. In particular, we
demonstrate how to improve the performance of \cascade{} by proper
implementation and use. Our implementation of \cascade{} reaches a
throughput above 80~Mbps under realistic conditions. This is more than
twice the throughput previously demonstrated in any information
reconciliation protocol.
Exact quantum algorithms have advantage for almost
all Boolean functions
(pp0435-0452)
Andris
Ambainis, Jozef Gruska, and Shenggen Zheng
It has been proved that almost all $n$-bit Boolean functions have
exact classical query complexity} $n$. However, the situation seemed
to be very different when we deal with exact quantum query
complexity. In this paper, we prove that almost all $n$-bit Boolean
functions can be computed by an exact quantum algorithm with less than
$n$ queries. More exactly, we prove that $\mbox{AND}_n$ is the only
$n$-bit Boolean function, up to isomorphism, that requires $n$ queries.
Demystifying the information reconciliation protocol
cascade
(pp0453-0477)
Jesus
Martinez-Mateo, Christoph Pacher, Momtchil Peev, Alex Ciurana, and
Vicente Martin
\Cascade is an information reconciliation protocol proposed in the
context of secret key agreement in quantum cryptography. This protocol
allows removing discrepancies in two partially correlated sequences that
belong to distant parties, connected through a public noiseless channel.
It is highly interactive, thus requiring a large number of channel
communications between the parties to proceed and, although its
efficiency is not optimal, it has become the de-facto standard for
practical implementations of information reconciliation in quantum key
distribution. The aim of this work is to analyze the performance of
\Cascade, to discuss its strengths, weaknesses and optimization
possibilities, comparing with some of the modified versions that have
been proposed in the literature. When looking at all design trade-offs,
a new view emerges that allows to put forward a number of guidelines and
propose near optimal parameters for the practical implementation of
\Cascade improving performance significantly in comparison with all
previous proposals.
Indecomposability of entanglement witnesses
(pp0478-0488)
Xiao-Fei Qi
and Jin-Chuan Hou
We present a way to construct indecomposable entanglement witnesses
from any permutation $\pi$ with $\pi^2\not=$id for any finite
dimensional bipartite systems. Some new bounded entangled states are
also found, which can be detected by such witnesses while cannot be
distinguished by PPT criterion, realignment criterion, etc.
Analysis of circuit imperfections in BosonSampling
(pp0489-0512)
Anthony
Leverrier, Raul Garcia-Patron
BosonSampling is a problem where a quantum computer offers a
provable speedup over classical computers. Its main feature is that it
can be solved with current linear optics technology, without the need
for a full quantum computer. In this work, we investigate whether an
experimentally realistic BosonSampler can really solve BosonSampling
without any fault-tolerance mechanism. More precisely, we study how the
unavoidable errors linked to an imperfect calibration of the optical
elements affect the final result of the computation. We show that the
fidelity of each optical element must be at least $1 - O(1/n^2)$, where
$n$ refers to the number of single photons in the scheme. Such a
requirement seems to be achievable with state-of-the-art equipment.
Locally restricted measurements on a multipartite
quantum system: data hiding is generic
(pp0513-0540)
Guillaume
Aubrun and Cecilia Lancien
We study the distinguishability norms associated to families of
locally restricted POVMs on multipartite systems. These norms
(introduced by Matthews, Wehner and Winter) quantify how quantum
measurements, subject to locality constraints, perform in the task of
discriminating two multipartite quantum states. We mainly address the
following question regarding the behaviour of these distinguishability
norms in the high-dimensional regime: On a bipartite space, what are the
relative strengths of standard classes of locally restricted
measurements? We show that the class of PPT measurements typically
performs almost as well as the class of all measurements whereas
restricting to local measurements and classical communication, or even
just to separable measurements, implies a substantial loss. We also
provide examples of state pairs which can be perfectly distinguished by
local measurements if (one-way) classical communication is allowed
between the parties, but very poorly without it. Finally, we study how
many POVMs are needed to distinguish almost perfectly any pair of states
on ${\mathbf{C}}^d$, showing that the answer is $\exp(\Theta(d^2))$.
back to QIC online Front page
|