Quantum Computing and Communications E-Book

Sandor Imre

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

Seitenzahl: 433

Veröffentlichungsjahr: 2013

Beschreibung

Quantum computers will revolutionize the way telecommunications networks function.

Quantum computing holds the promise of solving problems that would be intractable with conventional computers by implementing principles from quantum physics in the development of computer hardware, software and communications equipment.

Quantum-assisted computing will be the first step towards full quantum systems, and will cause immense disruption of our traditional networks. The world’s biggest manufacturers are investing large amounts of resources to develop crucial quantum-assisted circuits and devices.

Quantum Computing and Communications:

• Gives an overview of basic quantum computing algorithms and their enhanced versions such as efficient database searching, counting and phase estimation.
• Introduces quantum-assisted solutions for telecom problems including multi-user detection in mobile systems, routing in IP based networks, and secure ciphering key distribution.
• Includes an accompanying website featuring exercises (with solution manual) and sample algorithms from the classical telecom world, corresponding quantum-based solutions, bridging the gap between pure theory and engineering practice.

This book provides telecommunications engineers, as well as graduate students and researchers in the fields of computer science and telecommunications, with a wide overview of quantum computing & communications and a wealth of essential, practical information.

Leseprobe

Contents

Preface

How to use this Book

Acknowledgments

List of Figures

Acronyms

Part I: Introduction to Quantum Computing

1 Motivations

1.1 Life Cycle of a Well-known Invention

1.2 What about Computers and Computing?

1.3 Let us Play Marbles

2 Quantum Computing Basics

2.1 Mystery of Probabilistic vI Gate

2.2 The Postulates of Quantum Mechanics

2.3 Qbits and Qregisters

2.4 Elementary Quantum Gates

2.5 General Description of the Interferometer

2.6 Entanglement

2.7 No Cloning Theorem

2.8 How to Prepare an Arbitrary Superposition

2.9 Further Reading

3 Measurements

3.1 General Measurements

3.2 Projective Measurements

3.3 Positive Operator Valued Measurement

3.4 Relations among the Measurement Types

3.5 Quantum Computing-based Solution of the Game with Marbles

3.6 Further Reading

Part II: Quantum Algorithms

4 Two Simple Quantum Algorithms

4.1 Superdense Coding

4.2 Quantum Teleportation

4.3 Further Reading

5 Quantum Parallelism

5.1 Introduction

5.2 Deutsch–Jozsa Algorithm

5.3 Simon Algorithm

5.4 Further Reading

6 Quantum Fourier Transform and its Applications

6.1 Quantum Fourier Transform

6.2 Quantum Phase Estimation

6.3 Order Finding and Factoring – Shor Algorithm

6.4 QFT as generalized Hadamard transform

6.5 Generalizations of order finding

6.6 Further Reading

Part III: Quantum-assisted Solutions of Infocom Problems

7 Searching in an Unsorted Database

7.1 The Basic Grover Algorithm

7.2 Quantum Counting

7.3 Quantum Existence Testing

7.4 Finding Extreme Values in an Unsorted Database

7.5 The Generalized Grover Algorithm

7.6 Further Reading

8 Quantum-based Multi-user Detection

8.1 Introduction to Code Division Multiple Access and Classical Multi-user Detection

8.2 Optimal Multi-user Detection

8.3 Quantum-based Multi-user Detection

8.4 Further Reading

9 Quantum-based Code Breaking

9.1 Introduction to Cryptology

9.2 Symmetric Key Cryptography

9.3 Public Key Cryptography

9.4 Quantum-based Solutions for Breaking Public Key Cryptosystems

9.5 Further Reading

10 Quantum-based Key Distribution

10.1 The BB84 Protocol

10.2 The B92 Algorithm

10.3 EPR Paradox Based Key Distribution

10.4 Teleportation as a Useful Element in Quantum Cryptography

10.5 Further Reading

11 Surfing the WEB on Quantum Basis

11.1 Introduction to WEB Surfing

11.2 Quantum-based Solution of the Guessing Secret Problem

Part IV: Appendices

12 Mathematical Background

12.1 Basic Probability Theory

12.2 Linear Algebra

12.3 Number Theory

13 Derivations Related to the Generalized Grover Algorithm

13.1 Eigenvalues of the Generalized Grover Operator

13.2 Eigenvectors of the Generalized Grover Operator

14 Complex Baseband-equivalent Description of Bandlimited Signals

15 Useful Links

References

Solutions of Exercises

Index

Copyright © 2005   John Wiley & Sons Ltd,The Atrium, Southern Gate, Chichester,West Sussex PO19 8SQ, EnglandTelephone ([phone]

Email (for orders and customer service enquiries): [email protected]

Visit our Home Page on www.wileyeurope.com or www.wiley.com

All Rights Reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except under the terms of the Copyright, Designs and Patents Act 1988 or under the terms of a licence issued by the Copyright Licensing Agency Ltd, 90 Tottenham Court Road, London W1T 4LP, UK, without the permission in writing of the Publisher. Requests to the Publisher should be addressed to the Permissions Department, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England, or emailed to [email protected], or faxed to ([phone].

This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the Publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Other Wiley Editorial Offices

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

Jossey-Bass, 989 Market Street, San Francisco, CA 94103-1741, USA

Wiley-VCH Verlag GmbH, Boschstr. 12, D-69469 Weinheim, Germany

John Wiley & Sons Australia Ltd, 33 Park Road, Milton, Queensland 4064, Australia

John Wiley & Sons (Asia) Pte Ltd, 2 Clementi Loop #02-01, Jin Xing Distripark, Singapore 129809

John Wiley & Sons Canada Ltd, 22 Worcester Road, Etobicoke, Ontario, Canada M9W 1L1

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

ISBN 0-470-86902-X

To my father who taught me the way of thinking and to my mother who showed me how to endure to the end.

Sándor Imre

P.S. and of course to my children Sanyus, Marci, Orsi, Andris and their mother Adel.

Preface

Quantum computing and communications is one of the promising new fields of the new millennium. This emerging topic has reached the age when not only physicists and mathematicians but also engineers are becoming more and more interested in it. This book is based on the first semester of a two-semester subject dedicated to Ph.D. students and undergraduates in electrical engineering and computer sciences at Budapest University of Technology and Economics. This first semester covers a thorough basic introduction to the quantum computing world and discusses quantum-assisted computing and communications where we use the new paradigm to improve (assist) the performance of classical systems (e.g. searching in an unsorted database or strengthening communication security). In addition the second semester deals with quantum-based communications or more precisely with quantum information theory (e.g. channel capacity, error correction). After six semesters of experience we decided to prepare a book which can be used both as lecture notes and as a standalone learning aid for colleagues with engineering practice.

Although there are several good books on the market none of them has been written by engineers to engineers. The so-called ‘engineering’ approach has minor and major differences compared to materials authored by experts of physics, despite the fact that they cover more or less the same topic. As a simple example for the former category let us mention that engineers use j rather than i to denote the imaginary part of a complex number. However, it is not only conventions that make the discussion different. A presented sophisticated solution of a certain problem and the proof of its correctness do no satisfy an engineer. She/he always wants to know the way leading from the definition of the problem via system model construction and a logical chain of thoughts before reaching an answer to the original problem. If this ‘special’ viewpoint is omitted, which happens often when the authors are not familiar with engineers’ everyday lives, then it always leaves behind a lack of completeness.

Another important aspect for engineers can be summarized as the ‘need for practical applications’. A new theory or even an algorithm in itself has limited value. One has to prove and show that their implementation constraints, such as computational complexity, required memory, etc., can be fulfilled in the case of certain practical applications. Furthermore an unambiguous mapping of theoretical and real-life parameters has to be provided.

Finally, working as an engineer means the permanent study of the science of making compromises. The outcome of a design process must be precise enough and cheap enough and manageable enough and etc. and not the most precise or the cheapest or the most manageable or etc. Hence error analysis must always be kept at the focus of investigations.

All these endeavors are motivated by the fact that engineers should learn how to design new practical solutions. We always have this philosophy in sight when addressing various topics of quantum computing and communications. Of course we do not want to rank the engineering approach above those of physicists and mathematicians, we simply state that they are different (and not better or worse) in some sense. Due to this fact learning and understanding are much easier if explanations follow the way we are used to.

From a background mathematics’ point of view we assumed a typical curriculum of engineers and computer scientists, however, the required math has been summarized in the appendix.

Because of the limited size of this book there are some aspects that are not discussed in detail. We did not devote an individual chapter to the implementation questions of quantum computers. Instead at the end of each chapter in the Further Reading we give a state-of-the-art survey of the current status of implementation and provide up-to-date references for interested readers. Philosophical questions and answers are also beyond the scope of this book but we suggest reading e.g. [84, 145] if the reader has time and would like to widen his/her knowledge.

Now we invite the reader to join us on the journey which is going to pass sometimes interesting, sometimes strange and sometimes challenging lands of the quantum world. Do not hesitate, the new world is waiting for you…

The Authors

How to use this book

According to ancient legend, one day Alexander the Great, conqueror of the ‘that time known world’ (Greece, Egypt, Persia), asked Menaikhmos the famous mathematician to teach him geometry in an easier and faster way. Menaikhmos smiled at this wish and answered: ‘Oh king, you ordered your engineers to build distinct roads for citizens and for messengers and the army of the king all around your empire, but there is only one road for all in geometry!’1

Basically we agree with Menaikhmos: learning and understanding quantum computing and communications need time and effort from the reader. However, we are convinced that if the way the knowledge is served is chosen carefully and fits more or less to previous studies of the reader, then high spirits can be maintained at hard portions of the topic. Before starting the voyage we would like to provide some useful hints and tools similarly to seamen who check their maps and compasses before sailing out to sea.

This book can be divided logically into three well-defined parts. Part I explains the basics of quantum computing and communications. As the next level Part II introduces well-known quantum algorithms while advanced readers can find several quantum assisted solutions for state-of-the-art infocom problems in Part III. The book has been equipped with several special features intended to help the reader.

A dedicated web site can be found at

www.mcl.hu/qcc

containing useful information related to this book.

All the used notations, acronyms and abbreviations are summarized at the beginning of this book so that the reader can turn to this list at any time.

We prepared plenty of exercises from easy to hard-to-answer types, which allow the reader to test whether his/her understanding is appropriate. The solutions of exercises can be downloaded from the web site of this book or a hard copy can be obtained from the publisher. We do not claim, however, that the proposed solutions are the simplest and shortest ones. Therefore we encourage diligent readers to find more attractive solutions and send them to the authors (

[email protected]

) in latex format. Appropriate alternatives will be included with the names of their solver into the solutions file.

As a life belt the reader may find a summary of corresponding mathematical background in the appendices.

In order to allow the reader to widen his/her knowledge beyond the scope and size of this book a carefully selected large list of references has been attached. We took special care to choose – if possible – such publications that can be accessed electronically on the Internet so that the reader may save time (and money).

The book is amended with a list containing links to the web pages of the most important leading institutes and laboratories where additional information can be found or even current activities can be followed.

Obviously the probability of writing a book without any error is fairly low. Therefore we ask the reader to address any comments or found errata to the authors (

[email protected]

). A regularly updated and downloadable list of errata is maintained on the book’s web site.

1The same story is known with Euclid and King Ptolemy.

Acknowledgments

The authors gratefully acknowledge the comments and helpful advice of Prof. Katalin Friedl from the Computer and Automation Research Institute of the Hungarian Academy of Sciences. Pressure from and interest of students attending the corresponding courses were the most motivating issues that helped us keep the deadlines. We thank our boss Prof. Laszló Pap for the permanent encouragement and allowing us enough free time to complete the work.

Certain results introduced in this book were prepared in the frames of OTKA F042590, COST 289.

List of Figures

1.1   Heron’s ball about 100 B.C.

1.2   Moore’s law

1.3   Alice and Bob are playing marbles

2.1   Scientific model for coin tossing

2.2   Scientific model for concatenated coin tossing

2.3   Concatenated probabilistic gates

2.4   Implementation of probabilistic gate – the half-silvered mirror

2.5   Concatenated half-silvered mirrors as identity transformation

2.6   Geometrical visualization of one qbit in the Bloch sphere

2.7   Generalized interferometer

2.8   Abstract quantum circuit of the generalized interferometer

2.9   Controlled NOT gate

2.10   SWAP gate made of CNOTs

2.11   Bell state generator quantum circuit

2.12   Generalized quantum entangler

2.13   Quantum COPY machine

2.14   Abstract quantum circuit of the generalized interferometer

3.3   Implementing general measurement by means of a projective one

3.4   Alice and Bob are playing marbles using quantum strategy

4.1   The superdense coding scenario

4.2   The teleportation scenario

5.1   f-controlled CNOT gate

5.2   f-controlled CNOT gate with N-dimensional control input implementing parallel evaluation of f

5.3   Quantum architecture for solving the Deutsch–Jozsa problem

5.4   Quantum architecture for solving Simon’s problem

6.1   Sketch of QFT circuit

6.2   Circuit of Un-1

6.3   Quantum circuit implementing QFT

6.4   Quantum circuit producing |µn〉

6.5   Quantum circuit computing the phase

6.6   Illustration of probability amplitude regions before measurement with different index transformations

6.13   Quantum error probability log10 vs. number of required additional qbits p

6.14   Quantum circuit implementing order finding

6.17   Deutsch–Jozsa circuit as a decision maker whether f is constant or varying

6.18   Deutsch–Jozsa circuit as a simple phase estimator

6.19   Period-finding quantum circuit over

6.20   Two-dimensional period-finding quantum circuit

7.1   Circuit implementing the Grover operator

7.2   Probability amplitude distribution of the index register at |φ1〉

7.3   Content of qregister |γ2〉 after invoking the Oracle

7.4   Effect of inversion about the average ā

7.5   Geometrical interpretation of the Grover operator

7.6   Explanation of the decision about the number of iterations

7.7   Pε,Ps, and vs.

7.8   Quantum counting circuit

7.12   Quantum circuit for searching in an unsorted database

7.16   Geometrical interpretation of the generalized Grover iteration

7.17   Different possible interpretations of | γ1〉′

8.1   Idealistic DS-CDMA architecture

8.2   Sequences, modulation and detection in DS-CDMA

8.3   Separation in the detector

8.4   Mobile access directions

8.5   Detection in the case of delayed signal

8.6   DS-CDMA transmitter and channel

8.7   Single-user DS-CDMA detector with matched filter, idealistic case

8.8   Multi-user DS-CDMA detector

8.9   System concept of quantum counting-based multi-user DS-CDMA detector

8.10   The structure of the index register

9.1   Basic concept of secure information transfer

9.2   Basic concept of symmetric key cryptosystems

9.3   Symmetric key cryptosystem in a public mobile network

9.4   Encryption with key generator

9.5   Architecture implementing the Diffie–Hellman concept

9.6   Architecture implementing the digital signature concept

9.7   log10(·) of required time in seconds to break the RSA with different methods

9.8    log10(·) of required time in seconds to break the RSA with different methods (enlarged)

10.1   Steps of BB84 protocol if no eavesdropper is present and the channel is idealistic

10.2   Eve’s eavesdropping equipment

10.3   Steps of BB84 protocol if Eve is present and the channel is idealistic

10.4   Steps of B92 protocol if Eve is not present and the channel is idealistic

10.5   Equivalence of two- and three-party version of BB84 protocol

11.1   The ‘All-IP’ concept

11.2   Graph representation of the Guessing Secrets problem

1   Geometrical interpretation to Exercise 6.4 and Exercise 6.5

2   Geometrical interpretation of the Grover operator

Acronyms

Part I

Introduction to Quantum Computing

1

Motivations

1.1 LIFE CYCLE OF A WELL-KNOWN INVENTION

Every invention/technology has its own life cycle, similar to a human being. It can be shorter or longer but all of them have common phases and stages. Let us summarize this evolution using the well-known example of steam engine. First, scientists spend lots of time to find out something new. In our case Heron, a most famous experimenter, designed and implemented a steam-engined ball named Heron’s ball (see Fig. 1.1).

Once a new idea has been born a long period of time is required until the stage when size, cost, efficiency, etc. of pieces of this equipment reach a minimally required and acceptable level. Many amateurs and experts devote their life to fulfil these requirements representing the childhood of the technology. The way is paved with many failures and rare successes therefore most of them remain anonymous forever. However, one day a clever guy manages to combine the small pieces of former results and adds something to them thus finally he/she succeeds. Concerning our example James Watt built the first working steam engine in 1765. Thanks to Mr. Watt steam technology attained its majority.

In the third phase the technology emerges from the deep of dark and mysterious laboratories and begins spreading among everyday people. Fulton’s ship Clermont in 1807 irreversibly ended the glorious age of sailing ships and men of war while Stephenson’s Rocket in 1829 convinced the skeptics that railway would be the leading transportation solution on land in the future. Human, sail and animal power had been replaced by steam engines during some decades from the kitchens via workshops up to enormously large ships such as Titanic or the battleships of World War I. The efficiency of the largest steam engine reached 22000 kW in 1941. Of course to achieve this level of popularity geniuses have to overcome strong resistance from those who exert the power. For instance William Symington built a steam-engined towboat on the Thames and presented her capabilities. Unfortunately the officials prohibited Symington from using the boat because they were afraid that the waves generated by the boat might damage the river-bank.

Fig. 1.1 Heron’s ball about 100 B.C.

The size/power in itself is, however, not enough to survive (cf. dinosaurs or large empires). After a certain point efficiency becomes as important as power. It was foreseen and proven theoretically – long before steam-powered systems reached the top – that the efficiency of any steam-engine is limited and not enough for example for flight. If the new demand cannot be satisfied by means of a certain technology then other, even very young ideas are brought to light while the old one will be squeezed gradually. The reader may guess the name of the new pretender: yes, it was the internal combustion engine.

1.2 WHAT ABOUT COMPUTERS AND COMPUTING?

Now let us turn to our ‘home’ science which focuses on computers, computing and communications. The most important steps towards an electronic computer were done during World War II when the large number calculations in the Manhattan project required an elementary new equipment which was fast enough and adaptive (programmable). Many clever scientists were engaged with this problem. We mention here the polymath Neumann because he will appear several times in this book. As we will see later he played important role in quantum mechanics as well but at this moment we say thank you to him for the invention of the ‘control by stored program’ principle.1 This principle combined with the vacuum tube hardware which formed the basis of the first successful computers.2 Unfortunately the tubes strongly limited the possibilities of miniaturization hence the first computers filled up a whole room, which strongly restricted their wide applications. Therefore scientists paid attention to the small-scale behavior of matter. Fortunately the invention of semiconductors and the appearance of the transistor in 1948 by Bardeen, Brattain and Schockley opened the way to personal computers and other handheld equipment.

One day in 1965 when Gordon Moore from Intel was preparing his talk and started to draw a plot about the performance of memory chips he suddenly observed an interesting rule called Moore’s law. As it is depicted in Fig. 1.2 he concluded that since the invention of the transistor the number of transistors per chip roughly doubled every 18–24 months, which means an exponential increase in the computing power of computers. Although it was an empirical observation without theoretical proof the law seems to be still valid nowadays. However, similar to the case of steam engine farseeing experts tried to determine the future of this technology. They estimate serious problems around 2015. What reasons may stand behind this prophecy?

No matter how surprising it sounds this trend can be traced back simply to drawing lines. The growth in processors’ performance is due to the fact that we put more and more transistors on the same size chip. This requires smaller and smaller transistors, which can be achieved if we are able to draw thinner and thinner – even much thinner than a hair – lines onto the surface of a semiconductor disk. Next current technology enables us to remove or retain parts of the disk according to the line structure evolving to transistors, diodes, contacts, etc. Apart from the technical problem of drawing such thin lines one day our lines will leave our well-known natural environment with well-known rules revealed step by step during the evolution of human race and enter into a new world where the traveler must obey new and strange rules if he/she would like to pass through this land. The new world is called nano-world, the new rules are explained by quantum mechanics and the border between the worlds lies around nanometer (10−9m) thickness. Fortunately scientists have already performed many reconnaissance missions in the nano-scale region thus we have not only theoretical but also technology-related knowledge in our hands called nanotechnology.

From a computer scientist’s point of view, who has algorithms and programs in his/her mind, the growth in the capabilities of the underlying hardware is vital. If we have an algorithm which is not efficient often enough time alone solves the problem due to the faster new hardware. We can say that we got used to Moore’s law during the last decades and forgot to follow what is happening and what will happen with the hardware. For decades, this attitude was irrelevant but the deadline to change it is near to its expiration. Fortunately experts called our attention to the fact that we will have to face serious problems if this trend cannot be maintained. One thing is sure, however, the closer we are to the one-electron transistor (see Fig. 1.2) disturbing quantum effects will appear more often and stronger. Hence either we manage to find a new way of miniaturization or we have to learn how to exploit the difficulties and strangeness of quantum mechanics. Independently from the chosen way we must do something because Computing is a must or as ancient Romans said “Navigare necesse est!”

Fig. 1.2 Moore’s law

In compliance with the latter concept Feynman suggested a new straightforward approach. Instead of regarding computers as devices working under the laws of classical physics – which is common sense – let us consider their operation as a special case of a more general theory governed by quantum mechanics. Thus the way becomes open from the hardware point of view. On the other hand hardware and software always influence each other. Since new hardware concepts require and enable new software concepts we have to study quantum mechanics from a computer science point of view. Moreover it is worth seeking algorithms which are more efficient than their best classical counterparts thanks to the exploited possibilities available only in the quantum world. These software-related efforts are comprehended by quantum computing. Once we familiarized ourselves with quantum-faced computing why keep communications away from the new chances. May be the capacity of a quantum channel could exceed that of classical cable or we could design more secure protocols than currently applied ones. Quantum communications or quantum information theory tries to answer these questions.

Realization issues are out of the scope of this book thus we mention here that there are fairly promising results in certain areas e.g. implementation of secure quantum-based communications but we do not want to conceal that desktop quantum personal computers are far from introduction to the market. Concerning the subject of our book, quantum computing and communications have passed several important milestones. Top experts have experimentally validated algorithms which overcome the classical competitors. For instance we are able to find an item in an unsorted database or factorize large numbers very quickly. Quantum principles allow solving easily a long discussed problem, namely random number generators e.g. [21]. Furthermore as we mentioned before, implementation of certain algorithms reached such a stage that one can buy corresponding equipment in an appropriate shop. Fortunately many questions are waiting to be answered thus the reader will find not only solutions but open questions in this book. Nothing shores up more convincing the spreading of the new paradigm than the fact that more and more publications appear in popular science magazines and journals [38, 22, 110, 115].

Remark: Moore’s law has several interpretations depending on which side of the market it has been phrased

Rock’s law: “

The cost of capital equipment to build semiconductors will double every four years.

” by Arthur Rock (industry)

Machrone’s law: “

The machine you wants always costs $5000.

” by Bill Machrone (customer)

If the reader is familiar with other versions of Moore’s law we ask him/her to post it to the authors (

[email protected]

) so that we will share them on the book’s web page.

1.3 LET US PLAY MARBLES

Playing games is as old as humankind. To give further motivations to study quantum computing and communications and to read the remaining more then 250 pages of this book we suggest playing a simple but interesting game. First let us introduce our virtual friends who are always ready to participate in games or any other experiment. They are Alice, Bob and Eve. Since Eve is often inclined to act the young rascal any time when we need an eavesdropper or negative hero she will be happy to play this role.

Alice and Bob decide to join. We explain the rules of the game to them (cf. Fig. 1.3). We have a sack full of marbles. First we put 0, 1, 2, 3 or 4 marbles into a blue colored box. Our choice is uniformly random. Next we take a red box and flip a coin. In compliance with the result if we got a tail we put marbles from the sack into this box such that the total number of marbles in the two boxes will be 4 else we complement them to 6. Now we ask Alice and Bob to enter two perfectly separated rooms which prevent any type of communications between them i.e. they are shaded from voice, electromagnetic radiation, etc. Both of them are only allowed to take one of two identical, previously prepared devices each having an integer input and a one-bit output. When our players have seated themselves comfortably we give Alice the blue box while Bob obtains the red one. Now they are allowed to open the boxes and feed the device with the number of marbles. Next each of them has the possibility to give a one-bit sign according to the device’s output, for instance via setting a flag in an up or down position. If they are able – based on this sign and their own marbles – to design a perfect device (i.e. strategy or mapping) which makes obvious to the audience whether the coin has fallen onto heads or tails then they win this turn and are rewarded with a pair of cinema or theatre tickets.

Fig. 1.3 Alice and Bob are playing marbles

Alice and Bob are clever and wily hence they investigate first the existence of such a strategy which provides success with probability 1. Let (x; y) denote a certain configuration, where x refers to the number of Alice’s marbles while y to that of Bob. If the total number of marbles equals 4 then one of the following five combinations has been prepared: {(0; 4), (1; 3), (2; 2), (3; 1), (4; 0)}. On the other hand Alice and Bob have to face one element of the following set: {(0; 6), (1; 5), (2; 4), (3; 3), (4; 2)}.3

It is easy to see that no classical strategy exists which ensures certain success. However, interestingly as we will present at the end of Part I a simple quantum protocol allows Alice and Bob to make any combination unambiguous for the audience. This seems to be in total contradiction to our classical theory of probability or more generally how nature works. We hope that the reader is eager to learn this protocol and we ask him/her to read the basics before turning to those pages. In the meantime we call the reader to participate in the quest of the most efficient classical strategy that results in the largest probability of success if the game is repeated many times. Please, post your candidate strategy with derivation of the corresponding probability of success to the authors ([email protected]) in ps or pdf format. Correct strategies will be published on the book’s web page.

1The third area where he is counted among the founding fathers is called game theory.

2As an interesting story we mention here that Neumann was talented in mental arithmetic, too. The correct operation of the computer under construction was tested by multiplying two 8-digit numbers. Typically Neumann was the fastest.

3Configurations (5; 1) and (6; 0) are trivially excluded since Alice is given at most 4 marbles.

2

Quantum Computing Basics

This chapter is devoted to the basic information, techniques and skills required to travel around the quantum world safely. First we introduce quantum phenomena using the strange sounding probabilistic gate in Section 2.1. Quantum computing is rooted in quantum mechanics therefore Section 2.2 explains the postulates of quantum mechanics which form the solid base of any further discussion. Next we build bridges between classical and quantum computing in Section 2.3 and 2.4 where generalization of registers and logic gates are investigated. The following Section 2.5 analyzes an interesting quantum circuit called quantum interferometer. Quantum mechanics offers certain possibilities which are not present in classical computing. The most important one which connects pieces of quantum information very tightly is referred to as entanglement and is introduced in Section 2.6. As in everyday life everything has its price. The price of entanglement has some restrictions e.g. we can use the COPY command in quantum computing as explained in Section 2.7. Finally we show how to prepare an arbitrary quantum state in a quantum register in Section 2.8.

2.1 MYSTERY OF PROBABILISTIC GATE

We propose to start getting acquainted with quantum computing and communications by means of a thought experiment leading to a fairly surprising result. Let us investigate coin tossing using scientific apparatus. If one flips a coin she/he will obtain a head or a tail randomly. When we have a legal coin1 tossed enough times then statistically both results occur about half of the times. This operation can be modeled by means of a device depicted in Fig. 2.1 where heads and tails are represented by logical 0 and 1, respectively. Transition probabilities are defined in the following manner

Fig 2.1 Scientific model for coin tossing

Now we make the experiment more difficult by tossing a certain coin two times successively, which can be modelled by concatenating two boxes according to Fig. 2.2. Furthermore we are interested in the transition probabilities Pkl of a special single gate which is equivalent to the two-gate configuration. It is reasonable to assume that the two tossings are independent thus basic probability theory advises us how to calculate different Pkl

(2.1)

Fig. 2.2 Scientific model for concatenated coin tossing

With this point our view of nature proved to be round and complete. However, readers who are not familiar with quantum mechanics are kindly asked to steel their hearts. There exist devices which operate in full compliance with the random coin tossing model if only one of them is investigated, but when concatenating two of them the output becomes suddenly deterministic! Deterministic means here that the two gates together look as if they implemented an identity transform.

Fig. 2.3 Concatenated probabilistic gates

In possession of the notion of probability amplitudes we are able to design suitable probabilistic gates and concatenate two of them, see Fig. 2.3. If one would like to define the quantum equivalent of the legal coin tossing then and has to be set up. Let us check the transition probability amplitudes of the equivalent single gate

(2.2)

A plausible explanation of this surprising result can be given if the reader considers the arrows in Fig. 2.3 as waves (sinusoid signals) with amplitudes ckl and these waves interfere with each other causing total wipe out or maximal gain. This reasoning is much closer to the truth than one may expect because our mysterious equipment which contradicts the classical probability theory is a half-silvered mirror (or beam splitter). It operates in the following way (see Fig. 2.4). When a great amount of photons are shot onto the beam splitter about half of them hits the vertical detector and the remaining half arrives at the horizontal detector. Next we connect the outputs of such a device by means of traditional mirrors to the inputs of an identical half-silvered mirror. Surprisingly the horizontally launched photons always hit the vertical detector (see Fig. 2.5). It is hard to interpret this result using our classical view of nature. If we consider the photon as a small marble whose way is chosen randomly at each beam splitter then it is impossible to explain why the photon is directed each time to the same detector. Maybe deploying a detector onto one of the paths between the two beam splitters can answer which way the photon was travelling? However, the photon does not accept this trick. Because of the extra detector the operation of the configuration loses its deterministic nature and becomes random as if only the second half-silvered mirror were used alone. This is another important lesson. Measurements typically influence the observed system and thus the measurement results themselves. A more successful attempt if the photon is regarded as a marble before arriving the first beam-splitter is that it turns into a wave which propagates on both paths. At the second half-silvered mirror the two waves (the photon) interfere(s) (with itself) and convert back to a marble before striking the detector. This explanation highlights why the concatenated probabilistic gates are referred as quantum interferometer.

Finally we would like to emphasize that there is no sense in thinking about the state of the photon (which path it is taking), it must be considered as being in both states (both paths) at the same time and the measurement force it to collapse (select) into one of them. This differs fundamentally from our classical approach which assumes that the photon always travels along a single path hidden to the eyes of the observer and measurements only reveal this path instead of deciding it. We will analyze the interferometer more scientifically in Section 2.5 and discuss measurements in Chapter 3.

Fig. 2.4 Implementation of probabilistic gate – the half-silvered mirror

Fig. 2.5 Concatenated half-silvered mirrors as identity transformation

Remark: Let us throw some light upon the close connection between the measuring apparatus and the measured object using the widely known microscopy. Optical microscopes use the reflected photons from the object’s surface. To achieve reflection the half-wavelength of the photon (more precisely light is considered as a wave at this point) has to be smaller than the unevenness of the surface. Therefore in order to observe smaller and smaller details we need shorter and shorter wavelengths e.g. X-rays. On the other hand the light can be regarded as a series of photons. Each photon has its mass and thus its energy which depends on the frequency of the light. The higher the frequency then the higher the corresponding energy. Since frequency and wavelength are in inverse relation the reflecting photon transfers more and more energy to the observed object, that is the photon influences it more and more radically.

2.2 THE POSTULATES OF QUANTUM MECHANICS

Nobody knows how the physical world really operates. The only thing we can do is to model it. A given model/theory can be regarded as a suitable tool for the description of events all around us if the difference/error between expectations originating from the theory and the observations remain below a certain limit. For instance different models were developed for throwing during the history of the human race. First cavemen formed some simple rules based on experiences related to the power and angle of throwing. Although this approach ensured a high percentage hit on a mammoth it proved to be insufficient for cannon-balls. Later Isaac Newton introduced gravity and more sophisticated formulas which enable more or less precise hits on the enemy’s castle if the shell is regarded as a zero-sized elementary mass and the trajectory is calculated in advance. Unfortunately in order to enter the spaceflight and advanced astronomical age Newtonian theory had to be replaced by relativity theory, which provides a high probability of survival for astronauts fired out towards the moon. This proposal handles the spaceship as a marble rolling ahead in the elastic textile of space-time curved by planets and stars. These models represent different viewpoints about nature therefore they give different explanations of how the world operates but what they have common is that they do not answer why the world operates that way.

Each theory is based on several assumptions that cannot be verified theoretically, only experiments shore up that they are in consonance of the nature. For example Euclidian geometry has so-called axioms e.g. the sum of angles in a triangle equals 180°. However, these assumptions can be replaced by other ones, for instance the sum of angles in a triangle is less or greater than 180° leading to Riemanian (elliptic) or Bolyaian (hyperbolic) geometry.

In the case of quantum mechanics we have four assumptions called postulates which form a solid base for the theory. According to our state-of-the-art knowledge most of the rules in the universe can be traced back to these postulates and only a few effects such as the long-range gravity seem to be an exception. Thousands of scientists are spending their scientific life trying to discover the so-called great unified theory (GUT) which is able to squeeze these two theories, i.e. relativity theory and quantum mechanics, into a single one.4

Because not only the universe but also the content of this book are based on these postulates let us summarize them from a quantum computing point of view.

First Postulate (state space):The actual state of any closed physical system can be described by means of a so-called state vectorvhaving complex coefficients and unit length in a Hilbert space V, i.e. a complex linear vector space (state space) equipped with an inner product.

Second Postulate (evolution):The evolution of any closed physical system in time can be characterized by means of unitary transforms depending only on the starting and finishing time of the evolution.

According to the previously introduced physical system the second Postulate can be interpreted as .

The above definition describes the evolution between discrete time instants, which is more suitable in the context of quantum computing, however, we cite here its original continuous-time form known as the Schrödinger equation

where denotes the Planck’s constant5 and H/ represents the so-called Hamiltonian, a Hermitian operator characterizing the evolution of the system. Comparing H to U the former is time invariant. The connection between the two approaches can be bridged by means of the following relation

Those readers who are not familiar with operator functions are advised to read Section 12.2.6.

The linear algebraic representation of a unitary operator U is a quadratic matrix U which consists of elements Uij denoting the conditional probability amplitude connecting input orthonormal basis vector j with vector i. Unitarity has several equivalent definitions which are summarized in Section 12.2.5.

Third Postulate (measurement):Any quantum measurement can be described by means of a set of measurement operators {Mm}, where m stands for the possible results of the measurement. The probability of measuringm if the system is in state v can be calculated as

and the system after measuringm goes to state

Because classical probability theory requires that

measurement operators have to satisfy the following completeness relation

Measurements are obviously not reversible and therefore they represent the only exception under the unitarity constraint. We can say that measurements connect the quantum and classical worlds6 or measurements are the only tools which allow taking a look at what happens in the quantum world. Unfortunately they prove to be very coarse, like an elephant in a porcelain store, i.e. they influence the system itself under measurement as the second part of the third Postulate and our former discussion about microscopes claim.

The completeness relation is very useful when designing measurements because it allows checking whether all the possible outcomes were taken into account.

2.3 QBITS AND QREGISTERS

The postulates of quantum mechanics introduced in the previous section provide exact mathematical formulations of the basic rules of nature. However, they are far from everyday computer scientist or engineering practice. We would rather prefer a higher level abstraction which hides real physical particles and processes and allows the application of such notions as bit, register, gates, circuits and last but not least communication channels because they represent our homely environment. Therefore this section is devoted to building up a similar level of abstraction for the quantum universe.

The smallest information-bearing unit is called a bit.