*
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**