Quantum Networking E-Book

Rodney Van Meter

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 561

Veröffentlichungsjahr: 2014

Beschreibung

Quantum networks build on entanglement and quantum measurement to achieve tasks that are beyond the reach of classical systems. Using quantum effects, we can detect the presence of eavesdroppers, raise the sensitivity of scientific instruments such as telescopes, or teleport quantum data from one location to another. Long-distance entanglement can be used to execute important tasks such as Byzantine agreement and leader election in fewer rounds of communication than classical systems, improving the efficiency of operations that are critical in distributed systems.

Leseprobe

Table of Contents

Notations

Acknowledgments

Introduction

Chapter 1. Overview

1.1. Introduction

1.2. Quantum information

1.3. Quantum repeaters

1.4. Network architectures

1.5. Conclusions

PART 1: Fundamentals

Chapter 2. Quantum Background

2.1. Introduction

2.2. Schrödinger’s equation

2.3. Qubits

2.4. Manipulating qubits

2.5. Bell pairs

2.6. The no-cloning theorem

2.7. Conclusion

Chapter 3. Networking Background

3.1. Concepts

3.2. Challenges in scaling up networks

3.3. Design patterns

3.4. The Internet

3.5. Conclusion

Chapter 4. Teleportation

4.1. The basic teleportation operation

4.2. Experimental demonstration of teleportation

4.3. State machines for teleportation

4.4. Teleporting gates

4.5. Conclusion

PART 2: Applications

Chapter 5. Quantum Key Distribution

5.1. QKD and the purpose of cryptography

5.2. BB84: single-photon QKD

5.3. E91: entanglement-based protocol

5.4. Using QKD

5.5. Existing QKD networks

5.6. Classical control protocols

5.7. Conclusion

Chapter 6. Distributed Digital Computation and Communication

6.1. Useful distributed quantum states

6.2. Coin flipping

6.3. Leader election

6.4. Quantum secret sharing

6.5. Byzantine agreement

6.6. Client-server and blind computation

6.7. Conclusion

Chapter 7. Entangled States as Reference Frames

7.1. Qubits in the environment

7.2. Distributed clock synchronization

7.3. Very long baseline optical interferometry

7.4. Conclusion

PART 3: Lines of Repeaters

Chapter 8. Physical Entanglement and Link-Layer Protocols

8.1. Creating entanglement using light

8.2. Memory and transceiver qubits

8.3. Link structure

8.4. State machines and protocol interactions

8.5. Managing density matrices in distributed software

8.6. Examples

8.7. Conclusion

Chapter 9. Purification

9.1. Measurement revisited

9.2. Basic purification

9.3. Scheduling purification

9.4. State machines and protocol interactions

9.5. More complex purification protocols

9.6. Experimental demonstrations

9.7. Conclusion

Chapter 10. Purification and Entanglement Swapping-Based Repeaters

10.1. Hardware architectures

10.2. Getting from here to there

10.3. Nested purification session architecture

10.4. State machines and protocol interactions

10.5. Putting it all together

10.6. Considerations in the design of a simulator

10.7. Conclusion

Chapter 11. Quantum Error Correction-Based Repeaters

11.1. Quantum error correction

11.2. CSS repeaters

11.3. Surface code repeaters

11.4. Conclusion

Chapter 12. Finessing the Key Limitations

12.1. Quasi-asynchronous

12.2. Memoryless

12.3. Summary: comparing quantum communication approaches

12.4. Conclusion

PART 4: Networks of Repeaters

Chapter 13. Resource Management and Multiplexing

13.1. Simulated network and traffic

13.2. Simulations

13.3. Conclusion

Chapter 14. Routing

14.1. Introduction

14.2. Difficulties: differences between quantum and classical networks

14.3. Problems and solutions

14.4. Simulation and results

14.5. Conclusion

Chapter 15. Quantum Recursive Network Architecture

15.1. Review: network architecture

15.2. Recursive quantum requests

15.3. Implementing recursion in quantum networks

15.4. Example

15.5. Conclusion

Chapter 16. Coda

16.1. Future development

16.2. Open problems

16.3. Further readings for depth

16.4. Further readings for breadth

16.5. Final thoughts

Bibliography

Index

For my first teachers: my parents

First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2014The rights of Rodney Van Meter to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014934407

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-537-5

Notations

Acknowledgments

As no better man advances to take this matter in hand, I hereupon offer my own poor endeavours. I promise nothing complete; because any human thing supposed to be complete, must for that very reason infallibly be faulty.

Herman Melville, Moby Dick   

I owe more than I can say to my wife Mayumi and daughters Sophia and Esther. They have been patient throughout the writing of this book, accepting, “Sorry, I have to work on the book”, as an excuse for everything from missing a soccer match to skipping my share of the housework. I love you three beyond all words.

My parents Doyle and Linda and sisters Sheila and Lera and their families have also been incredibly supportive. Lera’s almost daily words of encouragement kept me going.

To borrow a phrase from Charlie Parker, Thaddeus Ladd is the other half of my heart. Without his patient teaching and guidance on the physics, in all probability I would not have been able to complete much of the research upon which my own share of the ideas in this book is founded, or even fully understand the impact of the giants of the field whose work I also attempt to explain here. I hope I have been able to return the favor at least in part by teaching him about systems and networks.

Besides Thaddeus, I owe a debt to Kohei Itoh, Mikio Eto, Eisuke Abe, Kae Nemoto, Bill Munro, Austin Fowler, Simon Devitt, Clare Horsman and Yoshihisa (Yoshi) Yamamoto for teaching me most of what I know about quantum information. The Core Research for Evolutionary Science and Technology (CREST) and Funding Program for World-Leading Innovative R&D on Science and Technology (FIRST) Quantum Summer Schools organized and taught by Yamamoto, Tarucha, Koashi, Nakamura, Tsai, Takeuchi, Imoto, Nemoto, Chuang, Wineland, Jozsa and others were immensely valuable; each time I attended, I learned a year’s worth of new material.

For showing the way, being smart, or otherwise being inspirational: Ron Ayres, Charlie Bennett, Richard Feynman, Ed Stone and Wook.

For additional personal support on this book and related projects: Fred Baker, Thomas Clausen, Chip Elliott, Dave Farber, Bob Hinden, Kohei Itoh, Seth Lloyd, Paul Mockapetris, Jun Murai, Timo Jokiaho, Wook, Suzanne Woolf and Yoshi Yamamoto.

The first person I should thank with respect to the book itself is Marcelo Dias de Amorim, for suggesting this book in the first place, when we met at our semi-annual WIDE Camp in September 2012. The staff at ISTE have done an excellent job of keeping me at least somewhat on track; without them, the book would never have been finished.

For reviewing the book as a fairly complete entity, even as it was evolving: Kilnam Chon and Bill Manning. Shigeya Suzuki deserves a special mention for actually working on some of these topics in parallel with the development of the book; his patience as I said, “I think that’s in the book… oh, wait, give me a day to write that…” in answer to many of his questions was extraordinary.

For reviewing parts of the book: Luciano Aparicio, Andi Frischknecht, Akira Furusawa, Jim Harrington, Thaddeus Ladd, Shota Nagayama, Sam Pottle, Yutaka Shikano, Shigeki Takeuchi, Seiichiro Tani, Todd Tilma, Joe Touch, Yidun Wan and Hideaki Yoshifuji.

For other advice on history and recent experimental work: Romain Alléaume, Thaddeus Ladd and Peter McMahon. For tidbits on radio interferometry: Min Yun.

For contributing to my modest share of the research covered in this book, and graciously allowing me to reuse large portions of several of our joint papers: Luciano Aparicio, Mourad Beji, Chia-Hung Chien, Byung-Soo Choi, Clare Horsman, Kaori Ishizaki, Hiroyuki Kusumoto, Thaddeus Ladd, Iori Mizutani, Bill Munro, Koji Murata, Shota Nagayama, Kae Nemoto, Takahiko Satoh, Shigeya Suzuki, Joe Touch, Jaw-Shien Tsai and Fumiki Yoshihara.

For photos and diagrams: Romain Alléaume, Chip Elliott, Akira Furusawa, Masahide Sasaki and Hajime Tazaki. Takaaki Matsuo and Shota Nagayama stepped in at the last minute and drew a stack of figures for the book.

Ultimately, I should thank the students in my Advancing Quantum Architecture (AQUA) “kenkyuukai” (research group) and my quantum information processing class, and the Murai Lab students and faculty in general, for bearing with me as I learned how to explain quantum computing and networking to classical systems folks.

My own share of the research presented here has been supported by three Kakenhi grants (21500020, 24102706, 25282197) from the Japan Society for the Promotion of Science (JSPS), including one through the Quantum Cybernetics program. This project has been made possible in part by a gift from the Cisco University Research Program Fund, a corporate advised fund of the Silicon Valley Community Foundation. This research is supported by the Cabinet Office, Government of Japan and the Japan Society for the Promotion of Science (JSPS) through the Funding Program for World-Leading Innovative R&D on Science and Technology (FIRST Program). My collaborators have been supported by the Ministry of Education, Culture, Sports, Science and Technology (MEXT) and the National Institute of Information and Communications Technology (NICT) in Japan, and the National Science Foundation (NSF) and other agencies in the United States. The generous and unrestricted support provided by the sponsors of the WIDE Project has enabled some of these collaborations. Thomas Clausen hosted me as a visiting professor in March 2011, as I got my start writing what would eventually become a string of survey and architecture papers that culminate in this book.

Although I have benefited immensely from the advice of a number of people who are more expert than me in many of the subfields covered in this book, I bear the ultimate responsibility for the contents; any misrepresentations of history, let alone actual technical mistakes, are my own. Comments are welcome; in this digital age, the print form of the first edition of a book is hardly the last word. I look forward to hearing from you.

This book consists in part of previously published material, used by permission of the copyright holders ACM, IEEE, National Institute of Informatics, SPIE and Springer. The material appeared in the following papers:

– APARICIO L., VAN METER R., “Multiplexing schemes for quantum repeater networks”, Proceedings of the SPIE, vol. 8163, pp. 816308, August 2011.

– APARICIO L., VAN METER R., ESAKI H., “Protocol design for quantum repeater networks”, Proceedings of Asian Internet Engineering Conference, November 2011.

– VAN METER R., LADD T.D., MUNRO W.J., et al., “System design for a long-line quantum repeater”, IEEE/ACM Transactions on Networking, vol. 17, no. 3, pp. 1002–1013, June 2009.

– VAN METER R., TOUCH J., HORSMAN C., “Recursive quantum repeater networks”, Progress in Informatics, no. 8, pp. 65–79, March 2011.

– VAN METER R., SATOH T., LADD T.D., et al., “Path selection for quantum repeater networks”, Networking Science, vol. 3, no. 1–4, pp. 82–95, December 2013.

– VAN METER R., HORSMAN C., “A blueprint for building a quantum computer”, Communications of the ACM, vol. 53, no. 10, pp. 84–93, October 2013.

Some of the material appeared in my PhD thesis, “Architecture of a quantum multicomputer optimized for Shor’s factoring algorithm,” Graduate School of Science and Technology, Keio University, 2006.

Rodney VAN METERFaculty of Environment and Information StudiesKeio UniversityMarch 2014

Introduction

We are going to need a quantum Internet, and to build it, we need quantum internetworking technology. This book is my contribution to both the technical and social work of getting there. It is based on my experiences during 15 years of work on classical computing systems and networks, followed by a decade of research on quantum computing systems and networks.

Quantum information, including both quantum computing and quantum communication, is poised to have a large and sustained impact on the fields of theoretical and experimental quantum physics, theoretical computer science (or informatics) and ultimately the information technology industry. One important subfield is quantum networking, especially using quantum repeaters, which are the focus of this tome. Quantum signals are weak and very fragile, and, in general, cannot be copied or amplified. Engineering quantum communication sessions that can reliably exchange data over long distances, in topologically complex networks built on heterogeneous technologies and managed by many independent organizations, requires an extraordinarily broad range of expertise, which few individuals anywhere have in toto. Over the next 300 or so pages, we will attempt to lay a common foundation on which each person can erect his or her contribution.

The primary audience of the book is two-fold:

– computer networking folks with no prior background in quantum information, who are curious and considering working in the field;

– quantum information experts who have yet to work in the area of repeaters and need an introduction, or those who have begun working in the area but need more background in networks.

Ideally, the book will produce a “meeting of minds” between the two communities. Networkers will find that quantum networking is less intimidating than it initially appears, and that there are breathtaking concepts underlying an emerging class of uses for distributed quantum information. Physicists will discover that networks are complex, artificial artifacts with emergent behaviors not immediately anticipated from the behavior of individual building blocks, and are built on some principles that are every bit as fundamental and beautiful as those they have been studying in physics. By the end of the book, readers from either community should be prepared to design a quantum repeater network, based on both classical network architecture and the existing literature on quantum repeaters. Readers should know enough to implement simulations of repeater networks that properly take into account (1) a reasonable abstraction of the physics, (2) the distributed, autonomous nature of decision-making and (3) the technical and operational heterogeneity of networks of networks such as the Internet.

The book is intended to be a readable introduction rather than a comprehensive, in-depth tome; each chapter is 10–20 pages, intended to be ingested in one sitting. Most chapters will use only basic linear algebra and probability theory. The approach emphasized throughout the book will be on the use of classical networking principles to build a sustainable, extensible, robust quantum repeater network architecture.

The overall flow of the book is an overview, three chapters on background (quantum information, networking concepts and teleportation), then three chapters on applications (QKD, distributed digital computation and entangled states as reference frames) to motivate the development of networking technology. In Part 3 of the book, the focus first shifts to the bottom of the stack, beginning with the physical entanglement experiments and link design. After working through purification, we come to the three major classes of communication session architecture for chains of quantum repeaters: the original entanglement swapping approach, the more recent error correction based approaches, and the recent work on asynchronous approaches. The book ends with a series of chapters on issues in multi-user, autonomous networks: multiplexing, routing and internetworking architecture, featuring the Quantum Recursive Network Architecture (QRNA).

The reader will find varying levels of mathematical and logical rigor in different chapters. In particular, a thorough discussion of physical implementations would fill a separate book, which we leave to the physicists. Likewise, at the highest level, the details of the security protocols and proofs for applications such as verifiable secret sharing are beyond the scope of this book; the applications are presented in just enough depth that casual readers will be able to understand why they are valuable, and what demands they make on the network itself.

Readers are assumed to be familiar with basic vector and matrix addition, multiplication and calculation of the determinant; exponentiation of matrices; complex numbers, including their exponentiation; and discrete probability. The mathematics presented here does not go beyond this level. Thus, although the concepts presented here are largely unfamiliar, abstract and sometimes counter-intuitive, the math itself is generally not particularly difficult. Chapter 2 includes explicit, worked examples of many of the mathematical principles. It is even possible for well-prepared first- and second-year undergraduates to work through the book.

For the advanced researcher, it is worth noting that this book lies halfway between the research monograph and the textbook on the spectrum. In the course of writing what I thought would be a relatively cut-and-dried presentation of some basics viewed from the point of view of a network engineer, I discovered a number of things that simply have not yet been done in the literature. Among them:

– distributed density matrix management (section 8.5);

– the “valley fold” timing for quasi-asynchronous repeaters (section 12.1);

– a moderately detailed analysis of network workloads imposed by applications of repeaters (Chapter 6);

– extended state machine-based designs for protocols.

Each of these likely will be a journal paper, perhaps more or less concurrent with the appearance of the book, but all but the last had their genesis in this writing project. (We began the state machine approach in a conference paper [APA 11b], but the book contains new material.) Each of these topics also deserves yet more attention than I have so far been able to give. I look forward to handing them off to my capable collaborators.

Chapter 1

Overview

“Teleportation” is a magic word, exotic and evocative, but it has been appearing in serious technical literature with increasing frequency. Both theoretically fascinating and experimentally demonstrated, teleportation is the key to quantum networks [GIS 07, KIM 08]. When used in discussions about quantum information, teleportation refers not to Captain Kirk stepping into a machine on the starship Enterprise, dissolving and reappearing on a planet’s surface, but to an operation in which a quantum variable dissolves here and reappears there, on a different physical device. Only the quantum state moves; the electron or other physical device remains where it was, and the receiver can in fact be a very different form of physical device than the sender. The quantum state is destroyed at the sender in the process.

Classical networks communicate by physically copying data and transmitting the copy, but the rules of quantum mechanics forbid the creation of independent copies of an unknown, arbitrary quantum state. Instead of risking the loss of valuable, fragile quantum data by directly transmitting our only copy, networks will prepare generic states that are used to teleport data or to perform teleportation-derived operations on the data.

Quantum networks bring new capabilities to communication systems. Quantum physical effects can be used to detect eavesdropping, to improve the shared sensitivity of separated astronomical instruments or to create distributed states that will enable numerical quantum computation over a distance using teleportation. Quantum communication is the exchange of quantum states over a distance, generally requiring the support of substantial classical communication.

The quantum states that are exchanged may be “standalone” states, an individual element of quantum data. They may also be part of a larger quantum state, spanning devices or even network nodes in a way no shared classical state can. These latter states we refer to as entangled states, which we will study extensively in this book.

Applications running on classical computers will use these quantum states to accomplish one of the above tasks. The classical computer is connected to a quantum device, which may do no more than measure the quantum states to find a classical value (such as a bit of a secret key), or may store them for use in more complex quantum computers. A classical computer will treat a quantum computer as a type of coprocessor; likewise, the classical computer will see the quantum network through the eyes of a separate device.