by Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura and
Martin Rötteler,
This paper considers the problem of efficiently transmitting quantum states
through a network. It has been known for some time that without
additional assumptions it is impossible to achieve this task
perfectly in general - indeed, it is impossible even for
the simple butterfly network. As additional resource we allow free classical
communication between any pair of network nodes. It is shown that
perfect quantum network coding is achievable in this model whenever
classical network coding is possible over the same network when
replacing all quantum capacities by classical capacities. More
precisely, it is proved that perfect quantum network coding using
free classical communication is possible over a network with k
source-target pairs if there exists a classical linear (or even
vector-linear) coding scheme over a finite ring. Our proof is
constructive in that we give explicit quantum coding operations for
each network node. This paper also gives an upper bound on the
number of classical communication required in terms of k, the
maximal fan-in of any network node, and the size of the network.
Proceedings of the International Colloquium on Automata,
Languages and Programming (ICALP'09), LNCS, vol. 5555, pp. 622-633. Springer, 2009.
See also ArXiv preprint
arXiv:0902.1299.
by Pradeep K. Sarvepalli, M. Rötteler, and A. Klappenecker
In this paper we give new decoding algorithms for the generalized
Shor codes and a class of subsystem codes due to Bacon and
Casaccino. Our interest in these codes stems from the fact these codes
can allow us to construct quantum codes from non-dual containing
codes. In this paper we show how to decode these codes efficiently.
Proceedings IEEE International Symposium on Information
Theory (ISIT'09), pp. 804-808, 2009.
by Pradeep K. Sarvepalli, A. Klappenecker, and M. Rötteler
Recently, quantum error-correcting codes were proposed that
capitalize on the fact that many physical error models lead to a
significant asymmetry between the probabilities for bit flip and
phase flip errors. An example for a channel which exhibits such
asymmetry is the combined amplitude damping and dephasing channel,
where the probabilities of bit flips and phase flips can be related
to relaxation and dephasing time, respectively. We study asymmetric
quantum codes that are obtained from the CSS construction. For such
codes we derive upper bounds on the code parameters using linear
programming. A central result of this paper is the explicit
construction of some new families of asymmetric quantum stabilizer
codes from pairs of nested classical codes. For instance, we derive
asymmetric codes using a combination of BCH and finite geometry LDPC
codes. We show that asymmetric quantum codes offer two advantages,
namely to allow a higher rate without sacrificing performance when
compared to symmetric codes and vice versa to allow a higher
performance when compared to symmetric codes of comparable rates.
Our approach is based on a CSS construction that combines BCH and
finite geometry LDPC codes.
Proceedings of the Royal Society London, Ser. A, vol. 465, no. 2105, pp. 1645-1672, 2009.
by Markus Grassl and Martin Rötteler
In the early days of quantum computing, Haroche and Raimond asked
the poignant question whether the dream of quantum computing could
ever be realized in a real physical system or if ``the large-scale
quantum machine ... is the experimenter's nightmare''. At the
time the article was written, the first quantum error-correcting code
had just been proposed. However, Haroche and Raimond argued that
"the implementation of error-correcting codes will become exceedingly
difficult" given any detection efficiency less than 100%. It was
only later that it was shown that even with imperfect quantum memory
and imperfect quantum operations it is possible to implement arbitrary
long quantum computation, provided that the failure probability of
each element is below a certain threshold.
Here we provide an overview of the ingredients leading to fault
tolerant quantum computation (FTQC). In the first part, we present
the theory of quantum error-correcting codes (QECCs) and in particular
two important classes of QECCs, namely the so-called CSS codes and
stabilizer codes. Both are related to classical error-correcting
codes, so we start with some basics from this area. In the second
part of the article, we present a high-level view of the main ideas of
FTQC and the threshold theorem.
In R. A. Meyers, editor, Encyclopedia of Complexity and Systems Science,
Springer, pp. 7324-7342, 2009.
by Martin Rötteler
This is an overview article about quantum error-correcting codes
which appeared as an entry about Shor's 1995 paper in the Encyclopdia
of Algorithms. Keywords: Asymptotically good quantum codes, CSS
quantum codes, Knill-Laflamme conditions for quantum codes, Pauli spin
matrices, quantum channels, quantum error-correcting codes, stabilizer
codes.
Encyclopedia of Algorithms, Ming-Yang Kao (editor), pp. 705-708.
Springer, 2008.
by Markus Grassl and Martin Rötteler
We present a family of non-additive quantum codes based on
Goethals and Preparata codes with parameters ((2^m,2^{2^m-5m+1},8)).
The dimension of these codes is eight times higher than the dimension
of the best known additive quantum codes of equal length and minimum
distance.
Proceedings IEEE International Symposium on Information
Theory (ISIT'08), pp. 300-304, 2008.
See also ArXiv preprint arxiv.org/0801.2150.
by P.K. Sarvepalli, M. Rötteler, and A. Klappenecker
Recently, quantum error-correcting codes were proposed that
capitalize on the fact that many physical error models lead to a
significant asymmetry between the probabilities for bit flip and
phase flip errors. An example for a channel which exhibits such
asymmetry is the combined amplitude damping and dephasing channel,
where the probabilities of bit flips and phase flips can be related
to relaxation and dephasing time, respectively. We give systematic
constructions of asymmetric quantum stabilizer codes that exploit
this asymmetry. Our approach is based on a CSS construction that
combines BCH and finite geometry LDPC codes.
Proceedings IEEE International Symposium on Information
Theory (ISIT'08), pp. 305-309, 2008.
See also ArXiv preprint arxiv.org/0804.4316.
by Markus Grassl and Martin Rötteler
We extend the stabilizer formalism to a class of non-additive
quantum codes which are constructed from non-linear classical codes.
As an example, we present infinite families of non-additive codes
which are derived from Goethals and Preparata codes.
Proceedings 2008 IEEE Information Theory Workshop (ITW'08), pp. 396-400, 2008.
See also ArXiv preprint arxiv.org/0801.2144.
by Salah Aly, Markus Grassl, Andreas Klappenecker, Martin Rötteler,
and Pradeep Sarvepalli
Quantum convolutional codes can be used to protect a sequence of
qubits of arbitrary length against decoherence. We introduce two new
families of quantum convolutional codes. Our construction is based on
an algebraic method which allows to construct classical convolutional
codes from block codes, in particular BCH codes. These codes have the
property that they contain their Euclidean, respectively Hermitian,
dual codes. Hence, they can be used to define quantum convolutional
codes by the stabilizer code construction. We compute BCH-like bounds
on the free distances which can be controlled as in the case of block
codes, and establish that the codes have non-catastrophic encoders.
Proceedings 10th Canadian Workshop on Information Theory (CWIT'07),
pp. 180-183, 2007.
See also ArXiv preprint quant-ph/0703113.
by Markus Grassl and Martin Rötteler
We address the problems of constructing quantum convolutional
codes (QCCs) and of encoding them. The first construction is a
CSS-type construction which allows us to find QCCs of rate 2/4. The
second construction yields a quantum convolutional code by applying a
product code construction to an arbitrary classical convolutional code
and an arbitrary quantum block code. We show that the resulting codes
have highly structured and efficient encoders. Furthermore, we show
that the resulting quantum circuits have finite depth, independent of
the lengths of the input stream, and show that this depth is
polynomial in the degree and frame size of the code.
Proceedings IEEE International Symposium on Information
Theory (ISIT'07), pp. 816-820, 2007.
See also ArXiv preprint quant-ph/0703182.
by Markus Grassl and Martin Rötteler
Quantum convolutional codes can be used to protect streams of
quantum bits against errors when sending them along a quantum
channel. We review the underlying error model, conditions for quantum
convolutional codes, and present a product code construction that
yields families of quantum convolutional codes. Concerning the
structure of encoding circuits for general quantum convolutional
codes, we review the notion of catastrophic errors and show that each
quantum convolutional code has encoders which are non-catastrophic,
i.e., which have good error propagation properties. We present an
algorithm to compute a quantum circuit which can be used to perform
non-catastrophic encoding and inverse encoding in constant depth and
give several examples for illustration.
Proceedings 44th Allerton Conference on Communication, Control, and
Computing, pp. 510-519, 2006.
by Markus Grassl and Martin Rötteler
We present an algorithm to construct quantum circuits for
encoding and inverse encoding of quantum convolutional codes. We show
that any quantum convolutional code contains a subcode of finite index
which has a non-catastrophic encoding circuit. Our work generalizes
the conditions for non-catastrophic encoders derived in a paper by
Ollivier and Tillich
(quant-ph/0401134)
which are applicable only for a restricted class of quantum
convolutional codes. We also show that the encoders and their inverses
constructed by our method naturally can be applied online, i.e.,
qubits can be sent and received with constant delay.
Proceedings IEEE International Symposium on Information
Theory (ISIT'06), pp. 1109-1113, 2006.
See also ArXiv preprint quant-ph/0602129.
by Andreas Klappenecker and Martin Rötteler
Mutually unbiased bases (MUBs) are a primitive used in quantum
information processing to capture the principle of
complementarity. While constructions of maximal sets of d+1 such bases
are known for systems of prime power dimension d, it is unknown
whether this bound can be achieved for any non-prime power
dimension. In this paper we demonstrate that maximal sets of MUBs come
with a rich combinatorial structure by showing that they actually are
the same objects as the complex projective 2-designs with angle set
{0,1/d}. We also give a new and simple proof that symmetric
informationally complete POVMs are complex projective 2-designs with
angle set {1/(d+1)}.
Proceedings of the 2005 IEEE International Symposium on Information Theory
(ISIT'05), pp. 1740-1744, 2005.
See also ArXiv preprint quant-ph/0502031.
by Markus Grassl and Martin Rötteler
We present a construction of self-orthogonal codes using product
codes. From the resulting codes, one can construct both block quantum
error-correcting codes and quantum convolutional codes. We show that
from the examples of convolutional codes found, we can derive ordinary
quantum error-correcting codes using tail-biting with parameters
[[42N,24N,3,2]]. While it is known that the product construction
cannot improve the rate in the classical case, we show that this can
happen for quantum codes: we show that a code [[15,7,3,2]] is obtained
by the product of a code [[5,1,3,2]] with a suitable code.
Proceedings of the 2005 IEEE International Symposium on Information Theory
(ISIT'05), pp. 1018-1022, 2005.
by Andreas Klappenecker and Martin Rötteler
The principle of complementarity lies at the heart of quantum
mechanics. In finite dimensional quantum systems this principle is
captured by pairs of observables which are given by mutually unbiased
bases (MUBs). Two orthonormal bases B and C of \C^d are mutually
unbiased if |\langle b | c \rangle|^2 = 1/d holds for all vectors b in
B and c in C. This implies that whenever we are given a vector from
one of these bases and perform a measurement with respect to any other
of the bases, then there is no information gained from this
measurement. A basic question about MUBs is how many of them can be
found in a given dimension d. While constructions of maximal sets of
d+1 such bases are known for system of prime power dimension d, it is
unknown whether this bound can be achieved for any non-prime power
dimension. We review the known constructions of MUBs and demonstrate
that maximal sets of MUBs come with a rich combinatorial structure by
showing that they actually are the same objects as the complex
projective 2-designs with angle set {0,1/d}. Furthermore, we address
the problem of constructing positive operator-valued measures (POVMs)
in finite dimension d consisting of d^2 operators of rank one which
have an inner product equal to uniform or very close to uniform. This
is motivated by the related question of constructing symmetric
informationally complete POVMs (SIC-POVMs) for which the inner
products are perfectly uniform. We also give a simple proof of the
fact that symmetric informationally complete POVMs are complex
projective 2-designs with angle set {1/(d+1)}. Moreover, we show that
MUBs and SIC-POVMs form uniform tight frames in \C^d.
Proceedings of SPIE International Symposium on Optics and
Photonics, Wavelets XI, vol. 5914, pp. 59140P (13 pages), 2005.
by Andreas Klappenecker, Martin Rötteler, Igor Shparlinski,
and Arne Winterhof
We address the problem of constructing positive operator-valued
measures (POVMs) in finite dimension $n$ consisting of $n^2$ operators
of rank one which have an inner product close to uniform. This is
motivated by the related question of constructing symmetric
informationally complete POVMs (SIC-POVMs) for which the inner
products are perfectly uniform. However, SIC-POVMs are notoriously
hard to construct and despite some success of constructing them
numerically, there is no analytic construction known. We present two
constructions of approximate versions of SIC-POVMs, where a small
deviation from uniformity of the inner products is allowed. The first
construction is based on selecting vectors from a maximal collection
of mutually unbiased bases and works whenever the dimension of the
system is a prime power. The second construction is based on
perturbing the matrix elements of a subset of mutually unbiased bases.
Moreover, we construct vector systems in $\C^n$ which are almost
orthogonal and which might turn out to be useful for quantum
computation. Our constructions are based on results of analytic number
theory.
Journal of Mathematical Physics, 46:082104, 2005.
See also ArXiv preprint quant-ph/0503239.
by Andreas Klappenecker and Martin Rötteler
Unitary error bases generalize the Pauli matrices to higher
dimensional systems. Two basic constructions of unitary error bases
are known: An algebraic construction by Knill, which yields nice error
bases, and a combinatorial construction by Werner, which yields
shift-and-multiply bases. An open problem posed by Schlingemann and
Werner relates these two constructions and asks whether each nice
error basis is equivalent to a shift-and-multiply basis. We solve this
problem and show that the answer is negative. However, we also show
that it is always possible to find a fairly sparse representation of a
nice error basis.
IEEE Transactions on Information Theory, vol. 51, no. 3, pp. 1084-1089,
2005.
See also ArXiv preprint
quant-ph/0301078.
by Andreas Klappenecker and Martin Rötteler
Clifford codes are a class of quantum error control codes that form a
natural generalization of stabilizer codes. These codes were
introduced in 1996 by Knill, but only a single Clifford code was
known, which is not already a stabilizer code. We derive a necessary
and sufficient condition that allows to decide when a Clifford code is
a stabilizer code, and compile a table of all true Clifford codes for
error groups of small order.
Quantum Information and Computation, Vol. 4, No. 2, pp. 152-160.
See also paper "Remarks on Clifford codes"
by Andreas Klappenecker and Martin Rötteler,
Proceedings IEEE International Symposium on Information
Theory (ISIT'04), p. 354, 2004.
See also ArXiv preprint
quant-ph/0312228.
by Markus Grassl, Thomas Beth, and Martin Rötteler
We present families of quantum error-correcting codes which are
optimal in the sense that the minimum distance is maximal. These
maximum distance separable (MDS) codes are defined over q-dimensional
quantum systems, where q is an arbitrary prime power. It is shown that
codes with parameters [[n,n-2d+2,d]]_q exist for all 3 <= n <= q and 1
<= d <= n/2+1. We also present quantum MDS codes with parameters
[[q^2,q^2-2d+2,d]]_q for 1 <= d <= q which additionally give rise to
shortened codes [[q^2-s,q^2-2d+2-s,d]]_q for some s.
International Journal of Quantum Information, vol. 2, no. 1, pp. 55-64, 2004.
See also paper "On quantum MDS codes" by Martin Rötteler, Markus
Grassl, and Thomas Beth,
Proceedings IEEE International Symposium on
Information Theory (ISIT'04), p. 356, 2004.
See also ArXiv preprint
quant-ph/0312164.
by Andreas Klappenecker and Martin Rötteler
Two orthonormal bases B and B' of a d-dimensional complex
inner-product space are called mutually unbiased if and only if |<
b|b'>|^2=1/d holds for all b in B and b' in B'. The size of any
set containing (pairwise) mutually unbiased bases of C^d cannot exceed
d+1. If d is a power of a prime, then extremal sets containing d+1
mutually unbiased bases are known to exist. We give a simplified proof
of this fact based on the estimation of exponential sums. We discuss
conjectures and open problems concerning the maximal number of
mutually unbiased bases for arbitrary dimensions.
Proceedings International Conference on Finite Fields and Applications
(Fq7),
vol. 2948 of Lecture Notes in Computer Science,
pp. 137-144. Springer, 2004.
See also ArXiv preprint
quant-ph/0309120.
by Andreas Klappenecker and Martin Rötteler
Unitary error bases are fundamental primitives in quantum
computing, which are instrumental for quantum error-correcting codes
and the design of teleportation and super-dense coding schemes. There
are two prominent constructions of such bases: an algebraic
construction using projective representations of finite groups and a
combinatorial construction using Latin squares and Hadamard
matrices. An open problem posed by Schlingemann and Werner relates
these two constructions, and asks whether each algebraic construction
is equivalent to a combinatorial construction. We answer this question
by giving an explicit counterexample in dimension 165 which has been
constructed with the help of a computer algebra system.
Proceedings Applied Algebra, Algebraic Algorithms and Error-Correcting
Codes (AAECC-15),
vol. 2643 of Lecture Notes in Computer Science, pp. 139-149, Springer, 2001.
Springer Link
by Markus Grassl, Martin Rötteler, and Thomas Beth
We present two methods for the construction of quantum circuits
for quantum error-correcting codes (QECC). The underlying quantum
systems are tensor products of subsystems (qudits) of equal dimension
which is a prime power. For a QECC encoding k qudits into n qudits,
the resulting quantum circuit has O(n(n-k)) gates. The running time of
the classical algorithm to compute the quantum circuit is O(n(n-k)^2).
International Journal of Foundations of Computer Science, vol. 14,
no. 5, pp. 757-775, 2003.
See also ArXiv preprint quant-ph/0211014.
by Markus Grassl, Andreas Klappenecker, and Martin Rötteler
We show that any stabilizer code over a finite field is
equivalent to a graphical quantum code. Furthermore we prove that a
graphical quantum code over a finite field is a stabilizer code. The
technique used in the proof establishes a new connection between
quantum codes and quadratic forms. We provide some simple examples to
illustrate our results.
Proceedings of the IEEE International Symposium on Information Theory
(ISIT'02), p. 45, Lausanne, 2002.
See also ArXiv preprint quant-ph/0703112.
by Andreas Klappenecker and Martin Rötteler
Quantum error control codes allow to detect and correct errors that
are due to decoherence effects. We review some basic properties of
these codes and give some constructions. Our main focus will be on a
construction of quantum error control codes that have been introduced
by Knill in 1996 with the intention to generalize stabilizer codes.
These so-called Clifford codes can be constructed and analyzed with
tools from representation theory of finite groups. We show that a
large class of Clifford codes are actually stabilizer codes. And we
construct the smallest example of a Clifford code that is not a
stabilizer code.
In: R. Brylinski and G. Chen, editors, The Mathematics of Quantum
Computation, pp. 253-273. CRC Press, 2002.
by Andreas Klappenecker and Martin Rötteler
Nice error bases have been introduced by Knill as a generalization of
the Pauli basis. These bases are shown to be projective
representations of finite groups. We classify all nice error bases of
small degree, and all nice error bases with abelian index groups. We
show that in general an index group of a nice error basis is
necessarily solvable.
IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2392-2395,
2002.
See also ArXiv preprint
quant-ph/0010082.
by Andreas Klappenecker and Martin Rötteler
Knill introduced a generalization of stabilizer codes, in this
note called Clifford codes. It remained unclear whether or not
Clifford codes can be superior to stabilizer codes. We show that
Clifford codes are stabilizer codes provided that the abstract error
group is given by an extraspecial p-group. Suppose that the abstract
error group has an abelian index group, then we show that a Clifford
code can be derived from an abelian normal subgroup.
IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2396-2399,
2002.
See also ArXiv preprint
quant-ph/0010076.