Research Articles:
A comparative code study for quantum
fault tolerance
(pp0541-0572)
A.W.
Cross, D.P. DiVincenzo, B.M. Terhal
We study a comprehensive list of quantum codes as candidates for codes
used at the physical level in a fault-tolerant code architecture. Using
the Aliferis-Gottesman-Preskill (AGP) ex-Rec method we calculate the
pseudo-threshold for these codes against depolarizing noise at various
levels of overhead. We estimate the logical noise rate as a function of
overhead at a physical error rate of $p_0=1 \times 10^{-4}$. The Bacon-Shor
codes and the Golay code are the best performers in our study.
Quantum multiplexing with optical
coherent states
(pp0573-0593)
J.C.
Garcia-Escartin and P. Chamorro-Posada
In this paper, we propose a novel quantum multiple access technique
based on optical coherent states. The information of several coherent
state optical qubits is combined into a single qudit, which is the
superposition of almost orthogonal coherent states. The original
information is encoded into a new Hilbert space with the help of a
quantum multiplexer (QMUX) and then recovered at the other end with a
quantum demultiplexer (QDEMUX). We introduce the optical tools that
complete the coherence state quantum computation model and give the
desired circuits. The proposed system can admit a number of users above
the optimal limit at the cost of a degradation of the transmitted data.
In this and some other aspects, it can be regarded as a quantum analogue
of classical Code Division Multiple Access techniques.
The decreasing
property of relative entropy and the strong superadditivity of quantum
channels
(pp0594-0609)
G.G.
Amosov and S. Mancini
We argue that a fundamental (conjectured) property of memoryless quantum
channels, namely the strong superadditivity, is intimately related to
the decreasing property of the quantum relative entropy. Using the
latter we first give, for a wide class of input states, an estimation of
the output entropy for phase damping channels and some Weyl quantum
channels. Then we prove, without any input restriction, the strong
superadditivity for several quantum channels, including depolarizing
quantum channels, quantum-classical channels and quantum erasure
channels.
An O(m^2)-depth
quantum algorithm for the elliptic curve discrete logarithm problem over
GF(2^m)
(pp0610-0621)
D.
Maslov, J. Mathew, D. Cheung, and D.K. Pradhan
We consider a quantum polynomial-time algorithm which solves the
discrete logarithm problem for points on elliptic curves over $GF(2^m)$.
We improve over earlier algorithms by constructing an efficient circuit
for multiplying elements of binary finite fields and by representing
elliptic curve points using a technique based on projective coordinates.
The depth of our proposed implementation, executable in the Linear
Nearest Neighbor (LNN) architecture, is $O(m^2)$, which is an
improvement over the previous bound of $O(m^3)$ derived assuming no
architectural restrictions.
An entropy
inequality
(pp0622-0627)
M.
Hellmund and A. Uhlmann
Let $S(\rho)=-\Tr (\rho\log\rho)$ be the von Neumann entropy of an
$N$-dimensional quantum state $\rho$ and $e_2(\rho)$ the second
elementary symmetric polynomial of the eigenvalues of $\rho$. We prove
the inequality S(\rho) \;\le \; c(N) \; \sqrt{e_2(\rho)} where $c(N)=\log(N)
\, \sqrt{\frac{2N}{N-1}}$. This generalizes an inequality given by Fuchs
and Graaf~\cite{fuchsgraaf} for the case of one qubit, i.e., $N=2$.
Equality is achieved if and only if $\rho$ is either a pure or the
maximally mixed state. This inequality delivers new bounds for
quantities of interest in quantum information theory, such as upper
bounds for the minimum output entropy and the entanglement of formation
as well as a lower bound for the Holevo channel capacity.
Quantum search of
partially ordered sets
(pp0628-0647)
A.
Montanaro
We investigate the generalisation of quantum search of unstructured and
totally ordered sets to search of partially ordered sets (posets). Two
models for poset search are considered. In both models, we show that
quantum algorithms can achieve at most a quadratic improvement in query
complexity over classical algorithms, up to logarithmic factors; we also
give quantum algorithms that almost achieve this optimal reduction in
complexity. In one model, we give an improved quantum algorithm for
searching forest-like posets; in the other, we give an optimal $O(\sqrt{m})$-query
quantum algorithm for searching posets derived from $m \times m$ arrays
sorted by rows and columns. This leads to a quantum algorithm that finds
the intersection of two sorted lists of $n$ integers in $O(\sqrt{n})$
time, which is optimal.
Entanglement-resistant two-Prover interactive proof systems and
non-adaptive PIRs
(pp0648-0656)
R.
Cleve, D. Gavinsky, and R. Jain
We show that every language in $\np$ is recognized by a two-prover
interactive proof system with the following properties. The proof system
is entanglement-resistant (i.e., its soundness is robust against provers
who have prior shared entanglement), it has one round of interaction,
the provers' answers are single bits, and the completeness-soundness gap
is constant (formally, $\np\subseteq \xmips_{1-\varepsilon,1/2+\varepsilon}\mo[2]$,
for any~$\varepsilon$ such that $0 < \varepsilon < 1/4$). Our result is
based on the ``oracularizing" property of a particular private
information retrieval scheme (PIR), and it suggests that investigating
related properties of other PIRs might bear further fruit.
Correlation loss
and multipartite entanglement across a black hole horizon
(pp0657-0665)
G.
Adesso and I. Fuentes-Schuller
We investigate the Hawking effect on entangled fields. By considering a
scalar field which is in a two-mode squeezed state from the point of
view of freely falling (Kruskal) observers crossing the horizon of a
Schwarzschild black hole, we study the degradation of quantum and
classical correlations in the state from the perspective of physical
(Schwarzschild) observers confined outside the horizon. Due to monogamy
constraints on the entanglement distribution, we show that the lost
bipartite entanglement is recovered as multipartite entanglement among
modes inside and outside the horizon. In the limit of a small-mass black
hole, no bipartite entanglement is detected outside the horizon, while
the genuine multipartite entanglement interlinking the inner and outer
regions grows infinitely.
Latency in local,
two-dimensional, fault-tolerant quantum computing
(pp0666-0682)
F.M.
Spedalieri and V.P. Roychowdhury
We analyze the latency of fault-tolerant quantum computing based on the
9-qubit Bacon-Shor code using a local, two-dimensional architecture. We
embed the data qubits in a 7 by 7 array of physical qubits, where the
extra qubits are used for ancilla preparation and qubit transportation
by means of a SWAP chain. The latency is reduced with respect to a
similar implementation using Steane's 7-qubit code~\cite{svore2007a}.
Furthermore, the error threshold is also improved to $2.02 \times
10^{-5}$, when memory errors are taken to be one tenth of the gate error
rates.
Practical random
number generation protocol for entanglement-based quantum key
distribution
(pp0683-0692)
G.B.
Xavier, T. Ferreira da Silva, G. Vilela de Faria, G.P. Temporao, and
J.P. von der Weid
A simple protocol which takes advantage of the inherent random times of
detections in single photon counting modules is presented for random
active basis choices when using entanglement-based protocols for Quantum
Key Distribution (QKD). It may also be applicable to the BB84 protocol
in certain cases. The scheme presented uses the single photon detectors
already present on a QKD setup, working on the same rate as the system
is capable of detecting, and is, therefore, not limited by the output
rates of quantum random number generators. This protocol only requires
small hardware modifications making it an attractive solution. We
perform a proof-of-principle experiment employing a spontaneous
parametric down-conversion process in a $\chi^{(2)}$ non-linear crystal
to demonstrate the feasibility of our scheme, and show that the
generated sequence passes randomness tests.
Auto-adaptive
interval selection for quantum key distribution
(pp0693-0700)
J.
Han and X. Qian
Key reconciliation plays an important role in quantum key distribution,
as well as shared bit string distillation. To distill efficiently the
final key a so-called Winnow protocol has been proposed. However, how to
choose the interval length of the shared string to maximize the Winnow
efficiency is difficult in practical program processing. Because the
interval choice remains an open problem the key rate of the Winnow
protocol is not as high as the one calculated in theory. Consequently,
the Winnow protocol is difficult to efficiently employ in application.
In this paper we first analytically investigate the dependence of the
interval length on the error distribution and the code. Then an
auto-adaptive interval selection algorithm is proposed. In addition, new
characteristics of the protocol are investigated.
Classical
approximation schemes for the ground-state energy of quantum and
classical Ising spin Hamiltonians on planar graphs
(pp0701-0720)
N.
Bansal, S. Bravyi, and B.M. Terhal
We describe a classical approximation algorithm for evaluating the
ground state energy of the classical Ising Hamiltonian with linear terms
on an arbitrary planar graph. The running time of the algorithm grows
linearly with the number of spins and exponentially with $1/\epsilon$,
where $\epsilon$ is the worst-case relative error. This result contrasts
the well known fact that exact computation of the ground state energy
for the two-dimensional Ising spin glass model is NP-hard. We also
present a classical approximation algorithm for the quantum Local
Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar
graph {\em with bounded degree} which is known to be a QMA-complete
problem. Using a different technique we find a classical approximation
algorithm for the quantum Ising spin glass problem on the simplest
planar graph with unbounded degree, the star graph.
