The Antikythera mechanism was probably the world’s first ‘analog computer’ — a sophisticated device for calculating the motions of stars and planets. This remarkable assembly of more than 30 gears with a differential mechanism, made on Rhodes or Cos in the first century B.C., revised the view of what the ancient Greeks were capable of creating at that time. A comparable level of engineering didn’t become widespread until the industrial revolution nearly two millennia later. This collection of papers provides a good overview of the current state-of-the-art of quantum information science. We do not know how a quantum Antikythera will look like but all we know is that the best way to predict the future is to create it. From the perspective of the future, it may well be that the real computer age has not yet even begun.
Chania, a picturesque little town on the coast of the western Crete, the birthplace of Dimitris Angelakis, the main organizer of this Advanced Study Institute in Quantum Information Science, is only a few miles away from the tiny island of Antikythera. In 1900 a party of sponge-divers were driven by a storm to anchor near the island and there, at a depth of some 40 meters, they found the wreck of an ancient cargo ship. Among the pieces of pottery and marble statutes sprawled on the seabed was a coral-encrusted lump of corroded bronze gear wheels. The Antikythera mechanism, as it is now known, was probably the world's first “analog computer” — a sophisticated device for calculating the motions of stars and planets. This remarkable assembly of more than 30 gears with a differential mechanism, made on Rhodes or Cos in the first century B.C., revised the view of what the ancient Greeks were capable of creating at that time. A comparable level of engineering didn't become widespread until the industrial revolution nearly two millennia later. Thus it is hardly surprising that Richard Feynman, who saw the Antikythera mechanism on display in Athens, called it “nearly impossible”. In one of his letters, reprinted in “What Do You Care What Other People Think?: Further Adventures of a Curious Character”, he wrote
“… Yesterday morning I went to the archaeological museum. … Also, it was slightly boring because we have seen so much of that stuff before. Except for one thing: among all those art objects there was one thing so entirely different and strange that it is nearly impossible. It was recovered from the sea in 1900 and is some kind of machine with gear trains, very much like the inside of a modern wind-up alarm clock. The teeth are very regular and many wheels are fitted closely together…”
It seems likely that the Antikythera tradition of complex mechanical technology was transmitted via the Arab world to medieval Europe where it formed the basis of clockmaking techniques. As such, the Antikythera mechanism is a venerable precursor of mechanical computing devices based on the meshing of metal gears. Indeed, for many years the basic raw material of the computer industry was brass. The 17th century calculators of Wilhelm Schickard, Blaise Pascal and Gottfried Wilhelm Leibniz testify to the importance of gears in the history of computing. When, in 1837, Charles Babbage was tinkering with a design of the first programmable computer, known as the Analytical Engine, he was thinking in terms of rods, gears and wheels.
From gears to relays to valves to transistors to integrated circuits and so on – in the 20th century brass gave way to silicon. Today's advanced lithographic techniques can etch logic gates and wires less than a micron across onto the surfaces of silicon chips. Soon they will yield even smaller components, until we reach the point where logic gates are so small that they consist of only a few atoms each. If computers are to continue to become faster (and therefore smaller), new, quantum technology must replace or supplement what we have now, but it turns out that such technology can offer much more than smaller and faster microprocessors. It can support entirely new modes of computation, with new quantum algorithms that do not have classical analogues.
The very same person who was so fascinated by the ancient Antikythera laid down the foundations of quantum computation. In 1981 Feynman observed that simulations of some quantum experiments on any classical computer appear to involve an exponential slowdown in time as compared to the natural run of the experiment. Instead of viewing this fact as an obstacle, Feynman regarded it as an opportunity. If it requires so much computation to work out what will happen in a complicated quantum experiment then, he argued, the very act of setting up an experiment and measuring the outcome is tantamount to performing a complex computation. After all, any real computation is a physical process, be it classical or quantum. Thus any computation can be viewed in terms of physical experiments which produce outputs that depend on initial preparations called inputs. Since then, the hunt has been on for interesting things for quantum computers to do, and at the same time, for the scientific and technological advances that could allow us to build quantum computers.
The NATO Advanced Study Institute in Chania brought together a number of researchers and students in both experimental and theoretical quantum information science. During lectures and talks, and in numerous discussions over Raki, the participants shared their views on just about everything; from quantum algorithms and intricacies of computational complexity to the finer parts of Cretan cuisine, and from new technologies for realizing quantum computers to the spirit of traditional Greek dances. The knowledge that nature can be coherently controlled and manipulated at the quantum level was perceived as both a powerful stimulus and one of the greatest challenges facing experimental physics. Fortunately the exploration of quantum technology has many staging posts along the way, each of which will yield scientifically and technologically useful results and some of them are described in this volume.
We hope this collection of papers provides a good overview of the current state-of-the-art of quantum information science. We do not know how a quantum Antikythera will look like but all we know is that the best way to predict the future is to create it. From the perspective of the future, it may well be that the real computer age has not yet even begun.
We also wish to thank our sponsors NATO, the Cambridge-MIT Institute, the Union of Agricultural Cooperatives of Kidonia and Kissamos, the Cooperative Bank of Chania, ANEK Lines, Olympic Airways, ABEA Olive Oil Products and Stigmes Magazine. Finally we acknowledge the helpful collaboration from IOS Press in the publication of this volume and also thank Kaija Hampson for being an excellent secretary during the meeting.
Entanglement is one of the most fascinating features of quantum information. In this lecture the focus is on two aspects of the broad field of entanglement theory: first, on methods for the detection or verification of entanglement. Here, the method of Bell inequalities is compared with the tool of witness operators and their local measurement. An overview of other methods such as entropic and uncertainty relations, as well as physical approximations of unphysical maps, will be given. Second, the zoo of multipartite entangled states will be visited, mainly with respect to their usefulness as a resource for a given task. As an example, distributed dense coding is presented.
As a connection between the two main topics, the detection of multipartite entangled states is discussed.
Recently the explicit applicability of bound entanglement in quantum cryptography has been shown. In this paper some of recent results respecting this topic are reviewed. In particular relevant notions and definitions are reminded. A new construction of bound entangled states containing secure correlations is presented. It provides low-dimensional bound entangled states with nonzero distillable key.
Entanglement distillation protocols are generalized for qudits of arbitrary dimension by studying the group of unitary local permutations. We introduce the concept of joint performance parameter η that allows us the comparison of distillation protocols with different values of fidelity, probability of success and number of Bell pairs used altogether.We analyze several distillation protocols assisted with twirling operations as the dimension D of qudits vary. We find that the best performance according to η is not achieved for qubits (D=2), but for qutrits (D=3) and n=3 input pairs of Bell states. We propose and study an extension of the Quantum Privacy Amplification protocols that work for arbitrary dimension D, being more efficient when D is a prime number.
These lectures are devoted to study of separability, entropy and channels in infinite dimensional Hilbert spaces. The first two sections deal with criteria of compactness for subsets in state space and collections of state ensembles. Next a general integral representation for separable states in the tensor product of infinite dimensional Hilbert spaces is given and an example of separable state that is not countably decomposable is provided. The structure theorem for the quantum communication channels that are entanglement-breaking is proved, generalizing the finite-dimensional result of M. Horodecki, Ruskai and Shor. We then discuss (dis)continuity properties of the quantum entropy and relative entropy in the infinite dimensional case. Sufficient conditions for the continuity of the output entropy of a quantum channel and related important entropic quantities are given. In case of compact constraints conditions for existence of optimal ensembles achieving the χ-capacity are given. These results are then applied to Gaussian channels.
I discuss the role that relativistic considerations play in quantum information processing. First I describe how the causality requirements limit possible multi-partite measurements. Then the Lorentz transformations of quantum states are introduced, and their implications on physical qubits are described. This is used to describe relativistic effects in communication and entanglement.
It is well known that all pure entangled bipartite states violate Bell inequalities. When one extends Bell inequalities to multipartite two dimensional states using either the Mermin inequalities or Werner-Wolf-Żukowski-Brukner inequalities, one finds that it is no longer true that all entangled pure states violate these inequalities. We show that it is possible to formulate a set of Bell inequalities for 3-qubit system in such a way that all entangled tripartite states violate it.
We demonstrate the persistence of entanglement at any temperature in a system composed by a cavity field mode interacting with a movable mirror, via radiation pressure coupling. We introduce a new method of analyzing entanglement in mixed states of infinite dimensional systems and identify an important symmetry between a special class of 2 × 2 subspaces of the density matrix.
Lawrence M. Ioannou, Benjamin C. Travaglione, Donny Cheung, Artur K. Ekert
93 - 98
Determining whether a quantum state is separable or entangled is a problem of fundamental importance in quantum information science. It has recently been shown that this problem is NP-hard. There is a highly inefficient 'basic algorithm' for solving the quantum separability problem which follows from the definition of a separable state. By exploiting specific properties of the set of separable states, we introduce a new classical algorithm that solves the problem significantly faster than the 'basic algorithm', allowing a feasible separability test where none previously existed e.g. in 3-by-3-dimensional systems. Our algorithm also provides a novel tool in the experimental detection of entanglement.
We consider an analogue of entanglement-swapping for a set of black boxes with the most general correlations consistent with relativity, and introduce couplers to represent joint measurements. For binary-input/binary-output boxes, we find that no such analogue exists.
A 'register' in quantum information processing is a composition of k quantum systems, 'qudits'. The dimensions of Hilbert spaces for one qudit and whole quantum register are d and dk respectively, but we should have the possibility of preparing arbitrary entangled state of these k systems. Preparation and arbitrary transformations of states are possible with a universal set of quantum gates and for any d, this universal set may consist of gates acting only on single systems and neighbouring pairs. Here, we revisit methods of construction of Hamiltonians for such universal sets of gates and as a concrete new example, we consider the case with qutrits. Quantum tomography is also revisited briefly.
Measurements of quantum systems extract only classical information. The resulting dichotomy between physically real and physically discoverable information underlies many of the most interesting phenomena of quantum theory. One such phenomenon is the capacity of quantum systems to encode information globally such that exhaustive measurement of their parts might not reveal it; this is the problem of local distinguishability. Here we focus on this problem and study simple qubit-based multipartite systems. We prove three results. First, arbitrarily large sets of arbitrarily multipartite states can always be found such that the states are completely mutually nonorthogonal, yet measurements on just one copy suffice to reduce the set of possible states of a system to two. Second, all locally indistinguishable sets of quantum states can be rendered perfectly distinguishable by the addition of just one system in a complementary set of purely nonorthogonal states. Third, sets of orthogonal product states exist that are perfectly LOCC distinguishable, yet only the completely nonorthogonal subsystem must always be measured during successful LOCC protocols.
Possibilities of increasing the critical error rate of quantum key distribution (QKD) protocols are investigated. We consider QKD protocols with discrete alphabets, letters of which form regular polyhedrons on the Bloch sphere (tetrahedron, octahedron, cube, icosahedron, and dodecahedron, which have 4, 6, 8, 12, and 20 vertices respectively) and a QKD protocol with continuous alphabet, which corresponds to the limiting case of a polyhedron with infinite number of vertices. The stability of such QKD protocols against intercept–resend and optimal eavesdropping attacks on the individual information carriers is studied in detail. It is shown that all these QKD protocols have approximately the same critical error rates. In the case of optimal eavesdropping strategies, after basis reconciliation, the QKD protocol with continuous alphabet surpasses all other protocols in terms of noise-resistance. Without basis reconciliation the protocol with the highest critical error rate has a tetrahedron-type alphabet. Additional increase of the dimensionality of the quantum alphabet leads to a further increase of the critical error rate.
In the formalism of measurement based quantum computation we start with a given fixed entangled state of many qubits and perform computation by applying a sequence of measurements to designated qubits in designated bases. The choice of basis for later measurements may depend on earlier measurement outcomes and the final result of the computation is determined from the classical data of all the measurement outcomes. This is in contrast to the more familiar gate array model in which computational steps are unitary operations, developing a large entangled state prior to some final measurements for the output. Two principal schemes of measurement based computation are teleportation quantum computation (TQC) and the so-called cluster model or one-way quantum computer (1WQC). We will describe these schemes and show how they are able to perform universal quantum computation. We will outline various possible relationships between the models which serve to clarify their workings. We will also discuss possible novel computational benefits of the measurement based models compared to the gate array model, especially issues of parallelisability of algorithms.
I give an overview of the basic concepts behind quantum error correction and quantum fault tolerance. This includes the quantum error correction conditions, stabilizer codes, CSS codes, transversal gates, fault-tolerant error correction, and the threshold theorem.
We describe the formalism of gate level simulation in higher dimensional encoding systems. Furthermore, we introduce efficient error–correcting codes for such systems and use coding theory to test the error prevention in prime bases. By making extensive use of quantum Fourier transforms, we simulate open quantum systems and benchmark the efficiency of the error–correcting algorithm using the QCHBS package . Numerical simulations indicate greater stability of prime base encoding systems.
We investigate bipartite entanglement in a class of multiparty quantum states, the G-states, constructed from a group G, and we derive an expression for the von Neumann entropy. We show that for a special subset of such states, the G-homogeneous states, the entropy satisfies the area law. If G is a group of spin-flips, the G-homogeneous states are locally equivalent to 2-colorable graph states (e.g., n-GHZ, cluster states, etc). The advantage of our representation is a more compact description of these states in terms of a group of spin-flips G. As an example, we compute the n-tangle τn for 2-colorable graph states.
We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods , which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern with high probability in queries, where N is the size of the string. The analysis and quantum circuit construction of our algorithm are presented in .
We compare the worst-case performance of quantum fingerprinting strategies under the one-way communication model to that of classical strategies when the error is one-sided. Bounds on the classical worst-case error probability are reported, while quantum strategies surpassing these bounds are constructed from spherical codes, equiangular tight frames and mutually unbiased bases.
Markus Popp, Frank Verstraete, Miguel Angel Martin-Delgado, Ignacio Cirac
191 - 217
We present here an introduction to the concept of localizable entanglement (LE). It is defined as the maximum entanglement that can be localized, on average, between two parties of a multipartite system by performing local measurements on the remaining parties. This entanglement measure leads naturally to notions like entanglement length and entanglement fluctuations. For both spin-1/2 and spin-1 systems we prove that the LE of a pure quantum state can be lower bounded by connected correlation functions. We further propose a scheme, based on matrix-product states and the Monte Carlo method, to efficiently calculate the LE for quantum states of a large number of spins. The virtues of LE are illustrated for various spin models. In particular, characteristic features of a quantum phase transition such as a diverging entanglement length can be observed. We also give examples for pure quantum states exhibiting a diverging entanglement length but finite correlation length. We have numerical evidence that the ground state of the antiferromagnetic spin-1 Heisenberg chain can serve as a perfect quantum channel. Furthermore, we apply the numerical method to mixed states and study the entanglement as a function of temperature.
Daniel Burgarth, Vittorio Giovannetti, Sougato Bose
218 - 237
We present a communication protocol for chains of permanently coupled qubits which achieves perfect quantum state transfer and which is efficient with respect to the number chains employed in the scheme. The system consists of M uncoupled identical quantum chains. Local control (gates, measurements) is only allowed at the sending/receiving end of the chains. Under a quite general hypothesis on the interaction Hamiltonian of the qubits a theorem is proved which shows that the receiver is able to asymptotically recover the messages by repetitive monitoring of her/his qubits. We show how two parallel Heisenberg spin chains can be used as quantum wires. Perfect state transfer with a probability of failure lower than P in a Heisenberg chain of N spin-1/2 particles can be achieved in a timescale of the order of . We demonstrate that our scheme is more robust to decoherence and non-optimal timing than any scheme using single spin chains. Arbitrarily perfect state transfer is even possible in the presence of random fluctuations in the couplings of a quantum chain. The scheme performs well for both spatially correlated and uncorrelated fluctuations if they are relatively weak (say 5%).
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com