Transcript Extrimes of Information Combining

Fidelities of Quantum ARQ Protocol
Alexei Ashikhmin
Bell Labs
 Classical Automatic Repeat Request (ARQ) Protocol
 Qubits, von Neumann Measurement, Quantum Codes
 Quantum Automatic Repeat Request (ARQ) Protocol
 Quantum Errors
 Quantum Enumerators
 Fidelity of Quantum ARQ Protocol
• Quantum Codes of Finite Lengths
• The asymptotical Case (the code length
)
Some results from the paper “Quantum Error Detection”, by A. Ashikhmin,A. Barg, E. Knill, and
S. Litsyn are used in this talk
Classical ARQ Protocol
Noisy Channel
•
is a parity check matrix of a code
• Compute syndrome
• If
• If
we detect an error
, but
we have an undetected error
Qubits
qubits
• The state (pure) of
• Manipulating by
qubits is a vector
qubits, we effectively manipulate by
complex coefficients of
• As a result we obtain a significant (sometimes exponential)
speed up
• In this talk all complex vectors
are assumed to be
normalized, i.e.
• All normalization factors are omitted to make notation short
von Neumann Measurement
and
orthogonal subspaces,
is the orthogonal projection on
is the orthogonal projection on
•
is projected on
with probability
•
is projected on
with probability
• We know to which subspace
was projected
Quantum Codes
1
2
…
k
information qubits
in state
k+1 …
n
unitary rotation
redundant qubits
in the ground states
1
2
… n
quantum codeword
in the state
the joint state:
is the code space
is the code rate
Quantum ARQ Protocol
ARQ protocol:
–
–
–
–
–
We transmit a code state
Receive
Measure
with respect
to
and
If the result of the
measurement belongs to
we ask to repeat transmission
Otherwise we use
is fidelity
If
is close to 1 we can use
Conditional Fidelity
Quantum ARQ Protocol
Recall that the probability that
is projected on is equal to
The conditional fidelity
under the condition that
is the average value of
is projected on
Quantum Errors
• Quantum computer is unavoidably vulnerable to errors
• Any quantum system is not completely isolated from the
environment
• Uncertainty principle – we can not simultaneously reduce:
– laser intensity and phase fluctuations
– magnetic and electric fields fluctuations
– momentum and position of an ion
• The probability of spontaneous emission is always greater
than 0
• Leakage error – electron moves to a third level of energy
Quantum Errors
Depolarizing Channel (Standard Error Model)
Depolarizing Channel
means the absence of error
are the flip, phase, and flip-phase errors respectively
This is an analog of the classical quaternary symmetric channel
Quantum Errors
Similar to the classical case we can define the weight of error:
Obviously
Quantum Enumerators
is a code with the orthogonal projector
P. Shor and R. Laflamme:
Quantum Enumerators
•
and
where
are connected by quaternary MacWilliams identities
are quaternary Krawtchouk polynomials:
•
• The dimension of
•
is
is the smallest integer s. t.
errors
then
can correct any
Quantum Enumerators
• In many cases
are known or can be accurately estimated
(especially for quantum stabilizer codes)
• For example, the Steane code (encodes 1 qubit into 7 qubits):
•
and
can correct any single ( since
therefore this code
) error
Fidelity of Quantum ARQ Protocol
Recall that the probability that
is projected on is equal to
The conditional fidelity
under the condition that
Theorem
is the average value of
is projected on
Lemma (representation theory) Let
be a compact group, is a
unitary representation of , and is the Haar measure. Then
Lemma
Fidelity of the Quantum ARQ Protocol
Quantum Codes of Finite Lengths
We can numerically compute upper and lower bounds on
(recall that
)
,
Fidelity of the Quantum ARQ Protocol
Sketch:
• using the MacWilliams identities
• we obtain
• using inequalities
we can
formulate LP problems for enumerator and denominator
Fidelity of the Quantum ARQ Protocol
For the famous Steane code (encodes 1 qubit into 7 qubits)
we have:
Fidelity of the Quantum ARQ Protocol
Lemma The probability that
Hence we can consider
will be projected onto
as a function of
equals
Fidelity of the Quantum ARQ Protocol
• Let
be the known optimal code encoding 1 qubit into 5 qubits
• Let
be code that encodes 1 qubit into 5 qubits defined by the
generator matrix:
•
is not optimal at all
Fidelity of the Quantum ARQ Protocol
Fidelity of the Quantum ARQ Protocol
The Asymptotic Case
Theorem ( threshold behavior )
Asymptotically, as
, we have
(if Q encodes
qubits into
qubits its rate is
Theorem (the error exponent) For
)
we have
Fidelity of the Quantum ARQ Protocol
Existence bound
Theorem There exists a quantum code Q with the
binomial weight enumerators:
Substitution of these
into
gives the existence bound on
Upper bound is much more difficult
Fidelity of the Quantum ARQ Protocol
Sketch:
• Primal LP problem:
• subject to constrains:
Fidelity of the Quantum ARQ Protocol
• From the dual LP problem we obtain:
Theorem Let
then
Good solution:
and
be s.t.