Vol.6 No.3
May 1, 2006
Research Articles:
A flowmap model for analyzing
pseudothresholds in faulttolerant quantum computing
(pp193212)
K.M. Svore, A.W. Cross, I.L. Chuang, and
A.V. Aho
An arbitrarily reliable quantum computer can be
efficiently constructed from noisy components using a recursive
simulation procedure, provided that those components fail with
probability less than the faulttolerance threshold. Recent estimates of
the threshold are near some experimentally achieved gate fidelities.
However, the landscape of threshold estimates includes pseudothresholds,
threshold estimates based on a subset of components and a low level of
the recursion. In this paper, we observe that
pseudothresholds are a generic phenomenon in faulttolerant computation.
We define pseudothresholds and present classical and quantum
faulttolerant circuits exhibiting pseudothresholds that differ by a
factor of $4$ from faulttolerance thresholds for typical relationships
between component failure rates. We develop tools for visualizing how
reliability is influenced by recursive simulation in order to determine
the asymptotic threshold. Finally, we conjecture that refinements of
these methods may establish upper bounds on the faulttolerance
threshold for particular codes and noise models.
A geometric approach to
quantum circuit lower bounds
(pp213262)
M.A. Nielsen
What is the minimal size quantum circuit required to
exactly implement a specified nqubit unitary operation, U, without the
use of ancilla qubits? We show that a lower bound on the minimal size is
provided by the length of the minimal geodesic between U and the
identity, I, where length is defined by a suitable Finsler metric on the
manifold SU(2^n). The geodesic curves on these manifolds have the
striking property that once an initial position and velocity are set,
the remainder of the geodesic is completely determined by a second order
differential equation known as the geodesic equation. This is in
contrast with the usual case in circuit design, either classical or
quantum, where being given part of an optimal circuit does not obviously
assist in the design of the rest of the circuit. Geodesic analysis thus
offers a potentially powerful approach to the problem of proving quantum
circuit lower bounds. In this paper we construct several Finsler metrics
whose minimal length geodesics provide lower bounds on quantum circuit
size. For each Finsler metric we give a procedure to compute the
corresponding geodesic equation. We also construct a large class of
solutions to the geodesic equation, which we call \emph{Pauli
geodesics}, since they arise from isometries generated by the Pauli
group. For any unitary U diagonal in the computational basis, we show
that: (a) provided the minimal length geodesic is unique, it must be a
Pauli geodesic; (b) finding the length of the minimal Pauli geodesic
passing from I to U is equivalent to solving an exponential size
instance of the closest vector in a lattice problem (CVP); and (c) all
but a doubly exponentially small fraction of such unitaries have minimal
Pauli geodesics of exponential length.
Mixing and decoherence in quantum walks on cycles
(pp263276)
L. Fedichkin,
D. Solenov, and C. Tamon
We prove analytical results showing that decoherence can
be useful for mixing time in a continuoustime quantum walk on finite
cycles. This complements the numerical observations by Kendon and
Tregenna (Physical Review A 67 (2003), 042315) of a
similar phenomenon for discretetime quantum walks. Our analytical
treatment of continuoustime quantum walks includes a continuous
monitoring of all vertices that induces the decoherence process. We
identify the dynamics of the probability distribution and observe how
mixing times undergo the transition from quantum to classical behavior
as our decoherence parameter grows from zero to infinity. Our results
show that, for small rates of decoherence, the mixing time improves
linearly with decoherence, whereas for large rates of decoherence, the
mixing time deteriorates linearly towards the classical limit. In the
middle region of decoherence rates, our numerical data confirms the
existence of a unique optimal rate for which the mixing time is
minimized.
On independent permutation
separability criteria
(pp277288)
L. Clarisse and P. Wocjan
Recently, P.\ Wocjan and M.\ Horodecki [Open Syst.\ Inf.\
Dyn.\ 12, 331 (2005)] gave a characterization of combinatorially
independent permutation separability criteria. Combinatorial
independence is a necessary condition for permutations to yield truly
independent criteria meaning that no criterion is strictly stronger that
any other. In this paper we observe that some of these criteria are
still dependent and analyze why these dependencies occur. To remove them
we introduce an improved necessary condition and give a complete
classification of the remaining permutations. We conjecture that the
remaining class of criteria only contains truly independent permutation
separability criteria. Our conjecture is based on the proof that for
two, three and four parties all these criteria are truly independent and
on numerical verification of their independence for up to 8 parties. It
was commonly believed that for three parties there were 9 independent
criteria, here we prove that there are exactly 6 independent criteria
for three parties and 22 for four parties.
back to QIC online Front page
