Riley Tipton Perry - Quantum Computing from the Ground Up

Quantum Computing
from the Ground Up Quantum Computing
from the Ground Up Riley Tipton Perry University of New South Wales, Australia NEW JERSEY LONDON SINGAPORE BEIJING SHANGHAI HONG KONG TAIPEI CHENNAI Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. QUANTUM COMPUTING FROM THE GROUND UP Copyright 2012 by World Scientific Publishing Co. Ltd. All rights reserved. All rights reserved.

This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher. For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher. ISBN 978-981-4412-11-7 (pbk) Printed in Singapore. Contents Acknowledgments This tutorial began life as something of an open book and has had many contributors and proof readers. I would like to thank everyone who has contributed. Special thanks go to the following people: Waranyoo Pulsawat, my dear wife.

Waranyoo has been a constant source of support, companionship, and inspiration. Brian Lederer, who is directly responsible for some parts of this text. He wrote the section on Bell states, some parts of the chapter on quantum mechanics, and a substantial amount of the other chapters. Without his help this work would never have been completed. Mohamed Barakat and Massoud Ghias Beygi who have published their own version of the original book in Arabic! Andreas Gunnarsson. Andreas' attention to detail is astonishing. A special thanks to Xerxes Rnby. Xerxes had some valuable comments and found a number of errors.

All the members of the QC4Dummies Yahoo group (http://groups.yahoo.com/group/QC4dummies/) and administrators David Morris and David Rickman.Sean Kaye and Micheal Nielson for mentioning this tutorial in their blogs. The people at Slashdot(http://slashdot.org/) and QubitNews(http://quantum.fis.ucm.es/) for posting the tutorial for review. James Hari, Simon Johnson, James Hollis, Nick Oosterhof, Rad Radish, Karol Bartkiewicz, Robin Kothari, Varun Vaidya, Kennedy Roulston, and Slashdotters AC, Birdie 1013, and s/nemesis. Chapter 1 Introduction 1.1 What is Quantum Computing? In quantum computers we exploit quantum effects to compute in ways that are faster or more efficient than, or even impossible, on conventional computers. Quantum computers use a specific physical implementation to gain a computational advantage over conventional computers. Properties called superposition and entanglement may, in some cases, allow an exponential amount of parallelism. Also, special purpose machines like quantum cryptographic devices use entanglement and other peculiarities like quantum uncertainty.

Quantum computing combines quantum mechanics, information theory, and aspects of computer science [31]. The field is a relatively new one that promises secure data transfer, dramatic computing speed increases, and may take component miniaturisation to its fundamental limit. This text describes some of the introductory aspects of quantum computing. We'll examine some basic quantum mechanics, elementary quantum computing topics like qubits, quantum algorithms, physical realisations of those algorithms, basic concepts from computer science (like complexity theory, Turing machines, and linear algebra), information theory, and more. 1.2 Why Another Quantum Computing Tutorial? Most of the books or papers on quantum computing require (or assume) prior knowledge of certain areas like linear algebra or physics so the majority of the current literature is hard to understand for the average computer enthusiast or interested layman. This text attempts to teach basic quantum computing from the ground up in an easily readable way.

It contains a lot of the background in mathematics, physics, and computer science that you will need, although it is assumed that you know a little about computer programming. At certain places in this document, topics that could make interesting research topics have been identified. These topics are presented in the following format: QuestionThe topic is presented in bold-italics. 1.2.1 Quantum Computation and Quantum Information By far the most complete book available for quantum computing is Quantum Computation and Quantum Information by Michael A. Nielsen and Isaac L. Chuang, which we'll abbreviate to QCQI. The main references for this work are QCQI and a great set of lecture notes, also written by Nielsen.

Nielsen's lecture notes are currently available at http://www.qinfo.org/people/nielsen/qicss.html. An honourable mention goes out to Vadim V. Bulitko who has managed to condense a large part of QCQI into fourteen pages! QCQI may be a little hard to get into at first, particularly for those without a strong background in mathematics. So this tutorial is, in part, a collection of worked examples from various web sites, sets of lecture notes, journal entries, papers, and books which may aid in understanding of some of the concepts in QCQI. Chapter 2 Computer Science 2.1 Introduction The special properties of quantum computers force us to rethink some of the most fundamental aspects of computer science. In this chapter we'll see how quantum effects can give us a new kind of Turing machine, new kinds of circuits, and new kinds of complexity classes.

This is important as it was thought that these things were not affected by what a computer is built from, but it turns out that they are. A distinction has been made between computer science and information theory. Although information theory can be seen as a part of computer science it is treated separately in this text with its own dedicated chapter. This is because the quantum aspects of information theory require some of the concepts introduced in the chapters that follow this one. There's also a little mathematics and notation used in this chapter which is presented in the first few sections of and some basic C and Javascript code for which you may need an external reference. 300 BC), which is an algorithm for finding the greatest common divisor of two numbers. 300 BC), which is an algorithm for finding the greatest common divisor of two numbers.

There are also much older sources like early Babylonian cuneiform tablets (c. 20001700 BC) that contain clear evidence of algorithmic processes []. Up until the 19th century it's difficult to separate computer science from other sciences like mathematics and engineering so we'll say here that computer science began as a separate science in the 19th century. Fig. 2.1 Charles Babbage and Ada Byron. An important precursor to early computing machines was the punched card.