Saturday, 22 May 2010

Book Review: Quantum Computation and Quantum Information

The Enigmatic Qubit

The first thing an engineer wants to do, having learned about quantum computational "qubits", is to simulate them. After all, digital simulations of arbitrary analog computers (of which the Gristleizer musical effects pedal is an example) can be realised in any modern synthesizer. The state of an analog machine is nothing more than the list of instantaneous voltages at the outputs of its various amplifiers, integrators, differentiators. Isn't the quantum computer just like such an analog machine, in every essential way?

Further investigation into the mathematical nature of the qubit initially appears to yield more encouragement of this kind. There's a model known as the Bloch Sphere which describes the qubit's state 'ψ' as a tethered vector of standard length, pointing out in some random spatial direction. The surface of the generated sphere is obviously two dimensional. So, just as we would treat each node voltage in a given analog setup as a single floating point number in our digital simulation, doesn't this mean we can model a qubit by an ordered pair of such floating point numbers (such as φ and θ in the diagram below)?

The Bloch Sphere (Wikipedia)
Reading the qubit causes it to "collapse" to an arrow pointing (say) vertically either straight up or straight down. Can't we just simulate this operation statistically, in well-known, classical ways?

Realistically, the answer to all of this is "No." Such simulations involve unbelievably unrealistic magnitudes of repetition, sampling, and hardware scaling. Often the end result is still a hopelessly crude approximation. And as soon as we make the first obvious upgrades, from a single qubit to a pair, admitting as this does the possibility of entanglement, then even this model vapourises; while ascending to larger numbers of qubits, classical approximations rapidly become impossible in principle, even as research simulations - see e.g. the Quantiki List of QC Simulators for coverage, or alternatively Steven Peil's Imitating quantum mechanics: Qubit-based model for simulation (Phys. Rev. A 79, 042320, 2009) for one thoroughly detailed treatment.

Fortunately, it doesn't take a lot of expertise in quantum fundamentals to prove this. And once accepted, you will find yourself already at such a level, and with sufficient theoretical tools of quantum modelling and investigation at your disposal, that you will no longer have any interest in following such a dead end path anyway!

A Comprehensive Introduction

Michael A. Nielsen (University of Queensland) and Isaac L. Chuang (IBM / Stanford University) first published their masterwork in 2000. Since then it has been reprinted better than annually. It is a considerable testament to their foresight, and to their thoroughness, that ten years later, and in the present environment of almost daily revelations and astounding leaps of progress in the field, their work has remained so current, relevant, authoritative, and easy to recommend as either comprehensive primer or full-year course.

The book is unapologetically mathematical in its hardcore technical approach, after all this is a serious course textbook, not a "popular science" title! There are several tables and figures of nomenclature and convention, distributed throughout the early sections of each main book part, to be encountered as and when these are required. The generous use of diagrams is particularly helpful, given the sheer density of topics likely to be completely new to the reader.

As the title implies, this book seeks to furnish a sound working fundamental basis in the theory and practice of both quantum computation, and quantum information systems. Each of these fields has spawned an expository industry of its own, and more modern publications tend to specialise in one field or the other (the cover blurbs include one from a certain Peter Shor of AT&T Research, saying The field is already too big to cover in one book...). It is therefore quite natural and unsurprising to discover that this venerable tome comprises three main parts, once the common fundamental concepts, necessary to make a start in either of these main areas, are factored out into their own introductory section.

Part I: Fundamental Concepts

This is further subdivided into three parts.

Chapter 1, a general Introduction and Overview, provides both basic historical context and remarks about future directions, followed by more in-depth introductions to quantum bits, isolated and multiple; qubit states, gates, circuits and measurements; quantum teleportation, parallelism and algorithms; practical information processing considerations, and information theory in a wider context.

Chapter 2 is a serviceable introduction to prerequisite mathematical subjects, including aspects of linear algebra; the postulates of quantum mechanics; and the nature and evolution of, and measurements within, quantum state space. The chapter ends with an assortment of more specialised discussions on density operators and the Bell Inequality.

Chapter 3 rounds off the introductory material from the perspective of computer science, with Turing Machines, logic circuits, resources and complexity. Here we are introduced to reversible computation, as a means of bringing some important, universal computation gates (Fredkin and Toffoli) into the discourse.

Part II: Quantum Computation

This section of the book deals mostly with the dynamics of closed quantum systems, i.e., those without any unwanted interactions with the outside world.

Chapter 4: Quantum Circuits kicks off the detailed exploration of quantum computation with a survey of the few essentially quantum algorithms known at the time of writing (January 2000, although there has by no means been an interim explosion in these). Next, single qubit operations are explored, and modelled using 2x2 matrices of complex coefficients. This allows the countenancing of compositions, and the introduction of quantum circuit components such as the common single qubit "gates": the Hadamard, H; the Pauli rotations, X, Y and Z; the Phase, S; and the π/8, T.

The general notion of a controlled operation, and particularly the controlled-NOT or CNOT (previously mentioned in the introductory material), then serves as our first example of a multi-qubit gate. The ensuing section, on the analysis and synthesis of higher-order operations such as the Toffoli and Fredkin gates, is particularly rigorous and lucid.

This chapter concludes with useful treatments of topics like quantum measurement, gate universality, computational complexity, the quantum circuit model of computation, and finally some illustrative examples of quantum simulation (an advanced topic).

Chapter 5: The Quantum Fourier Transform and its Applications, after a brace of introductory limericks, focuses down on one of the most spectacular successes (to date) in the search for uniquely quantum algorithms: the Quantum Fourier Transform, an efficient quantum algorithm for performing a Fourier transform of quantum mechanical amplitudes. Here the authors begin to disabuse us of faulty preconceptions engendered by the popular science press, as this is not a faster version of the classical Fourier transform; rather, certain problems thought to be quite intractable on classical systems can be attacked through it. Various applications such as phase estimation, order-finding, the hidden subgroup problem, and of course good old fashioned factoring, are demonstrated.

Chapter 6: Quantum Search Algorithms reintroduces the notion of the oracle, a black box previously alluded to in the introductory sections, showing how its application can be used to speed up a process (such as factoring, although this example has expository rather than practical advantages) in probabilistic ways, effectively by allowing an already "known" answer to become "recognised". Illustrations of Grover Iteration are derived, rigorously presented, and analysed; while one particular full-page diagram, illustrating the quantum addressing of a classical strip of memory, takes the biscuit for effective communication of principles.

Chapter 7: Quantum Computers: Physical Realization is inevitably the least current of all the subject subdivisions on show here. Not a week goes by without one or several new and revolutionary potential mechanisms or improvements being heralded as the vanguard of the ultimate scalable quantum computer. As important and significant as these advances certainly are, they are nevertheless matters of degree, while for theoretical purposes you'd be just as well using any of the implementations detailed here.

Comparisons are made among the various qubit design types - spin, charge, and photon - on the basis of decoherence, and the maximum expected number of operations. Hamiltonian analysis of simplified quantum harmonic oscillators will surely remain extremely important and useful for the foreseeable future (even today, any engineer should know how to solve the Schrodinger wave equation for various sample potential profiles). Then too are considered optical photons and cavities, ion traps, NMR, and some other types that once, a decade ago, must have appeared a lot more speculative than now.

Part III: Quantum Information

The last and largest section of the book covers various aspects of noise, i.e., unwanted interactions between real quantum systems and the world external to these.

Chapter 8: Quantum Noise and Quantum Operations breaks the ice with a brief description of stochastic changes to classical states, traditionally modelled by cascaded independent Markov processes under the assumption that is termed Markovicity, before going on to introduce a powerful tool for describing the evolution of quantum states: the quantum operations formalism. The particularly elegant operator-sum representation (using operators only on the Hilbert space of the main system) is developed and applied to several example cases.

Chapter 9: Distance Measures for Quantum Information gets a bit esoteric, tackling questions like: How close are two quantum states? How well does a quantum channel preserve information? Trace distance and fidelity are discussed (the former being found to have a particularly simple geometric interpretation in the case of a single qubit, namely half the Euclidean distance between the corresponding points on the Bloch Sphere illustrated above). One significant takeaway is a satisfyingly short proof of Uhlmann's Theorem.

Chapter 10: Quantum Error-Correction covers three broad topics relating to the reliable processing of quantum information in the presence of noise; to wit (the basic theory of) quantum error-correcting codes, fault-tolerant quantum computation, and the threshold theorem. Starting with classical error-correction, we are shown some conceptual challenges on the road to simple quantum error-correcting codes, subsequently generalised into a theory of quantum error-correcting codes. Then, some musing on the classical theory of linear codes gives rise to the fascinating Calderbank-Shor-Steane code system, and eventually we reach the so-called stabilizer codes. By this point, the authors' poetic sub-chapter introductions have evolved into sonnets! No, I'm serious. A refreshingly practical treatment of fault tolerance winds up chapter 10.

Chapter 11: Entropy and Information contains rather a lot of mathematics for such a short chapter, but looks as if it just might be of interest to someone, somewhere, some day. Who can say? Not me anyway. Stephen Hawking maybe?

Chapter 12: Quantum Information Theory brings it all nicely together. Yes, even the entropy stuff: high entropy implies low fidelity, after all. Other topics include the Holevo bound; Shannon's (classical) and Schumacher's (quantum) noiseless channel coding theorems; information over noisy quantum channels; entanglement distillation; and of course quantum cryptography.

Appendices mitigate the forementioned prerequisites by furnishing basic coverage of number theory; the theories of basic probability, and of groups; self-contained treatments of the Solovay-Kitaev and Lieb Theorems; and public key / RSA cryptography.


If any chapter(s) would be seen as the Achilles' Heel of the book, then the concluding chapters of parts II and III are surely most at risk, concerned as they are with the state of the art of quantum computing and/or IT at the turn of the millennium. But with help from the certitude of mathematics, the breadth of scope (and consequently implied shallowness of treatment), and expert exposition and presentation, upon inspection it passes the test of time rather well.

Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang

Cambridge University Press

First published 2000

ISBN 0-521-63235-8 (hardback)

ISBN 0-521-63503-9 (paperback)

No comments:

Post a Comment