Quantum Information Processing - Hardcover

Hardcover

ISBN 10: 3527405410 ISBN 13: 9783527405411

Verlag: Wiley-VCH, 2005

Inhaltsangabe

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.

Über diesen Titel

Über die Autorin bzw. den Autor

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.

Von der hinteren Coverseite

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.

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

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

Details zur Ausgabe

• Verlag: Wiley-VCH
• Erscheinungsdatum: 2005
• Sprache: Englisch
• ISBN 10: 3527405410
• ISBN 13: 9783527405411
• Einband: Gebundene Ausgabe
• Auflage: 2
• Anzahl der Seiten: 471
• Herausgeber: Beth Thomas, Leuchs Gerd
• Kontakt zum Hersteller: Wiley VCH Verlag GmbH; info@wiley-vch.de; ; Boschstraße 12; Weinheim; Baden-Württemberg; 69469; Deutschland