Thomas G. Wong Introduction to Classical and Quantum Computing Copyright©2022ThomasWong All rights reserved. No part of this publication may be reproduced, distributed, or transmittedinanyformorbyanymeans,incudingphotocopying,recording,orother electronicormechanicalmethods,withoutthepriorwrittenpermissionofthepub- lisher,exceptinthecaseofbriefquotationsembodiedincriticalreviewsandcertain othernoncommericalusespermittedbycopyrightlaw. ISBN:979-8-9855931-0-5(Paperback) ISBN:979-8-9855931-1-2(Hardcover) LibraryofCongressControlNumber:2022900358 BookdesignbyThomasWong www.thomaswong.net PublishedbyRootedGrove,Omaha,Nebraska www.rootedgrove.com 345678910 Formystudents. Preface DearReader, Thistextbookfornewcomerswhoareinterestedinquantumcomputingasapo- tential career, but who may not be ready for advanced books or courses. The only prerequisiteforthisbookistrigonometry,alsocalledpre-calculus.Youarenotex- pectedtohavetakenadvancedmathbeyondthat,andyouarenotexpectedtohave experiencewithprogramming.So,ifyouareanadvancedhighschoolstudentora beginninguniversitystudent,thistextbookisforyou. Thatsaid,thisbookisnotmerelyaconceptualoverviewofquantumcomputing. I will teach the math and programming skills that may be missing. Since you are interestedinquantumcomputingasapotentialcareer,Iwanttoequipyouwiththe skillsyouwillneedformoreadvancedtopics. If you are more advanced, and especially if you have already studied linear al- gebra,thenyoumayfindthistextbooktooelementary.Foramoremathematically rigorousintroductiontoquantuminformationscience,IreferyoutoQuantumCom- putation and Quantum Information by Michael Nielsen and Isaac Chuang, affec- tionatelycalled“MikeandIke,”likethechewy,fruitcandywiththesamename.It isthestandardadvancedtext,andforgoodreason. Ihopethistextbookwillhelpyourealizethatyoucandoit,thatyoucanunder- stand quantum computing. I hope it will inspire you to study quantum computing more deeply, and I hope that some of you might even choose quantum computing as a career. If so, I look forward to calling you colleagues and learning from your discoveries. Thistextbookstemmedfromanintroductoryspecial-topicscoursethatItaught atCreightonUniversity,andIthankeachclassofstudentsforsharingthejourneyof developingandrefiningthecoursecontent.Imustalsothankthosewhohavetaught mequantumcomputinginbothformalandinformalroles.Icouldnothavedoneit withoutyou. TomWong v Contents 1 ClassicalInformationandComputation .......................... 1 1.1 Bits ...................................................... 2 1.1.1 Coins .............................................. 2 1.1.2 Dice ............................................... 3 1.1.3 EncodingInformation ................................ 4 1.1.4 PhysicalBits ........................................ 5 1.1.5 Binary ............................................. 6 1.1.6 ASCII.............................................. 9 1.2 LogicGates ............................................... 11 1.2.1 Single-BitGates ..................................... 11 1.2.2 Two-BitGates....................................... 13 1.2.3 LogicGatesasPhysicalCircuits........................ 15 1.2.4 MultipleGates ...................................... 21 1.2.5 UniversalGates...................................... 23 1.3 AddersandVerilog ......................................... 27 1.3.1 AddingBinaryNumbersbyHand ...................... 27 1.3.2 HalfAdder ......................................... 28 1.3.3 FullAdder.......................................... 32 1.3.4 Ripple-CarryAdder .................................. 34 1.3.5 Ripple-CarrywithFullAdders ......................... 36 1.3.6 CircuitComplexity................................... 37 1.4 CircuitSimplificationandBooleanAlgebra..................... 37 1.4.1 OrderofOperations .................................. 38 1.4.2 Association,Commutivity,andDistribution .............. 38 1.4.3 IdentitiesInvolvingZeroandOne ...................... 39 1.4.4 Single-VariableIdentities ............................. 39 1.4.5 Two-VariableIdentitiesandDeMorgan’sLaws ........... 40 1.4.6 CircuitSimplification................................. 42 1.5 ReversibleLogicGates...................................... 44 1.5.1 ReversibleGates..................................... 44 1.5.2 IrreversibleGates .................................... 45 vii viii Contents 1.5.3 ToffoliGate:AReversibleANDGate ................... 46 1.5.4 MakingIrreversibleGatesReversible ................... 48 1.6 ErrorCorrection ........................................... 52 1.6.1 ErrorsinPhysicalDevices............................. 52 1.6.2 ErrorDetection...................................... 54 1.6.3 ErrorCorrection ..................................... 55 1.7 ComputationalComplexity .................................. 58 1.7.1 AsymptoticNotation ................................. 58 1.7.2 ComplexityClasses .................................. 60 1.8 TuringMachines ........................................... 63 1.8.1 Components ........................................ 63 1.8.2 IncrementingBinaryNumbers ......................... 64 1.8.3 Church-TuringThesis ................................ 67 1.9 Summary ................................................. 71 2 OneQuantumBit .............................................. 73 2.1 QubitTouchdown:AQuantumComputingBoardGame.......... 73 2.2 Superposition.............................................. 74 2.2.1 ZeroorOne......................................... 74 2.2.2 Superposition ....................................... 76 2.2.3 ReviewofComplexNumbers.......................... 80 2.3 Measurement .............................................. 83 2.3.1 MeasurementintheZ-Basis ........................... 83 2.3.2 Normalization....................................... 85 2.3.3 MeasurementinOtherBases........................... 86 2.3.4 ConsecutiveMeasurements............................ 90 2.4 BlochSphereMapping...................................... 90 2.4.1 GlobalandRelativePhases............................ 91 2.4.2 SphericalCoordinates ................................ 92 2.4.3 CartesianCoordinates ................................ 95 2.5 PhysicalQubits ............................................ 97 2.6 QuantumGates ............................................ 98 2.6.1 LinearMaps ........................................ 98 2.6.2 ClassicalReversibleGates.............................100 2.6.3 CommonOne-QubitQuantumGates....................102 2.6.4 GeneralOne-QubitGates .............................108 2.7 QuantumCircuits ..........................................111 2.7.1 CircuitDiagrams ....................................111 2.7.2 Quirk ..............................................111 2.8 Summary .................................................112 3 LinearAlgebra ................................................115 3.1 QuantumStates ............................................115 3.1.1 ColumnVectors .....................................115 3.1.2 RowVectors ........................................116 Contents ix 3.2 InnerProducts .............................................118 3.2.1 InnerProductsAreScalars ............................118 3.2.2 Orthonormality......................................119 3.2.3 Projection,Measurement,andChangeofBasis ...........120 3.3 QuantumGates ............................................124 3.3.1 GatesasMatrices ....................................124 3.3.2 CommonOne-QubitGatesasMatrices ..................127 3.3.3 SequentialQuantumGates ............................128 3.3.4 CircuitIdentities.....................................129 3.3.5 Unitarity ...........................................131 3.3.6 Reversibility ........................................132 3.4 OuterProducts.............................................133 3.4.1 OuterProductsAreMatrices...........................133 3.4.2 CompletenessRelation ...............................135 3.5 Summary .................................................136 4 MultipleQuantumBits .........................................137 4.1 Entanglion:AQuantumComputingBoardGame................137 4.1.1 Mechanics..........................................137 4.1.2 ConnectiontoQuantumComputing.....................139 4.2 StatesandMeasurement.....................................140 4.2.1 TensorProduct ......................................140 4.2.2 KroneckerProduct ...................................142 4.2.3 MeasuringIndividualQubits...........................144 4.2.4 SequentialSingle-QubitMeasurements..................146 4.3 Entanglement..............................................147 4.3.1 ProductStates.......................................147 4.3.2 EntangledStates.....................................149 4.4 QuantumGates ............................................150 4.4.1 One-QubitQuantumGates ............................150 4.4.2 Two-QubitQuantumGates ............................153 4.4.3 ToffoliGate.........................................163 4.4.4 No-CloningTheorem.................................165 4.5 QuantumAdders ...........................................166 4.5.1 ClassicalAdder......................................166 4.5.2 MakingtheClassicalAdderaQuantumGate .............168 4.5.3 QuantumSetup......................................172 4.5.4 QuantumSum.......................................172 4.5.5 QuantumCarry......................................174 4.5.6 QuantumRipple-CarryAdder..........................175 4.5.7 CircuitComplexity...................................183 4.5.8 AddinginSuperposition ..............................184 4.6 UniversalQuantumGates....................................185 4.6.1 Definition ..........................................185 4.6.2 ComponentsofaUniversalGateSet ....................185 x Contents 4.6.3 ExamplesofUniversalGateSets .......................186 4.6.4 Solovay-KitaevTheorem..............................186 4.6.5 QuantumComputingwithoutComplexNumbers..........187 4.7 QuantumErrorCorrection ...................................188 4.7.1 Decoherence ........................................188 4.7.2 Bit-FlipCode .......................................190 4.7.3 Phase-FlipCode .....................................196 4.7.4 ShorCode ..........................................201 4.8 Summary .................................................207 5 QuantumProgramming ........................................209 5.1 IBMQuantumExperience ...................................209 5.1.1 Services............................................209 5.1.2 CircuitComposer ....................................212 5.1.3 QuantumProcessor ..................................215 5.1.4 Simulator...........................................218 5.2 QuantumAssemblyLanguage................................219 5.2.1 OpenQASM ........................................219 5.2.2 QuantumExperienceStandardHeader ..................221 5.2.3 OpenQASMinIBMQuantumExperience ...............222 5.2.4 QuantumAdder .....................................222 5.3 Qiskit ....................................................228 5.3.1 CircuitComposer ....................................228 5.3.2 QuantumLab .......................................229 5.3.3 Simulator...........................................232 5.3.4 QuantumProcessor ..................................234 5.4 OtherQuantumProgrammingLanguages ......................236 5.5 Summary .................................................236 6 EntanglementandQuantumProtocols ...........................237 6.1 Measurements .............................................237 6.1.1 ProductStates.......................................238 6.1.2 MaximallyEntangledStates ...........................238 6.1.3 PartiallyEntangledStates .............................238 6.2 BellInequalities............................................240 6.2.1 EPRParadoxandLocalHiddenVariables................240 6.2.2 BellInequalitiesandtheCHSHInequality ...............241 6.2.3 QuantumProcessorExperiment ........................246 6.2.4 OtherExperiments ...................................249 6.2.5 No-SignalingPrinciple ...............................249 6.2.6 OtherTheories ......................................251 6.3 MonogamyofEntanglement .................................253 6.3.1 ClassicalCorrelations ................................253 6.3.2 QuantumEntanglement...............................253 6.4 SuperdenseCoding .........................................255