Topics in Applied Physics Volume 102 TopicsinAppliedPhysicsispartoftheSpringerLinkservice.Forallcustomerswithstanding ordersforTopicsinAppliedPhysicsweofferthefulltextinelectronicformviaSpringerLink freeofcharge.Pleasecontactyourlibrarianwhocanreceiveapasswordforfreeaccesstothefull articlesbyregistrationat: springerlink.com→Orders Ifyoudonothaveastandingorderyoucanneverthelessbrowsethroughthetableofcontentsof thevolumesandtheabstractsofeacharticleat: springerlink.com→BrowsePublications Topics in Applied Physics Topics in Applied Physics is a well-established series of review books, each of which presents a comprehensivesurveyofaselectedtopicwithinthebroadareaofappliedphysics.Editedandwritten by leading research scientists in the field concerned, eachvolume contains review contributions coveringthevariousaspectsofthetopic.Togethertheseprovideanoverviewofthestateoftheart intherespectivefield,extendingfromanintroductiontothesubjectrightuptothefrontiersof contemporaryresearch. TopicsinAppliedPhysicsisaddressedtoallscientistsatuniversitiesandinindustrywhowishto obtainanoverviewandtokeepabreastofadvancesinappliedphysics.Theseriesalsoprovideseasy butcomprehensiveaccesstothefieldsfornewcomersstartingresearch. Contributionsarespeciallycommissioned.TheManagingEditorsareopentoanysuggestionsfor topicscomingfromthecommunityofappliedphysicistsnomatterwhatthefieldandencourage prospectiveeditorstoapproachthemwithideas. ManagingEditors Dr.ClausE.Ascheron Dr.HansJ.Koelsch Springer-VerlagGmbH Springer-VerlagNewYork,LLC Tiergartenstr.17 233,SpringStreet 69121Heidelberg NewYork,NY10013 Germany USA Email:[email protected] Email:[email protected] AssistantEditor AdelheidH.Duhm Springer-VerlagGmbH Tiergartenstr.17 69121Heidelberg Germany Email:[email protected] Hiroshi Imai Masahito Hayashi (Eds.) Quantum Computation and Information From Theory to Experiment With49Figures 123 HiroshiImai GraduateSchoolofInformation,ScienceandTechnology TheUniversityofTokyo 7-3-1Hongo,Bunkyo-ku Tokyo,113-8656Japan and ERATOQuantumComputationandInformationProject JapanScienceandTechnologyAgency 201DainiHongoWhiteBldg 5-28-3,Hongo,Bunkyo-ku Tokyo113-0033,Japan [email protected] MasahitoHayashi ERATOQuantumComputationandInformationProject JapanScienceandTechnologyAgency 201DainiHongoWhiteBldg 5-28-3,Hongo,Bunkyo-ku Tokyo113-0033,Japan [email protected] LibraryofCongressControlNumber:2006923435 PhysicsandAstronomyClassificationScheme(PACS): 03.67.Lx,03.67.-a,03.67.Dd,03.67.Mn,42.50.-p ISSNprintedition:0303-4216 ISSNelectronicedition:1437-0859 ISBN-10 3-540-33132-8SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-33132-2SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialisconcerned, specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting,reproductionon microfilmorinanyotherway,andstorageindatabanks.Duplicationofthispublicationorpartsthereofis permittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965,initscurrentversion,and permissionforusemustalwaysbeobtainedfromSpringer.ViolationsareliableforprosecutionundertheGerman CopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply,evenin theabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelawsandregulations andthereforefreeforgeneraluse. Typesetting:DA-TEX·GerdBlumenstein·www.da-tex.de Production:LE-TEXJelonek,Schmidt&V¨ocklerGbR,Leipzig Coverdesign:design&productionGmbH,Heidelberg Printedonacid-freepaper 57/3100/YL 543210 Preface Once the quantum effect had been regarded as an obstacle to suitable in- formation processing in existing information systems. Recently, it has been discovered that quantum effect is, to the contrary, very useful as a resource used in information processesing. This research field is called quantum infor- mation and is rapidly growing as a new paradigm for information systems. For example, we can factorize a large number quickly by Shor’s algorithm on a quantum computer once a quantum computer is available, and we can communicate securely without any assumption for computation complexity by using quantum key distribution. These quantum information protocols cannot be realized without quantum effects. In the research of existing information processes, it is possible to study hardware and software separately because their roles are clearly divided. However, such separation between them becomes an obstacle for the whole researchonquantuminformation.Towardthedevelopmentofquantumalgo- rithmsandprotocols,itisnecessarytounderstandthemathematicaldescrip- tionofquantumphenomena.Therealizationofquantuminformationsystems requires development of quantum devices, for which we need to understand the theoretical scheme of quantum information science. Therefore, we need collaboration over the existing framework. To promote such collaboration, we bring this book as a collection of overviews of selected topics in quantum information. Thisbookorganizedasfollows.Weexplainthepowerofquantumcompu- tation in Part I. Currently, only Shor’s factorization algorithm and Grover’s search algorithm are known to be faster on a quantum computer than on a classical computer. The ability of a quantum computer cannot be cleared up onlybydiscoveryofthesealgorithms.Now,manyresearchersareattempting to developing better quantum devices to build a quantum computer. How- ever, the research for the power of quantum computers is as important as the research for quantum devices. Part I reviews the so-called identification problem of an unknown function f using a quantum computer, where the function f is often called an oracle. In fact, many problems in computer sci- enceareformulatedinthisform.Forinstance,Grover’ssearchproblemisalso in this form. Part I discusses the superiority of a quantum computer over a classical computer for this type of problems. In particular, the Chapter by Ambainis et al. treats the case of no error in the computation process, and VI Preface theChapterbyIwamaetal.coversthecasewheresomeerrorshappeninthe specific points. By reviewing these topics, Part I signifies the importance of building a quantum computer. Part II focuses on the bounds of the power of several quantum informa- tionprocessesandquantumentanglement,whichisanimportantresourcefor quantum information protocols. TheChapter byHayashi dealswith theoret- ical issues on the identification of the density matrix of a quantum system. Since the perfect cloning of a quantum state is impossible and any mea- surement demolishes quantum states, precise identification requires a better measurementextractingmuchinformationfromthequantumsystem.Hence, theselectionofmeasurementisanimportantissueofthistopic.Ontheother hand, an approximate cloning is possible. The Chapter by Fan discusses the boundoftheperformanceofthequantumapproximatecloning.Throughthe Chapters by Hiroshima et al. and Matsumoto, we give an overview of the researchonquantumentanglement.TheChapterbyHiroshimaetal.reviews approaches toward quantum entanglement from various viewpoints. In par- ticular, entanglement is closely related to the problem of sending a quantum state via a noisy quantum channel. Such a relation is also discussed. The Chapter by Matsumoto focuses on the additivity problem, the hottest topic in quantum entanglement. This problem is essentially linked to the problem on sending classical information via a noisy quantum channel. We highlight thisconnection.Notethattheproblemonsendingquantumstateisdifferent from the problem on sending classical information. PartIIItreatssecurequantuminformationprocesses.Shor’sfactorization algorithmmakestheRSApublic-keycryptosysteminsecureonceonebuildsa quantumcomputer.Hence,wehavetopreparealternativecryptosystemsasa countermeasureforrealizationofquantumcomputer.Oneideaisthedevelop- ment of public-key cryptosystem that is secure even for quantum computers. Another is an information-theoretically secure cryptographic system whose security does not depend on the assumption for computational complexity. The Chapter by Kawachi et al. highlights the former type of cryptosystems by discussing the concept of one-way functions, which is a basic concept for public key cryptosystems. Based on this concept, the quantum public-key cryptosystem is explained. This cryptosystem well works on the assump- tion that all component parts (eavesdropper, channel, sender, and receiver) are quantum. The Chapter by Wang treats an information-theoretically se- cure protocol that distributes a secret key via a quantum channel, which is called quantum key distribution. Perfect single photons and noiseless quan- tumchannelsarenecessaryfortherealizationoftheinitialprotocolproposed byBennettandBrassard.Hence,weneedtoconsidertheprotocolofsending imperfectsingle-photonsvianoisyandlossyquantumchannels.Thesecurity oftheaboverealisticprotocolisthemaintopicofthischapter.Secureproto- cols are not limited in cryptography. Steganography is known as a protocol that keeps the secret of the existence of the communication. The Chapter by Natori shows that quantum steganography exceeds classical steganography. Preface VII Finally, Part IV reports the research activities of realization of quantum informationsystems.Thispartcontainsexperimentsconcerningquantumkey distribution,apartofShor’sfactorizationalgorithm,andgenerationofentan- gled states. First, we review 150km transmission quantum key distribution and quantum key distribution with a real optical fiber of commercial use for 14 days. Next, we see how to realize quantum computation with 1024 qubits of a part of Shor’s factorization algorithm. High-quality generation of entan- gled states is also discussed in this part. This book is organized so that each chapter can be read independently. We recommend that the reader begins with the chapter of interest and then expandtherangeofthisinterest.Wehopethatthereaderofthisbookwould get interested in a wide research area of quantum information science. In fact, the contents of this book mainly consist of research results obtained by the ERATO Quantum Computation and Information (QCI) Project. This project started in October 2000 by gathering interdiscipnary researchers from various research fields as one of Exploratory Research for Advanced Technology (ERATO) programs of Japan Science and Technol- ogy Agency (JST). This project finished in September 2005, and continued another program, Solution-Oriented Research for Science and Technology (SORST)ofJST.Eachchapterofthisbookiswrittenbytheresearchersand a visiting researcher of this project. WewouldliketoexpressourgratitudetoMr.HideoOhgata,Mr.Jun-ichi Hoshi,Mr.SatoshiAsada,andMr.TakanoriKamei,DepartmentofResearch Project in JST, for their kind management. We are also thankful to all the contributors for their interesting research manuscripts. We are also grate- fultoalltheresearchersofERATOQuantumComputationandInformation Projectandtheircollaborators.Moreover,weareparticularlyindebtedtoour administrativeandsupportingstaff,Mr.MichiyukiAmaike,Ms.EmiBandai, Ms. Miho Inagaki, Ms. Chie Matsumoto, Ms. Minako Ooyama, Ms. Takako Sakuragi,Ms.HirokoTakeshima,andMr.NobuyoshiUmezawafortheirkind support. Finally, we wish to thank Dr. Claus E. Ascheron of Springer-Verlag forhisexcellentmanagementforthepublicationofthisbookandhisencour- angement. Hongo, Tokyo, Hiroshi Imai January 2006 Masahito Hayashi Contents Part I Quantum Computation Quantum Identification of Boolean Oracles Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Rudy Raymond, Shigeru Yamashita .............................................. 3 1 Introduction ................................................ 3 2 Formalization............................................... 5 3 General Upper Bounds....................................... 8 4 Relation With Learning Theory ............................... 11 5 Tight Upper Bounds for Small M ............................. 12 6 Classical Lower and Upper Bounds ............................ 14 7 Concluding Remarks......................................... 15 References ..................................................... 16 Index.......................................................... 18 Query Complexity of Quantum Biased Oracles Kazuo Iwama, Rudy Raymond, Shigeru Yamashita ................. 19 1 Introduction ................................................ 19 2 Goldreich–Levin Problem and Biased Oracles ................... 21 2.1 The Model of Quantum Biased Oracles .................... 26 3 Upper Bounds of the Query Complexity of Biased Oracles With Special Conditions........................................... 27 3.1 Basic Tools for Quantum Computation .................... 27 3.2 Quantum Biased Oracles With the Same Bias Factor........ 28 3.3 Quantum Biased Oracles With Resettable Condition ........ 33 4 Lower Bounds of the Query Complexity of Biased Oracles ........ 34 5 Concluding Remarks......................................... 39 References ..................................................... 40 Index.......................................................... 42 Part II Quantum Information Quantum Statistical Inference Masahito Hayashi .............................................. 45 X Contents 1 Introduction ................................................ 45 2 Quantum State Estimation ................................... 47 2.1 State Estimation in Pure State Family .................... 47 2.2 State Estimation for Covariant Pure States Family.......... 48 2.3 State Estimation in Gaussian States Family ................ 49 2.4 State Estimation in Nonregular Family .................... 51 2.5 Estimation of Eigenvalue of Density Matrix in Qubit System . 52 3 Estimation of SU(2) Action With Entanglement................. 52 3.1 One-Parameter Case .................................... 53 3.2 Three-Parameter Case................................... 53 4 Hypothesis Testing and Discrimination......................... 54 4.1 Hypothesis Testing of Entangled State..................... 54 4.2 Distinguishability and Indistinguishability by LOCC ........ 55 4.3 Application of Quantum Hypothesis Testing................ 55 5 Experimental Application of Quantum Statistical Inference ....... 56 5.1 State Estimation in the Two-Qubit System ................ 57 5.2 Testing of Entangled State in the SPDC System ............ 57 6 Analysis on Quantum Measurement ........................... 58 6.1 Quantum Measurement With Negligible State Demolition.... 58 6.2 Quantum Universal Compression ......................... 58 References ..................................................... 59 Index.......................................................... 61 Quantum Cloning Machines Heng Fan ...................................................... 63 1 Introduction ................................................ 63 2 Buˇzek and Hillery Universal Quantum Cloning Machine.......... 63 3 N to M UQCM (Gisin and Massar) ............................ 65 4 Universal Quantum Cloning Machine for General d-Dimensional System, Werner Cloning Machine.............................. 65 5 A UQCM for d-Dimensional Quantum State Proposed by Fan et al. 66 6 Further Results About the UQCM............................. 67 6.1 UQCM for 2-Level System ............................... 68 6.2 UQCM for d-Level System ............................... 71 7 UQCM Realized in Real Physical Systems ...................... 74 8 UQCM for Identical Mixed States ............................. 79 8.1 A 2 to 3 Universal Quantum Cloning for Mixed States....... 79 8.2 General 2 to M(M >2) UQCM .......................... 81 9 Phase-Covariant Quantum Cloning Machine .................... 81 10 Transformation ............................................. 82 11 Hilbert–Schmidt Norm ....................................... 84 12 Bures Fidelity .............................................. 88 13 Quantum Cloning for x−y Equatorial Qubits .................. 90 14 Quantum Cloning Networks for Equatorial Qubits ............... 91 15 Separability of Copied Qubits and Quantum Triplicators ......... 93