book

Programming Quantum Computers

by Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia

July 2019

Intermediate to advanced

333 pages

8h 13m

English

O'Reilly Media, Inc.

Read now

Unlock full access

How This Book Is StructuredConventions Used in This BookUsing Code ExamplesO’Reilly Online LearningHow to Contact UsAcknowledgments
Required BackgroundWhat Is a QPU?A Hands-on ApproachA QCEngine PrimerNative QPU InstructionsSimulator LimitationsHardware LimitationsQPU Versus GPU: Some Common Characteristics
A Quick Look at a Physical QubitIntroducing Circle NotationCircle SizeCircle RotationThe First Few QPU OperationsQPU Instruction: NOTQPU Instruction: HADQPU Instruction: READQPU Instruction: WRITEHands-on: A Perfectly Random BitQPU Instruction: PHASE(θ)QPU Instructions: ROTX(θ) and ROTY(θ)COPY: The Missing OperationCombining QPU OperationsQPU Instruction: ROOT-of-NOTHands-on: Quantum Spy HunterConclusion
Circle Notation for Multi-Qubit RegistersDrawing a Multi-Qubit RegisterSingle-Qubit Operations in Multi-Qubit RegistersReading a Qubit in a Multi-Qubit RegisterVisualizing Larger Numbers of QubitsQPU Instruction: CNOTHands-on: Using Bell Pairs for Shared RandomnessQPU Instructions: CPHASE and CZQPU Trick: Phase KickbackQPU Instruction: CCNOT (Toffoli)QPU Instructions: SWAP and CSWAPThe Swap TestConstructing Any Conditional OperationHands-on: Remote-Controlled RandomnessConclusion
Hands-on: Let’s Teleport SomethingProgram WalkthroughStep 1: Create an Entangled PairStep 2: Prepare the PayloadStep 3.1: Link the Payload to the Entangled PairStep 3.2: Put the Payload into a SuperpositionStep 3.3: READ Both of Alice’s QubitsStep 4: Receive and TransformStep 5: Verify the ResultInterpreting the ResultsHow Is Teleportation Actually Used?Fun with Famous Teleporter Accidents
Strangely DifferentArithmetic on a QPUHands-on: Building Increment and Decrement OperatorsAdding Two Quantum IntegersNegative IntegersHands-on: More Complicated MathGetting Really QuantumQuantum-Conditional ExecutionPhase-Encoded ResultsReversibility and Scratch QubitsUncomputingMapping Boolean Logic to QPU OperationsBasic Quantum LogicConclusion
Hands-on: Converting Between Phase and MagnitudeThe Amplitude Amplification IterationMore Iterations?Multiple Flipped EntriesUsing Amplitude AmplificationAA and QFT as Sum EstimationSpeeding Up Conventional Algorithms with AAInside the QPUThe IntuitionConclusion
Hidden PatternsThe QFT, DFT, and FFTFrequencies in a QPU RegisterThe DFTReal and Complex DFT InputsDFT EverythingUsing the QFTThe QFT Is FastInside the QPUThe IntuitionOperation by OperationConclusion

Learning About QPU OperationsEigenphases Teach Us Something UsefulWhat Phase Estimation DoesHow to Use Phase EstimationInputsOutputsThe Fine PrintChoosing the Size of the Output RegisterComplexityConditional OperationsPhase Estimation in PracticeInside the QPUThe IntuitionOperation by OperationConclusion
Noninteger DataQRAMVector EncodingsLimitations of Amplitude EncodingAmplitude Encoding and Circle NotationMatrix EncodingsHow Can a QPU Operation Represent a Matrix?Quantum Simulation
Phase LogicBuilding Elementary Phase-Logic OperationsBuilding Complex Phase-Logic StatementsSolving Logic PuzzlesOf Kittens and TigersGeneral Recipe for Solving Boolean Satisfiability ProblemsHands-on: A Satisfiable 3-SAT ProblemHands-on: An Unsatisfiable 3-SAT ProblemSpeeding Up Conventional Algorithms
What Can a QPU Do for Computer Graphics?Conventional SupersamplingHands-on: Computing Phase-Encoded ImagesA QPU Pixel ShaderUsing PHASE to DrawDrawing CurvesSampling Phase-Encoded ImagesA More Interesting ImageSupersamplingQSS Versus Conventional Monte Carlo SamplingHow QSS WorksAdding ColorConclusion
Hands-on: Using Shor on a QPUWhat Shor’s Algorithm DoesDo We Need a QPU at All?The Quantum ApproachStep by Step: Factoring the Number 15Step 1: Initialize QPU RegistersStep 2: Expand into Quantum SuperpositionStep 3: Conditional Multiply-by-2Step 4: Conditional Multipy-by-4Step 5: Quantum Fourier TransformStep 6: Read the Quantum ResultStep 7: Digital LogicStep 8: Check the ResultThe Fine PrintComputing the ModulusTime Versus SpaceCoprimes Other Than 2
Solving Systems of Linear EquationsDescribing and Solving Systems of Linear EquationsSolving Linear Equations with a QPUQuantum Principle Component AnalysisConventional Principal Component AnalysisPCA with a QPUQuantum Support Vector MachinesConventional Support Vector MachinesSVM with a QPUOther Machine Learning Applications
From Circle Notation to Complex VectorsSome Subtleties and Notes on TerminologyMeasurement BasisGate Decompositions and CompilationGate TeleportationQPU Hall of FameThe Race: Quantum Versus Conventional ComputersA Note on Oracle-Based AlgorithmsDeutsch-JozsaBernstein-VaziraniSimonQuantum Programming LanguagesThe Promise of Quantum SimulationError Correction and NISQ DevicesWhere Next?BooksLecture NotesOnline Resources

Content preview from Programming Quantum Computers

Chapter 12. Shor’s Factoring Algorithm

If you’d heard about one application of quantum computing before you picked up this book, there’s a good chance it was Shor’s factoring algorithm.

Quantum computing was mostly considered to be of academic, rather than practical, interest until Peter Shor’s 1994 discovery that a sufficiently powerful quantum computer can find the prime factors of a number exponentially faster than any conventional machine. In this chapter, we take a hands-on look at one specific implementation of Shor’s QPU factoring algorithm.

Far from being a mere mathematical curiosity, the ability to quickly factorize large numbers can help break the Rivest–Shamir–Adleman (RSA) public-key cryptosystem. Anytime you spin up an ssh session you’re making use of RSA. Public-key cryptosystems like RSA work by a process wherein a freely available public key can be used by anybody to encrypt information. But once encrypted, the information can only be decrypted using a secret, privately held key. Public-key cryptosystems are often compared to an electronic version of a mailbox. Imagine a locked box with a slit allowing anyone to post (but not retrieve) a message, and a door with a lock to which only the owner has the key. It turns out that the task of finding the prime factors of a large number N works really well as part of a public-key cryptosystem. The assurance that someone can only use the public key to encrypt and not to decrypt information rests on the assumption that finding ...