QIC Abstracts

 Vol.8 No.3&4 March 1, 2008

Research Articles:
Accuracy threshold for postselected quantum computation (pp0181-0244)
P. Aliferis, D. Gottesman, and J. Preskill
We prove an accuracy threshold theorem for fault-tolerant quantum computation based on error detection and postselection. Our proof provides a rigorous foundation for the scheme suggested by Knill, in which preparation circuits for ancilla states are protected by a concatenated error-detecting code and the preparation is aborted if an error is detected. The proof applies to independent stochastic noise but (in contrast to proofs of the quantum accuracy threshold theorem based on concatenated error-correcting codes) not to strongly-correlated adversarial noise. Our rigorously established lower bound on the accuracy threshold, $1.04\times 10^{-3}$, is well below Knill's numerical estimates.

Entanglement and separability of quantum harmonic oscillator systems at finite temperature (pp0245-0262)           J. Anders and A. Winter
In the present paper we study the entanglement properties of thermal (a.k.a.~\emph{Gibbs}) states of quantum harmonic oscillator systems as functions of the Hamiltonian and the temperature. We prove the physical intuition that at sufficiently high temperatures the thermal state becomes fully separable and we deduce bounds on the critical temperature at which this happens. We show that the bound becomes tight for a wide class of Hamiltonians with sufficient translation symmetry. We find, that at the crossover the thermal energy is of the order of the energy of the strongest normal mode of the system and quantify the degree of entanglement below the critical temperature. Finally, we discuss the example of a ring topology in detail and compare our results with previous work in an entanglement-phase diagram.

The LU-LC conjecture, diagonal local operations and quadratic forms over GF(2) (pp0263-0281)
D. Gross and M. Van den Nest
We report progress on the LU-LC conjecture---an open problem in the context of entanglement in stabilizer states (or graph states). This conjecture states that every two stabilizer states which are related by a local unitary operation, must also be related by a local operation within the Clifford group. The contribution of this paper is a reduction of the LU-LC conjecture to a simpler problem---which, however, remains to date unsolved. As our main result, we show that, if the LU-LC conjecture could be proved for the restricted case of \emph{diagonal} local unitary operations, then the conjecture is correct in its totality. Furthermore, the reduced version of the problem, involving such diagonal local operations, is mapped to questions regarding quadratic forms over the finite field GF(2). Finally, we prove that correctness of the LU-LC conjecture for stabilizer states implies a similar result for the more general case of stabilizer codes.

Optimal synthesis of linear reversible circuits (pp0282-0294)
K.N. Patel, I.L. Markov, and J.P. Hayes
In this paper we consider circuit synthesis for $n$-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with $O\left(n^2\right)$ gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as $O\left(n^2/\log\, n\right)$ gates.

Entanglement of formation of rotationally symmetric states (pp0295-0310)
K.K. Manne and C.M. Caves
Computing the entanglement of formation of a bipartite state is generally difficult, but special symmetries of a state can simplify the problem. For instance, this allows one to determine the entanglement of formation of Werner states and isotropic states. We consider a slightly more general class of states, rotationally symmetric states, also known as SU(2)-invariant states. These states are invariant under global rotations of both subsystems, and one can examine entanglement in cases where the subsystems have different dimensions. We derive an analytic expression for the entanglement of formation of rotationally symmetric states of a spin-$j$ particle and a spin-${1\over2}$ particle. We also give expressions for the I-concurrence, I-tangle, and convex-roof-extended negativity.

Entanglement purification with two-way classical communication (pp0311-0329)
A.W. Leung and P.W. Shor
We present an entanglement purification protocol for Bell-diagonal mixed states and show that this protocol has improved yields over the recurrence methods and the method proposed by Maneva-Smolin. We then generalize this protocol to a family, and show that this family is also a generalization of the recurrence method, the modified recurrence method and the method proposed by Maneva-Smolin. We show that the yields of these protocols on the Werner state $\rho_F$ are higher than those of universal hashing for F less than 0.99999 and as F goes to 1.

Universal fault tolerant quantum computation on bilinear nearest neighbor arrays (pp0330-0344)
A.M. Stephens, A.G. Fowler, and L.C.L. Hollenberg
Assuming an array that consists of two parallel lines of qubits and that permits only nearest neighbor interactions, we construct physical and logical circuitry to enable universal fault tolerant quantum computation under the $[[7,1,3]]$ quantum code. A rigorous lower bound to the fault tolerant threshold for this array is determined in a number of physical settings. Adversarial memory errors, two-qubit gate errors and readout errors are included in our analysis. In the setting where the physical memory failure rate is equal to one-tenth of the physical gate error rate, the physical readout error rate is equal to the physical gate error rate, and the duration of physical readout is ten times the duration of a physical gate, we obtain a lower bound to the asymptotic threshold of $1.96\times10^{-6}$.

Quantum measurements for hidden subgroup problems with optimal sample complexity (pp0345-0358)
M. Hayashi, A. Kawachi, and H. Kobayashi
One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case \REVISE{where the candidate nontrivial subgroups} have the same prime order $p$, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.

Book Review:
On “xxxxx (authored by )” (pp0359-0360)
G.J. Milburn

back to QIC online Front page