QIP · 1999

I will review the main quantum algorithms using new insights obtained over the past few years. This will include the quantum Fourier transform, Shor's algorithms, the eigenvalue estimation approach of Kitaev, relations to other algorithms and connections between them. Quantum amplitude estimation (a generalisation of quantum counting) will also be discussed.

Quantum information processing (including classical processing as a subset) utilizes resources such as entanglement, interaction, communication via noiseless or noisy channels, and thermodynamic irreversibility to perform desired transformations of classical information and intact quantum states. I survey the emerging theory of reducibilities and equivalences among these resources.

The quantum correlations between spatially separated systems that were formerly in close contact but no longer interact, can have a mysterious quality, captured by the phrase "quantum nonlocality". Attitudes toward this "nonlocality" vary from the view that nothing is nonlocal except the misguided attempt to explain the correlations in terms of nonexistent "hidden variables", to the view that quantum mechanics has proved that what you decide to do over here can instantaneously alter the physical character of something over there. Such conceptually mysterious correlations have assumed a central role in quantum information theory. While the philosophical puzzles do not hinder the gedanken-practical application of the correlations, quantum information scientists might bear the puzzles in mind, on the chance that some of the exquisitely clever things they manage to do with entangled states might illuminate them.

Bell inequalities are upper bounds on the correlations of distant events. They involve only classical (Boolean) logic and the principle of local causes, namely: events that occur in a given spacetime region are independent of external parameters that may be controlled, at the same moment, by agents located in distant spacetime regions. Bell's momentous discovery was that these bounds might be exceeded by the correlations predicted by quantum mechanics.

We have discovered various ensembles of orthogonal bipartite (and multipartite) quantum states which show a variety of manifestations of quantum nonlocality. When their parts are shared between several parties, the identity of these states cannot be determined reliably, even if these parties are allowed any local quantum operations and any amount of classical communication.

It is by now widely accepted that decoherence can single out a preferred pointer basis through the process known as environment-induced superselection (or einselection), and that its undoing is difficult as the monitoring by the environment is (effectively, if not in principle) irreversible. I shall analyse the nature of decoherence -- in particular, the reasons for why is it so difficult to undo -- from an algorithmic point of view.

A mixed state is called entangled (non-separable) if it is not a mixture of product states. It called bound entangled if it is entangled, but cannot be distilled i.e. brought to the maximally entangled form by means of local quantum operations and classical communication. A characterization of bound entangled states is given.

We obtain easy examples of "bound" entanglement--entangled mixed states from which no pure entanglement is distillable--using the notion of an unextendible product basis, of which we give examples. We exhibit a bound-entangled state of a tripartite 2x2x2 system that has no bipartite entanglement, in the sense that all three corresponding 2x4 bipartite states are unentangled.

I will describe a classical randomized simulation of noisy quantum Turing machines and noisy quantum circuits. It is shown that for quantum Turing machine with any non-zero amount of noise, the simulation is efficient. Hence noisy quantum Turing machines have no computational advantage over classical computers.

I address the question of how a quantum computer can be used to simulate experiments on quantum systems in thermal equilibrium. I present two approaches for the preparation of the equilibrium state on a quantum computer. For both approaches, one can show that the output state of the algorithm, after long enough time, is the desired equilibrium.

I will explain how quantum error correcting codes work, using a few simple examples, and introduce some of the general theory of quantum error correction.

I will present some of the general theory of quantum error correction, while discussing recent work in the area of fault tolerant computing. There is a fundamental discrepancy between the conditions for efficient memory storage and those for simple operations to evolve a quantum computation.

In this talk, we will present a set of recent results on universal gates and fault-tolerant (FT) quantum computing. Several sets of gates have been proved to be universal for quantum computing; however, sets of gates that are universal for fault-tolerant quantum computing have received only limited attention.

Recent advances in communication complexity in a setting where quantum information is available are reviewed. Holevo's Theorem implies that n qubits cannot convey more classical information than n bits. Nevertheless, there are information processing tasks that require communication and for which using qubits instead of bits results in substantial savings.

Although Communication Complexity is not a recent topic in computer science, its relations to quantum information theory is much more recent. Following the result of R. Cleve and H. Buhrman, we now know that entanglement can significantly reduce the communication required for a set of players to compute some specific function of their private inputs.

Alice and Bob want to play cards over the phone. To start the game each of them should choose a set of ten random cards, and of course the two sets have to be disjoint. How much communication between Alice and Bob is needed to achieve this task? In the talk I will define the sampling communication complexity model, which generalizes the above example.

A computational problem is said to be in BQNP if it can be defined in terms of a quantum witness verifiable on a quantum computer in polynomial time. (The abbreviation stands for "bounded error probability, quantum nondeterministic polinomial"). The following problem is shown to be BQNP complete: decide whether a "local Hamiltonian" (a sum of several Hermitian operators, each involving a constant number of qubits) has an eigenvalue smaller then a, or all the eigenvalues are larger than b, where 1/(b-a) is polynomial.

One can view the class BQP of problems efficiently computable on quantum computers in one of two ways: A class of problems captured by a new paradigm of computation built on deep principles of quantum mechanics, or yet another complexity class. As a complexity theorist I wish to explore the latter view.

The success probability of a classical randomized algorithm can be boosted by repetition: If the algorithm succeeds with probability a, then by repeating the algorithm k times, we can increase the probability of success to roughly ka, assuming ka << 1. Intuitively, we can think of this basic strategy as each additional run of the given algorithm boosting the probability of success by an additive amount of roughly a.

Most algorithms in Quantum Computation are developed in the black box setting. This is the setting where we are interested in determining the property of some function f : {0,1}^n → {0,1}. The algorithms are geared to determine this property with as few applications---black-box calls---of f as possible.

Besides their use for efficient computation, quantum computers are a base for studying quantum systems that create valid physical theories using mathematics and physics. An essential part of the validation process for quantum mechanics is the development of a coherent theory of mathematics and quantum mechanics together.

An important problem in classical cryptography consists in finding the weakest assumption for the implementation of some fundamental primitives. One such a primtive is called Zero-Knowledge Arguments which allows a polynomial-time prover to convince a polynomial-time verifier of the validity of some statement without revealing any additional information.

Can quantum mechanics be harnessed to provide unconditionally secure bit commitment schemes and other cryptographic primitives beyond key distribution? This was believed possible for several years until Mayers came along with his proof that the "provably" secure BCJL bit commitment scheme was fatally flawed.

Quantum cryptography potentially allows the ability to distribute keys in an information-secure way, which is beyond the abilities of classical cryptography. Security of quantum key distribution against sophisticated attacks is among the most important issues in quantum information theory. In this talk we present the basics of quantum key distribution and discuss its security against collective and joint attacks.

Quantum physics tells us that, in principle, one can manipulate quantum bits (two-level systems, now called simply qubits). One can store them and send them, initialize and measure their state, transform their state, each one alone, or a few together. Unfortunately, quantum physics does not tell us how to do these basic operations, and as yet, there is no suggestion of a system where all these steps can be done.