Vol.10
No.5&6 May 1, 2010
Research Articles:
Upper bounds on the noise threshold for fault-tolerant quantum computing
(pp0361-0376)
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 one-qubit gates that are essentially noise-free. 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 two-qubit 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.
Three-party entanglement in tripartite teleportation scheme through
noisy channels
(pp0377-0397)
E.
Jung, M.R. Hwang, D. Park, and S. Tamaryan
In this paper we have tried to interpret the physical role of
three-tangle 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 Z-noisy 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 isotropy-noise channels.
For the Y-noise 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 three-tangles
for the X- and Z-noise channels. The remarkable fact is that the
three-tangle for the Z-noise channel coincides exactly with the
corresponding $\pi$-tangle. In the X-noise channel the three-tangle
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 isotropy-noise channels are rank-$8$ mixed states,
their three-tangles are not computed explicitly in this paper. Instead,
their upper bounds are derived by making use of the analytic formulas of
the three-tangle for other noisy channels. Our analysis strongly
suggests that different tripartite entanglement measure is needed whose
value is between three-tangle and $\pi$-tangle.
Teleportation via maximally and non-maximally entangled mixed states
(pp0398-0419)
S.
Adhikari, A.S. Majumdar, S. Roy, B. Ghosh, and N. Nayak
We study the efficiency of two-qubit 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 non-maximally entangled
mixed state obtained as a convex combination of a two-qubit entangled
mixed state and a two-qubit separable mixed state. It is shown that such
a teleportation channel can outperform another non-maximally 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 Bell-CHSH 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
(pp0420-0434)
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 poly-logarithmically 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 quantum-classical equivalence for composed communication problems
(pp0435-0455)
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 bounded-error
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 bounded-error complexities.
We further show that the quantum bounded-error 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
(pp0456-0469)
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
nearest-neighbor 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 nearest-neighbor architectures by several orders of
magnitude. We describe in detail an error correction procedure for the
toric and planar codes, which is based on polynomial-time graph matching
techniques and is efficiently implementable as the classical
feed-forward 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 non-ideal 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 non-ideal 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
(pp0470-0497)
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
spin-1/2 particles, using a variant of the spin-network 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 Ponzano-Regge spin foam model of quantum gravity. No polynomial time
classical algorithms for these problems are known.
Quantum Fisher information for superpositions of spin states
(pp0498-0508)
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 sub-shot-noise 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 shot-noise 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 shot-noise limit phase
sensitivity, their superpositions may reach the Heisenberg limit.
One dimensional quantum walks with memory
(pp0509-0524)
M.
Mc Gettrick
We investigate the quantum versions of a one-dimensional 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
(pp0535-0538)
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
|