Edge 173

Home

About Edge

Features

Edge Editions

Press

Edge Search

Subscribe

Edge 173— November 14, 2005
(3,200 words)

THE $100,000 EDGE OF COMPUTATION SCIENCE PRIZE

For individual scientific work, extending the computational idea, performed, published, or newly applied within the past ten years.

David Deutsch

Recipient of the 2005
$100,000 Edge of Computation Science Prize

DAVID DEUTSCH is the founder of the field of quantum computation. Paul Benioff, Richard Feynman, and others had written about the possibility of quantum computation earlier, but Deutsch's 1985 paper on Quantum Turing Machines was the first full treatment of the subject, and the Deutsch-Jozsa algorithm is the first quantum algorithm.

When he first proposed it, quantum computation seemed practically impossible. But the last decade has seen an explosion in the construction of simple quantum computers and quantum communication systems. None of this would have taken place without Deutsch's work.

The nominating essay is reproduced in part below.

Although the general idea of a quantum computer had been proposed earlier by Richard Feynman, in 1985 David Deutsch wrote the key paper which proposed the idea of a quantum computer and initiated the study of how to make one. Since then he has continued to be a pioneer and a leader in a rapidly growing field that is now called quantum information science.

Presently, small quantum computers are operating in laboratories around the world, and the race is on to find a scalable implementation that, if successful, will revolutionize the technologies of computation and communications. It is fair to say that no one deserves recognition for the growing success of this field more than Deutsch, for his ongoing work as well as for his founding paper. Among his key contributions in the last ten years are a paper with Ekert and Jozsa on quantum logic gates, and a proof of universality in quantum computation, with Barenco and Ekert (both in 1995).

One reason to nominate Deutsch for this prize is that he has always aimed to expand our understanding of the notion of computation in the context of the deepest questions in the foundations of mathematics and physics. Thus, his pioneering work in 1985 was motivated by interest in the Church-Turing thesis. Much of his recent work is motivated by his interest in the foundations of quantum mechanics, as we see from his 1997 book.

ABOUT DAVID DEUTSCH

The main papers written by Deutsch that contained "achievement in scientific work that embodies extensions of the computational idea" were in 1985 ("Quantum theory, the Church-Turing principle, and the universal quantum computer") and 1989 ("Quantum computational networks").

His 1995 paper, "Conditional quantum dynamics and logic gates" (with A. Barenco, A. Ekert and R. Jozsa) was an important step in clarifying what sort of physical processes would be needed to implement quantum computation in the laboratory, and what sort of things the experimentalists should be trying to get to work.

"Universality in quantum computation", also written in 1995 (with A. Barenco and A. Ekert) proved the universality of almost all 2-qubit quantum gates, thus verifying his conjecture made in 1989 and showing that quantum computation and quantum gate operations are 'built in' to quantum physics far more deeply than classical physics. In 1996, in "Quantum privacy amplification and the security of quantum cryptography over noisy channels" (with A. Ekert, R. Jozsa, C. Macchiavello, S. Popescu and A. Sanpera), he brought quantum cryptography a little bit closer to being practical as opposed to just a laboratory curiosity.

His recent work as seen in the following three papers can be seen as new "applications" of the computational idea, rather than extensions of it.

In 2000, "Information Flow in Entangled Quantum Systems" (with P. Hayden) refutes the long-held belief that quantum systems contain 'non-local' effects, and it does it by appealing to the universality of quantum computational networks, and analysing information flow in those.

Also in 2000, in "Machines, Logic and Quantum Physics" (with A. Ekert and R. Lupacchini), a philosophic paper, not a scientific one, he appealed to the existence of a distinctive quantum theory of computation to argue that our knowledge of mathematics is derived from, and is subordinate to, our knowledge of physics (even though mathematical truth is independent of physics).

In 2002, he answered several long-standing questions about the multiverse interpretation of quantum theory in "The Structure of the Multiverse" — in particular, what sort of structure a 'universe' is, within the multiverse. It does this by using the methods of the quantum theory of computation to analyse information flow in the multiverse.

His two main lines of research at the moment , qubit field theory and quantum constructor theory, may well yield important extensions of the computational idea eventually, but at the moment neither of them has yielded any results at all, to speak of, only promising avenues of research.

Born in Haifa, Israel, David Deutsch was educated at Cambridge and Oxford universities. After several years at the University of Texas at Austin, he returned to Oxford, where he now lives and works. Since 1999, he has been a non-stipendiary Visiting Professor of Physics at the University of Oxford, where he is a member of the Centre for Quantum Computation at the Clarendon Laboratory, Oxford University.

In 1998 he was awarded the Institute of Physics' Paul Dirac Prize and Medal. This is the Premier Award for theoretical physics within the gift of the Council of the Institute of Physics. It is made for “outstanding contributions to theoretical (including mathematical and computational) physics”. In 2002 he received the Fourth International Award on Quantum Communication for “theoretical work on Quantum Computer Science”.

He is the author of The Fabric of Reality [1997].

References:

"Quantum Theory, The Church-Turing Principle, and the Universal Quantum Computer," Proc. Roy. Soc. London A400, 97-117 (1985)

" Quantum computational networks" Proceedings of the Royal Society of London A425:73-90. (1989)

"Conditional quantum dynamics and logic gates" (with A. Barenco, A. Ekert and R. Jozsa) Phys. Rev. Lett. 74 4083-6 (1995)

"Universality in quantum computation" (with A. Barenco and A. Ekert) Proc. R. Soc. Lond. A449 669-77 (1995)

"Quantum privacy amplification and the security of quantum cryptography over noisy channels" (with A. Ekert, R. Jozsa, C. Macchiavello, S. Popescu and A. Sanpera) Phys. Rev. Lett. 77 2818-21 (1996)

"Information Flow in Entangled Quantum Systems" (with P. Hayden) Proc. R. Soc. Lond. A456 1759-1774 (2000)

"Machines, Logic and Quantum Physics" (with A. Ekert and R. Lupacchini) Bulletin of Symbolic Logic 3 3 (2000)

"The Structure of the Multiverse" Proc. R. Soc. Lond.A458 2028 2911-23 (2002)

David Deutsch's Edge bio page

Further reading on Edge:
"It's Much Bigger Than It Looks" - A talk with David Deutsch

Beyond Edge:
David Deutsch's Home Page
Lectures on Quantum Computation
Centre for Quantum Computation

ABOUT THE EDGE OF COMPUTATION SCIENCE PRIZE

The Prize, established by Edge Foundation, Inc., is a $100,000 prize initiated and funded by science philanthropist Jeffrey Epstein.

The Prize recognizes individual achievement in scientific work that embodies extensions of the computational idea — the design space created by Turing. It is a 21st Century prize in recognition of cutting edge work — theoretical, experimental, or both — performed, published, or newly applied within the past ten years.

The most significant developments in the sciences today (i.e. those that affect the lives of everybody on the planet) are about, informed by, or implemented through advances in software and computation.

Metaphors of information processing and computation are at the center of today's intellectual action, and a new and unified language of science is beginning to emerge. Concepts of information and computation have infiltrated a wide range of sciences, from mathematics, physics and cosmology, to cognitive psychology, to evolutionary biology, to genetic engineering. Such innovations as the binary code and the algorithm have been applied in ways that reach far beyond the programming of computers, and are being used to understand such mysteries as the origins of the universe, the operation of the human body, and the working of the mind.

These are the areas of exploration that have been central to Edge, transcending the more narrowly-defined academic field of computer science. The Edge community is about people who have some connection with computer science but have much broader interests and activities.

Nominators were not allowed to nominate themselves, but in some cases they were nominated by others. Some individuals were nominated more than once by different nominators. The judges, who were also nominators, were anonymous, and were ineligible for the Prize in the event they were nominated. Jeffrey Epstein, the donor of the Prize, was not a judge.

The judges, nominators, and nominations are listed below. The judging began on November 8th and ended on November 12th.

As to the future of the Prize, Jeffrey Epstein stated:

"I am looking forward to next year...as The Edge of Computation Science Prize encourages more recognition for the science that will bring greatest sea change in the world and in our lives in the next twenty years."

— JB

Judges

Rodney A. Brooks, Daniel C. Dennett, Freeman Dyson, George Dyson, W. Daniel Hillis, Seth Lloyd, Marvin Minsky, Nathan Myhrvold, Charles Simonyi, Anton Zeilinger

Nominators

Alun Anderson, Chris Anderson, Thomas A. Bass, Patrick Bateson, Stewart Brand, Rodney Brooks, Andy Clark, Paul Davies, Daniel C, Dennett, David Deutsch, Freeman Dyson, George Dyson, Edward Feigenbaum, Neil Gershenfeld, Beatrice Golomb, Marc D. Hauser, W. Daniel Hillis, Steve Jurvetson, Eric Kandel, George Lakoff, Jaron Lanier, Armand Leroi, Seth Lloyd, Marvin Minsky, Nathan Myhrvold, Jordan Pollack, Carolyn Porco, Steven Quartz, Dan Rockmore, Douglas Rushkoff, Terrence Sejnowski, Michael Shermer, Clay Shirky, Charles Simonyi, Lee Smolin, Maria Spiropulu, Tom Standage, Nassim Taleb, Joseph Traub, J. Craig Venter, Dan Wegner, Anton Zeilinger

Nominations

LAURENCE F. ABBOTT, for using mathematical modeling to study the neural networks that are responsible for our actions and behaviors.

DAVID H. BAILEY (Peter Borwein, and Simon Plouffe), for their 1997 work on the BBP algorithm, an exact computation of any digit of PI without computing previous digits.

CHARLES H. BENNETT, (1) for his many ongoing contributions to the physics of information, including reversible computation, quantum cryptography, quantum teleportation, and quantum communication theory; (2) for his dramatic extension of Rolf Landauer's observation that bit erasure necessarily dissipates kT ln 2 energy from the loss of information; and launching both the theoretical and experimental study of quantum information through his central role in the discovery of quantum cryptography.

PETER J BENTLEY for "Digital Gardening" — taking the first steps in creating the new science of digital horticulture...by allowing programs to evolve and grow instead of being designed.

TIM BERNERS-LEE for inventing hypertext and for realizing the first browser, the World Wide Web, and the first internet server NeXSTEP.

CYNTHIA BREAZEAL, for designing sociable robots that humans will accept as one of their own.

SERGEY BRIN, For achieving practical scaling in social software.

GREGORY CHAITIN, for extraordinary insights into the nature of mathematical truth, building on the seminal work of Kurt Gödel and Alan Turing.

NOAM CHOMSKY, for the minimalist program, explaining language as an optimal solution to the interface between sound and meaning.

MARTIN DAVIS, gatekeeper of computability.

DAVID DEUTSCH, (1) for expanding our understanding of the notion of computation in the context of the deepest questions in the foundations of mathematics and physics; (2) for the enormous potential of quantum computing in studying the architecture of the brain.

J. DOYNE FARMER & NORMAN H. PACKARD, for their work at the forefront of the sciences of prediction.

IAN FOSTER, for developing advanced distributed computing ("Grid") technologies, computational science efforts applying these tools to problems in areas ranging from the analysis of data from physics experiments to remote access to earthquake engineering facilities, and the Globus open source Grid software project.

EDWARD FREDKIN , for his seimnal and pioneering work in the field of cellular automata.

DAVID GEDYE, the computer scientist who co-conceived of SETI@home, the distributed computing effort for finding extraterrestrial intelligence.

DAVID GELERNTER, for fundamental contributions to both the technical and cultural sides of computation. He continues to expand our knowledge of parallel computation and the nature of the human experience of information technology.

DAVID HAUSSLER, for pioneering work in the fields of computational learning theory and bioinformatics, and for establishing strong and productive interdisciplinary interactions between computer scientists and molecular biologists.

JEFF HAWKINS, for advancing AI research and Brain research by proposing the first plausible common cortical algorithm: the hierarchical temporal predictive memory.

JOHN HOLLAND, for genetic algorithms, which not only demonstrate the creative power of the basic Darwinian algorithmic process, but provide a fundamental engine to drive the vehicles now beginning to explore the space of software applications whose designs can evolve without further intervention by software engineers.

JOE JACOBSON, for creating the e-ink display system, for fundamental work in molecular machines, quantum computing, among many other very important research areas.

BREWSTER KAHLE, for his pioneering efforts in online publishing, search engines and the archiving of the World Wide Web.

STUART KAUFFMAN, for work on the dynamical-computational foundations of cell biology.

HIROAKE KITANO, for seminal work in genetic algorithms, artificial life and multi-agent systems before pioneering and leading the field of computational systems biology and establishing two ERATO laboratories.

JARON LANIER, for being a fountain of creativity, a voice defining a new digital humanism, and an exceedingly useful contrarian.

SETH LLOYD, for turning quantum computers from dream into device.

BENOIT MANDELBROT, for developing the multi-fractal theory for times series.

NORMAN MARGOLUS, for the invention of reversible cellular automata and for the Margolus-Levitin theorem, the fundamental physical limit for the speed of computation.

READ MONTAGUE, for creating a new computational architecture of mind, value computing, that underlies a revolution in our understanding of humans.

GENE MYERS, for his work in leading the team for algorithm development that enabled large eukaryotic genomies to be sequences by the using the whole genome shotgun technique.

SRINIVAS NARAYANAN, for the development of executing schemas, a major advance in neural computation that has permitted the contemporary neural theory of language to come into being.

DONALD NORMAN, for exploring and extending the complex space limned by computation on one side and design and enjoyment on the other.

CHARLES A. OFRIA, for the experimental study of digital organisms to improve our understanding of how natural evolution works.

LARRY PAGE, for having the right idea at the right time and best extending computation into the real world. Inside the last decade, no one else even comes close for impact

ERIC PAULOS, for pushing the boundaries of technology as human extension in tele-robotics, atmosphere, communications, and feedback mechanisms.

JORDAN POLLACK, for pioneering physical instantiations of deeply adaptive systems.

THOMAS S. RAY, for pioneering the computer simulation of evolution of populations of living
creatures in an evolving ecosystem.

LARRY ROBERTS for the design, initiation, planning and development of the world's first major packet network, now called the Internet.

EHUD SHAPIRO, for building a molecular Turing machine that works.

PETER SHOR, for his discovery of revolutionary algorithms for quantum computation, which will hasten the day when this fundamentally new mode of computation becomes practicable.

LARRY SMARR, for prototyping the information infrastructure of the 21st Century.

RAYMOND SOLOMONOFF, for inventing the modern theory called "Algorithmic Complexity," which was later developed by Kolmogoroff and Chaitin.

J. CRAIG VENTER, (1) for reengineering the information systems of biology and pioneering the field of synthetic genomics; (2) whose work is (a) outstandingly important, (b) intellectually exciting, and (c) based on advances in information processing in addition to advances in chemical hardware; (3) for the shotgun sequencing technique, which revolutionized genetic analysis and thus biology and medicine.

GEORGE VON DASSOW, for providing the first working model of a real genetic network, thereby demonstrating that the embryo is computable.

JACK WISDOM, for illuminating, through his seminal work in both analytical and computational celestial dynamics, the role that dynamical chaos plays in the long-term evolution of the solar system, with far-reaching consequences for a diverse range of topics including the evolution of climate, the possibility of life on Mars, and the origin of life on Earth.

STEPHEN WOLFRAM, (1) for three seminal contributions: (a) pioneering the study of complexity and complex systems; (b)developing the programming software (Mathematica) that changed the manner in which much of computational science is conducted; (c) developing the case for Computation Science in A New Kind of Science; (2) for asking what the very simplest programs actually do — and establishing their systematic study as a field of basic science.