Vol.10
No.5&6 May 1, 2010
Research Articles:
Upper bounds on the noise threshold for faulttolerant quantum computing
(pp03610376)
J.
Kempe, O. Regev, F. Unger, and R. de Wolf
We prove new upper bounds on the tolerable level of noise in a quantum
circuit. We consider circuits consisting of unitary $k$qubit gates each
of whose input wires is subject to depolarizing noise of strength $p$,
as well as arbitrary onequbit gates that are essentially noisefree. We
assume that the output of the circuit is the result of measuring some
designated qubit in the final state. Our main result is that for
$p>1\Theta(1/\sqrt{k})$, the output of any such circuit of large enough
depth is essentially independent of its input, thereby making the
circuit useless. For the important special case of $k=2$, our bound is
$p>35.7\%$. Moreover, if the only allowed gate on more than one qubit is
the twoqubit CNOT gate, then our bound becomes $29.3\%$. These bounds
on $p$ are numerically better than previous bounds, yet are incomparable
because of the somewhat different circuit model that we are using. Our
main technique is the use of a Pauli basis decomposition, in which the
effects of depolarizing noise are very easy to describe.
Threeparty entanglement in tripartite teleportation scheme through
noisy channels
(pp03770397)
E.
Jung, M.R. Hwang, D. Park, and S. Tamaryan
In this paper we have tried to interpret the physical role of
threetangle and $\pi$tangle in real physical information processes.
For the model calculation we adopt the tripartite teleportation scheme
through various noisy channels. The three parties consist of sender,
accomplice and receiver. It is shown that the $\pi$tangles for the X
and Znoisy channels vanish at the limit $\kappa t \rightarrow \infty$,
where $\kappa t$ is a decoherence parameter introduced in the master
equation in the Lindblad form. At this limit the maximum fidelity of the
receiver's state reduces to the classical limit $2/3$. However, this
nice feature is not maintained for the Y and isotropynoise channels.
For the Ynoise channel the $\pi$tangle vanishes when $0.61 \leq \kappa
t$. At $\kappa t = 0.61$ the maximum fidelity becomes $0.57$, which is
much less than the classical limit. Similar phenomenon occurs for the
isotropic noise channel. We also compute analytically the threetangles
for the X and Znoise channels. The remarkable fact is that the
threetangle for the Znoise channel coincides exactly with the
corresponding $\pi$tangle. In the Xnoise channel the threetangle
vanishes when $0.10 \leq \kappa t$. At $\kappa t = 0.10$ the fidelity of
the receiver's state can reduce to the classical limit provided that the
accomplice performs the measurement appropriately. However, the maximum
fidelity becomes $8/9$, which is much larger than the classical limit.
Since the Y and isotropynoise channels are rank$8$ mixed states,
their threetangles are not computed explicitly in this paper. Instead,
their upper bounds are derived by making use of the analytic formulas of
the threetangle for other noisy channels. Our analysis strongly
suggests that different tripartite entanglement measure is needed whose
value is between threetangle and $\pi$tangle.
Teleportation via maximally and nonmaximally entangled mixed states
(pp03980419)
S.
Adhikari, A.S. Majumdar, S. Roy, B. Ghosh, and N. Nayak
We study the efficiency of twoqubit mixed entangled states as resources
for quantum teleportation. We first consider two maximally entangled
mixed states, viz., the Werner state\cite{werner}, and a class of states
introduced by Munro {\it et al.} \cite{munro}. We show that the Werner
state when used as teleportation channel, gives rise to better average
teleportation fidelity compared to the latter class of states for any
finite value of mixedness. We then introduce a nonmaximally entangled
mixed state obtained as a convex combination of a twoqubit entangled
mixed state and a twoqubit separable mixed state. It is shown that such
a teleportation channel can outperform another nonmaximally entangled
channel, viz., the Werner derivative for a certain range of mixedness.
Further, there exists a range of parameter values where the former state
satisfies a BellCHSH type inequality and still performs better as a
teleportation channel compared to the Werner derivative even though the
latter violates the inequality.
Efficient circuits for quantum walks
(pp04200434)
C.F.
Chiang, D. Nagaj, and P. Wocjan
We present an efficient general method for realizing a quantum walk
operator corresponding to an arbitrary sparse classical random walk. Our
approach is based on Grover and Rudolph's method for preparing coherent
versions of efficiently integrable probability distributions \cite{GroverRudolph}.
This method is intended for use in quantum walk algorithms with
polynomial speedups, whose complexity is usually measured in terms of
how many times we have to apply a step of a quantum walk \cite{Szegedy},
compared to the number of necessary classical Markov chain steps. We
consider a finer notion of complexity including the number of elementary
gates it takes to implement each step of the quantum walk with some
desired accuracy. The difference in complexity for various
implementation approaches is that our method scales linearly in the
sparsity parameter and polylogarithmically with the inverse of the
desired precision. The best previously known general methods either
scale quadratically in the sparsity parameter, or polynomially in the
inverse precision. Our approach is especially relevant for implementing
quantum walks corresponding to classical random walks like those used in
the classical algorithms for approximating permanents \cite{Vigoda,
Vazirani} and sampling from binary contingency tables \cite{Stefankovi}.
In those algorithms, the sparsity parameter grows with the problem size,
while maintaining high precision is required.
On quantumclassical equivalence for composed communication problems
(pp04350455)
A.A.
Sherstov
An open problem in communication complexity proposed by several authors
is to prove that for every Boolean function $f,$ the task of computing $f(x\wedge
y)$ has polynomially related classical and quantum boundederror
complexities. We solve a variant of this question. For every $f,$ we
prove that the task of computing, on input \mbox{$x$ and $y,$}
\emph{both} of the quantities $f(x\wedge y)$ and $f(x\vee y)$ has
polynomially related classical and quantum boundederror complexities.
We further show that the quantum boundederror complexity is
polynomially related to the classical deterministic complexity and the
block sensitivity of $f.$ This result holds regardless of prior
entanglement.
Threshold error rates for the toric and planar codes
(pp04560469)
D.S.
Wang, A.G. Fowler, A.M. Stephens, and L.C.L. Hollenberg
The planar code scheme for quantum computation features a 2d array of
nearestneighbor coupled qubits yet claims a threshold error rate
approaching 1\%. This result was obtained for the toric code, from which
the planar code is derived, and surpasses all other known codes
restricted to 2d nearestneighbor architectures by several orders of
magnitude. We describe in detail an error correction procedure for the
toric and planar codes, which is based on polynomialtime graph matching
techniques and is efficiently implementable as the classical
feedforward processing step in a real quantum computer. By applying one
and two qubit depolarizing errors of equal probability $p$, we determine
the threshold error rates for the two codes (differing only in their
boundary conditions) for both ideal and nonideal syndrome extraction
scenarios. We verify that the toric code has an asymptotic threshold of
$p_{\textrm{th}} = 15.5\%$ under ideal syndrome extraction, and $p_{\textrm{th}}
= 7.8 \times 10^{3}$ for the nonideal case, in agreement with
\cite{Raus07d}. Simulations of the planar code indicate that the
threshold is close to that of the toric code.
Permutational quantum computing
(pp04700497)
S.P.
Jordan
In topological quantum computation the geometric details of a particle
trajectory are irrelevant; only the topology matters. Taking this one
step further, we consider a model of computation that disregards even
the topology of the particle trajectory, and computes by permuting
particles. Whereas topological quantum computation requires anyons,
permutational quantum computation can be performed with ordinary
spin1/2 particles, using a variant of the spinnetwork scheme of
Marzuoli and Rasetti. We do not know whether permutational computation
is universal. It may represent a new complexity class within BQP.
Nevertheless, permutational quantum computers can in polynomial time
approximate matrix elements of certain irreducible representations of
the symmetric group and approximate certain transition amplitudes from
the PonzanoRegge spin foam model of quantum gravity. No polynomial time
classical algorithms for these problems are known.
Quantum Fisher information for superpositions of spin states
(pp04980508)
H.N.
Xiong, J. Ma, W.F. Liu, and X. Wang
In terms of quantum Fisher information, a quantity $\chi^{2}$ was
introduced by Pezz\'{e} and Smerzi, which is a multiparticle
entanglement measure, and provides a necessary and sufficient condition
for subshotnoise phase estimation sensitivity. We derive a general
expression of $\chi ^{2}$ for arbitrary symmetric multiqubit states with
nonzero mean spins. It is shown that the entangled symmetric states are
useful for phase sensitivity beyond the shotnoise limit. Using the
expression, we explicitly examine a series of superpositions of spin
states. We find that the superpositions of Dicke states perform better
than Dicke states themselves in phase esitmation. Although the spin
coherent states themselves only have a shotnoise limit phase
sensitivity, their superpositions may reach the Heisenberg limit.
One dimensional quantum walks with memory
(pp05090524)
M.
Mc Gettrick
We investigate the quantum versions of a onedimensional random walk,
whose corresponding Markov Chain is of order 2. This corresponds to the
walk having a memory of one previous step. We derive the amplitudes and
probabilities for these walks, and point out how they differ from both
classical random walks, and quantum walks without memory.
PPT classifiable families of bipartite states
(pp05350538)
F.E.S.
Steinhoff and M.C. de Oliveira
We construct a family of bipartite states of arbitrary dimension whose
eigenvalues of the partially transposed matrix can be inferred directly
from the block structure of the global density matrix. We identify from
this several subfamilies in which the PPT criterion is both necessary
and sufficient. A sufficient criterion of separability is obtained,
which is fundamental for the discussion. We show how several examples of
states known to be classifiable by the PPT criterion indeed belong to
this general set. Possible uses of these states in numerical analysis of
entanglement and in the search of PPT bound entangled states are briefly
discussed.
back to QIC online Front page
