Quantum Information Processing - Hardcover

Hardcover

ISBN 10: 3527405410 ISBN 13: 9783527405411

Publisher: Wiley-VCH, 2005

Synopsis

Quantum processing and communication is emerging as a challenging technique at the beginning of the new millennium. This is an up-to-date insight into the current research of quantum superposition, entanglement, and the quantum measurement process - the key ingredients of quantum information processing. The authors further address quantum protocols and algorithms. Complementary to similar programmes in other countries and at the European level, the German Research Foundation (DFG) realized a focused research program on quantum information. The contributions - written by leading experts - bring together the latest results in quantum information as well as addressing all the relevant questions.

About this title

About the Author

Thomas Beth studied mathematics, physics and medicine. He received his Ph.D. in 1978 and his Postdoctoral Lecturer Qualification (Dr.-Ing. habil.) in informatics in 1984. From a position as Professor of computer science at the University of London he was apppointed to a chair of informatics at the University of Karlsruhe. He also is the director of the European Institute for System Security (E.I.S.S.). In the past decade he has built up a research center for quantum information at the Institute for Algorithms and Cognitive Systems (IAKS). Professor Thomas Beth passed away in 2005.

Gerd Leuchs studied physics and mathematics at the University of Cologne and received his Ph.D. in 1978. After two research visits at the University of Colorado, Boulder, he headed the German Gravitational Wave Detection Group from 1985 to 1989. He then went on to be the technical director of Nanomach AG in Switzerland for four years. Since 1994 he holds the chair for optics at the Friedrich-Alexander-University of Erlangen-Nuremberg, Germany. His fields of research span the range from modern aspects of classical optics to quantum optics and quantum information.

From the Back Cover

This revised edition provides an up-to-date insight into the current research of quantum superposition, entanglement, and the quantum measurement process - the key ingredients of quantum information processing. The contributions have been carefully revised and enlarged with respect to recent developments in quantum computation, quantum transportation and cryptography. Here, leading experts bring together the latest results in quantum information and address all the relevant questions.

Excerpt. © Reprinted by permission. All rights reserved.

Quantum Information Processing

John Wiley & Sons

Copyright © 2005 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim
All right reserved.
ISBN: 978-3-527-40541-1

Chapter One

Algorithms for Quantum Systems - Quantum Algorithms

Th. Beth, M. Grassl, D. Janzing, M. Rtteler, P. Wocjan, and R. Zeier

Institut fr Algorithmen und Kognitive Systeme Universitt Karlsruhe Germany

1.1 Introduction

Since the presentation of polynomial time quantum algorithms for discrete log and factoring [Sho94] it is generally accepted that quantum computers may-at least for some problems-outperform classical ones. But the field of quantum information processing does not only have implications for computational problems. Using quantum mechanical systems for information processing naturally leads to the problem of finding efficient ways to control quantum mechanical systems.

Here we address several algorithmic aspects of quantum information processing in different areas. First, the state of the art of quantum signal transforms which are at the core of a huge class of quantum algorithms, namely hidden subgroup problems, is presented. Second, we discuss aspects of quantum error-correcting codes, in particular an interesting view on stabilizer codes which relates them to simple interaction Hamiltonians. The efficient implementation of unitary operations by given Hamiltonians is investigated next. Finally, results on the simulation of one quantum mechanical system by another are discussed.

1.2 Fast Quantum Signal Transforms

A basic task in classical signal processing is to find fast algorithms which compute the matrix-vector-product of a given transformation with an arbitrary input vector. Suppose that the input is a vector of length N with complex entries. A transformation is said to have a fast algorithm if the number of arithmetic operations needed to compute the matrix vector product-i.e., the number of additions and multiplications-is bounded by O(N [log.sup.c N), for some constant c. Amongst the most useful algorithms in computer science, physics, and engineering is the discrete Fourier transform [DFT.sub.N] which is given by the unitary matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where w = [e.sup.2[pi]i/N] denotes a primitive N-th root of unity. The computational complexity of computing the product [F.sub.N] x for an input vector x [member of] [[??].sup.N] is O(N log N).

In quantum computing the unitary transformation [F.sub.N] is used in the following way. Suppose that a system consisting of n qubits holds a normalized state vector |[psi]> = [[summation].sup.N.sub.i=1] [x.sub.i]|i> [member of] [[??].sub.N], where N := [2.sup.n]. Note that here the information is encoded into the amplitudes of the basis states. To this state the unitary transformation [F.sub.N] can be applied resulting in a state [F.sub.N]|[psi]>. Unlike the situation in classical signal processing the components of |[psi]> and [F.sub.N] |[psi]> are not directly accessible; they merely can be extracted by (POVM) measurements. However, for feature detecting purposes like the location of spectral peaks this approach is well-suited.

A quantum Fourier transform can be computed using O([log.sup.2] N) elementary operations. This exponential speed-up compared to the classical complexity of the DFT, which surprisingly enough is obtained by a direct adaptation of the classic Cooley-Tukey algorithm to the quantum circuit model, is an essential indication for the power of quantum computing. This becomes manifest in the fact that the ability to compute a DFT in polylogarithmic time is the backbone of Shor's algorithms for factoring and computing the discrete logarithm [Sho94].

A natural question is whether other signal transforms which have desirable feature extraction properties in classical signal processing can be used for quantum algorithms. In a series of works [PRB99, RPB99, KR00, [ABH.sup.+]01, KR01, Rt02] it has been shown that many well-known signal transforms allow highly efficient realizations on a quantum computer. In particular the following classes of unitary transformations have been shown to be efficiently implementable on a quantum computer:

Discrete Fourier transforms for finite abelian groups [[ABH.sup.+]01, Rt02].

Generalized Fourier transforms for

- 2-groups with maximal cyclic normal subgroup [PRB99, Rt02].

- wreath products of the form G = A [??] Z.sub.2], where A is abelian [RB98, Rt02].

- Heisenberg groups over the finite fields [[??].sub.[2.sup.n] [Rt02].

Discrete cosine and sine transforms of types I, II, III, and IV [RB99, KR01, Rt02].

Discrete Hartley transforms [KR00, Rt02].

More precisely, we have shown that for discrete cosine transforms, discrete sine transforms, and discrete Hartley transforms O([log.sup.2] N) elementary quantum gates are sufficient to implement any of those transforms for input sequences of length N. The Fourier transforms for finite groups which have been mentioned above have the same computational complexity, except for the Heisenberg group where an implementation using O([log.sup.3] N) gates has been found.

The underlying theory which allows to find efficient factorizations in the above mentioned cases relies on two techniques which have been developed at the Institut fr Algorithmen und Kognitive Systeme. The first technique is the so-called method of symmetry-based matrix factorizations. Here a matrix M [member of] [[??].sup.n n] is said to have symmetry (G, [empty set], [psi]) if [empty set] and [psi] are representations of a finite group G and furthermore

[empty set](g) M = M [psi](g), for all g [member of] G.

The importance of symmetry in connection with generalized Fourier transforms was first recognized in the work of Th. Beth [Bet84]. An important feature of this approach is that classical fast algorithms can be explained-and automatically derived-in terms of symmetry of matrices [Min93, Egn97, Ps98].

In the thesis of M. Rtteler [Rt02] symmetry-based matrix factorizations have been taken as a starting point for further optimizations. This has led to efficient implementations of several generalized Fourier transforms, trigonometric transforms, and the Hartley transform.

A second technique has been developed by A. Klappenecker and M. Rtteler and is described in [Rt02]and [KR03]. The basic idea is to reuse previously found factorizations for the construction of higher level operations. A prime example is given by the problem of implementing functions of unitary transformations, i. e., operations of the form f(U), where U is a unitary transformation of finite order and f(U) is also unitary.

1.3 Quantum Error-correcting Codes

Owing to the high sensitivity of quantum mechanical systems to even small perturbations, means of error protection are essential for any computation or communication process based on quantum mechanics. A general theory of quantum error-correcting codes (QECC) has been developed (see, e.g., [KL97]), but many algorithmic aspects are still open. The main tasks are to find methods for constructing good QECC and efficient algorithms for encoding and decoding, including the correction of the errors.

A large family of QECC can be derived from cyclic codes (see [GB99, GGB99, GB00]). Those QECC admit various techniques for encoding and decoding, e.g., based on Fourier transformations over finite fields and quantum shift registers [BG00]. An interesting new class of QECC has been developed in cooperation with the group of G. Alber [ABC.sup.+]01, AMD03]. Those so-called jump codes exploit side-information about the errors due to the emission of quanta (quantum jumps). The side-information is obtained by continuously monitoring the quantum system and recording which subsystem emitted, e.g., a photon. An interesting connection to design theory leads to various constructions of jump codes [[BCG.sup.+]03].

Another new concept of QECC linking various groups in the Schwerpunktprogramm QIV are so-called graph codes which have been introduced by D. Schlingemann and R. F. Werner [SW02]. Similar to the cluster states used in the one-way quantum computer of R. Raussendorf and H. J. Briegel [RB01], the basis states of a graph code are defined via an interaction graph corresponding to the spin-spin coupling Hamiltonian which can be used for encoding. Compared to the standard gate model of quantum computation, such a coupling Hamiltonian yields a very efficient-intrinsically parallel-algorithm.

We have shown that the concepts of graph codes and that of so-called stabilizer codes are equivalent, i.e., any graph code is a stabilizer code and vice versa [GKR02, Sch02, [WSR.sup.+]02]. In the following, we will present the main ideas used in the proof.

Starting from an [alpha]-dimensional Hilbert space H, a graph code is an [[alpha].sup.k]-dimensional subspace Q of [H.sup.[cross product]n] which is spanned by the vectors

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1.1)

Here the dimension a is a prime power, i.e., [alpha] = [p.sup.m] for some prime number p. The basis states |y> of [H.sup.[cross product]n] are labeled by vectors y [member of] [[??].sup.n.sub.[p.sup.m]] over the finite field [[??].sub.[p.sup.m]], and the encoded states |[x.bar]> are labeled by vectors x [member of] [[??].sup.k[p.sup.m]]. The coefficients on the right hand side are given by the values of a non-degenerate symmetric bicharacter [chi] on [[??][p.sup.m]] [[??][p.sup.m]], where z = (x, y). Finally, the exponents [[GAMMA].sub.ij] are given by the adjacency matrix [GAMMA] of a weighted undirected graph with integral weights (corresponding to the coupling strength between the subsystems i and j). Equivalently, the states (1.1) of the graph code Q can be expressed in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2)

where [zeta] is a non-trivial additive character of [[??].sub.p] and q is a quadratic form on [[??].sup.k+n.sub.[p.sup.m] [congruent to] [[??].sup.m(k + n).sub.p]. This isomorphism shows that it is sufficient to consider graphical quantum codes which are defined over prime fields.

First we show that a graph code defined over the finite field [[??].sub.p] is a stabilizer code, i.e., a joint eigenspace of an abelian subgroup of the error group G generated by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for a, d [member of] [[??].sup.n.sub.p] (cf. [KR02a,KR02b]). Starting from (1.2) one can show that the stabilizer of Q is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The matrices [M.sub.y] [member of] [[??].sup.n n.sub.p] and B [member of] [[??].sup.k n.sub.p] are submatrices of the adjacency matrix [GAMMA] defining the quadratic form q which can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Additionally, the orthogonal projection onto the joint eigenspace for the eigenvalue 1 of the operators in [S.sub.Q] coincides with Q, showing that Q indeed is a stabilizer code.

In order to show that any stabilizer code defined over the finite field [[??].sub.p.sup.m] can be realized as a graph code, we first note that those stabilizer codes can equivalently be considered as stabilizer codes over [[??].sub.p] (see [AK01]). To any stabilizer code corresponds a (classical) symplectic code ITLITL over [[??].sub.p.sup.2]. The generator matrix of ITLITL can be written as (X|Z) where X, Z [member of] [[??].sup.(n-k) n.sub.p] and X[Z.sup.t] - X[Z.sup.t] = 0. As the code ITLITL is self-orthogonal, i.e., contained in the orthogonal code [ITLITL.sup.[perpendicular to]] with respect to the symplectic inner product on [[??].sup.n.sub.p.sup.2]], there exists a self-dual code D with C [[subset].bar] D = [D.sup.[perpendicular to]][[subset].bar] [C.sup.[perpendicular to]]. We can choose a generator matrix for D of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similar to Gauss' algorithm, the matrix G' can be transformed into standard form (I|C) where ITLITL is symmetric [Gra02a, Gra02b]. Quantum mechanically, the transformations correspond to local unitary operations which do not change the error-correcting properties of the QECC. Applying the same transformations to the subcode ITLITL of D, we obtain an equivalent code whose generator matrix can be written as (D|DC) where D [member of] [[??].sup. (n-k) n]. Finally, we obtain the symmetric matrix

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where D[B.sup.t] = 0. Using this matrix [GAMMA] as adjacency matrix in (1.1), we obtain a graph code which is equivalent to the stabilizer code corresponding to ITLITL. Hence, for any stabilizer code over [[??].sub.[p.sup.m] there exists an equivalent graph code.

In general, the corresponding graph is not uniquely determined, as illustrated in Fig. 1.1. All four graphs yield equivalent QECC, but the graphs are non-isomorphic. Therefore it is not straightforward to relate basic properties of the graph and the error-correcting properties of the resulting graph code. But the possibility to choose among different graphs results in different interaction Hamiltonians which may yield more efficient algorithms for encoding (cf. Section 1.5).

1.4 Efficient Decomposition of Quantum Operations into Given One-parameter Groups

The time evolution of all quantum mechanical systems is governed by the Schrdinger equation. To control the time evolution of a concrete physical implementation, we apply different Hamilton operators which are supposed to be time independent. This gives us the ability to implement computational operators on the state space. Equipped with m one-parameter groups

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

generated by the different Hamilton operators [H.sub.j], the goal is to build up each unitary U as a product of elements of the given one-parameter groups:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As an efficiency measure we consider the minimal number of terms needed to express each unitary as a product of the given one-parameter groups. This efficiency measure is called the order of generation [Low71]. In a physical implementation of the given unitary operator this corresponds to the number of switches between different Hamilton operators.

As a first step we derive conditions on the set of Hamilton operators to be universal, i.e., to be able to generate each unitary. From the work of Chow [Cho39] follows the Lie algebra rank condition which states that each unitary can be implemented if the rank of the subalgebra generated by the given Hamilton operators equals the dimension of the Lie algebra belonging to the considered unitary operators. The work of Jurdjevic and Sussmann [JS72] states in addition that the order of generation is finite if the Lie algebra rank condition is fulfilled. To exclude-in the case of compact and connected Lie groups-the possibility of an infinite order of generation in the closure the work in [D'A02] can be used.

We emphasize that the order of generation depends heavily on the given one-parameter groups. The problem of determining bounds on the order of generation in the case of up to three Hamilton operators from the su(2) was considered in [ZB02]. Describing Hamilton operators as infinitesimal rotations of the Bloch sphere we can depict the application of an Hamilton operator in the complex plane after a stereographic projection from the Bloch sphere to the one-point compactification of the complex numbers. It is known [Gau19] that under stereographic projection the rotations of the sphere correspond to rotational Mbius transformations:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(Continues...)

Excerpted from Quantum Information Processing Copyright © 2005 by Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Edition details

• Publisher: Wiley-VCH
• Publication date: 2005
• Language: English
• ISBN 10: 3527405410
• ISBN 13: 9783527405411
• Binding: Hardcover
• Edition number: 2
• Number of pages: 471
• Editor: Beth Thomas, Leuchs Gerd