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