Programming Quantum Computers: Essential Algorithms and Code Samples

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

Overview

Quantum computers are poised to kick-start a new computing revolution—and you can join in right away. If you’re in software engineering, computer graphics, data science, or just an intrigued computerphile, this book provides a hands-on programmer’s guide to understanding quantum computing. Rather than labor through math and theory, you’ll work directly with examples that demonstrate this technology’s unique capabilities.

Quantum computing specialists Eric Johnston, Nic Harrigan, and Mercedes Gimeno-Segovia show you how to build the skills, tools, and intuition required to write quantum programs at the center of applications. You’ll understand what quantum computers can do and learn how to identify the types of problems they can solve.

This book includes three multichapter sections:

• Programming for a QPU—Explore core concepts for programming quantum processing units, including how to describe and manipulate qubits and how to perform quantum teleportation.
• QPU Primitives—Learn algorithmic primitives and techniques, including amplitude amplification, the Quantum Fourier Transform, and phase estimation.
• QPU Applications—Investigate how QPU primitives are used to build existing applications, including quantum search techniques and Shor’s factoring algorithm.

Product Details

ISBN-13:	9781492039686
Publisher:	O'Reilly Media, Incorporated
Publication date:	07/23/2019
Pages:	333
Product dimensions:	6.90(w) x 9.00(h) x 0.80(d)

About the Author

Eric Johnston ("EJ") is the creator of the QCEngine quantum computation simulator, and also an acrobat and competitive gymnast. As an engineer, EJ values surprise and whimsy above all other things. He studied Electrical Engineering and Computer Science at U. C. Berkeley, and worked as a researcher in Quantum Engineering at the University of Bristol Centre for Quantum Photonics. EJ worked at Lucasfilm for two decades as a software engineer for video games and movie effects, along with occasional motion-capture stunt performance.

Alongside developing strategies for encoding information within quantum computers, Nic has also worked extensively in the foundations of quantum mechanics. His time grappling with the fundamental meaning of quantum physics has uniquely equipped him to convey (and sometimes judiciously avoid) it’s finer details. He also has 10+ years experience working in science communication, having developed numerous public lectures, workshops and educational resources aimed at conveying complex physics topics to a general audience. Along with work in other media (eg: television, radio), his public engagement work has won various awards (eg: NESTA UK Famelab winner) and been recognized by a visit to 10 downing street. He also has a lifelong passion for more conventional computing and machine learning.

Mercedes Gimeno-Segovia is a world-class researcher in quantum computing. She has a PhD in Quantum Computing Architectures from Imperial College London, and 7+ years of research experience in the field. Her PhD thesis has become a milestone in the field of linear optical quantum computing, as her design of a linear optical architecture overcame many challenges thought unsurmountable and proved to be feasible using current manufacturing techniques. Mercedes has expert knowledge on the limitations of quantum computing implementations, and is passionate about understanding every last detail of a physical system in her quest to find optimal quantum computing hardware. She enjoys science communication, writing a blog and giving public lectures to young students. She’s also an accomplished violinist, having finished qualifications in violin performance and winning an extraordinary award during her studies.

Table of Contents

Preface ix

1 Introduction 1

Required Background 1

What Is a QPU? 2

A Hands-on Approach 3

A QCEngine Primer 4

Native QPU Instructions 6

Simulator Limitations 8

Hardware Limitations 9

QPU Versus GPU: Some Common Characteristics 9

Part I Programming for a QPU

2 One Qubit 13

A Quick Look at a Physical Qubit 15

Introducing Circle Notation 18

Circle Size 18

Circle Rotation 19

The First Few QPU Operations 21

QPU Instruction: NOT 21

QPU Instruction: HAD 22

QPU Instruction: READ 23

QPU Instruction: WRITE 23

Hands-on: A Perfectly Random Bit 24

QPU Instruction: PHASE(θ) 28

QPU Instructions: ROTX(θ) and ROTY(θ) 29

COPY: The Missing Operation 29

Combining QPU Operations 30

QPU Instruction: ROOT-of-NOT 30

Hands-on: Quantum Spy Hunter 32

Conclusion 36

3 Multiple Qubits 37

Circle Notation for Multi-Qubit Registers 37

Drawing a Multi-Qubit Register 40

Single-Qubit Operations in Multi-Qubit Registers 41

Reading a Qubit in a Multi-Qubit Register 43

Visualizing Larger Numbers of Qubits 44

QPU Instruction: CNOT 45

Hands-on: Using Bell Pairs for Shared Randomness 49

QPU Instructions: CPHASE and CZ 50

QPU Trick: Phase Kickback 51

QPU Instruction: CCNOT (Toffoli) 53

QPU Instructions: SWAP and CSWAP 54

The Swap Test 55

Constructing Any Conditional Operation 58

Hands-on: Remote-Controlled Randomness 61

Conclusion 65

4 Quantum Teleportation 67

Hands-on: Lets Teleport Something 67

Program Walkthrough 73

Step 1 Create an Entangled Pair 74

Step 2 Prepare the Payload 74

Step 3.1 Link the Payload to the Entangled Pair 75

Step 3.2 Put the Payload into a Superposition 76

Step 3.3 READ Both of Alice's Qubits 76

Step 4 Receive and Transform 77

Step 5 Verify the Result 78

Interpreting the Results 79

How Is Teleportation Actually Used? 80

Fun with Famous Teleporter Accidents 81

Part II QPU Primitives

5 Quantum Arithmetic and Logic 85

Strangely Different 85

Arithmetic on a QPU 87

Hands-on: Building Increment and Decrement Operators 88

Adding Two Quantum Integers 91

Negative Integers 92

Hands-on: More Complicated Math 94

Getting Really Quantum 95

Quantum-Conditional Execution 95

Phase-Encoded Results 96

Reversibility and Scratch Qubits 98

Uncomputing 100

Mapping Boolean Logic to QPU Operations 103

Basic Quantum Logic 103

Conclusion 106

6 Amplitude Amplification 107

Hands-on: Converting Between Phase and Magnitude 107

The Amplitude Amplification Iteration 110

More Iterations? 111

Multiple Flipped Entries 114

Using Amplitude Amplification 120

AA and QFT as Sum Estimation 120

Speeding Up Conventional Algorithms with AA 120

Inside the QPU 121

The Intuition 121

Conclusion 123

7 QFT: Quantum Fourier Transform 125

Hidden Patterns 125

The QFT, DFT, and FFT 127

Frequencies in a QPU Register 128

The DFT 132

Real and Complex DFT Inputs 134

DFT Everything 135

Using the QFT 140

The QFT Is Fast 140

Inside the QPU 146

The Intuition 148

Operation by Operation 149

Conclusion 153

8 Quantum Phase Estimation 155

Learning About QPU Operations 155

Eigenphases Teach Us Something Useful 156

What Phase Estimation Does 158

How to Use Phase Estimation 158

Inputs 159

Outputs 161

The Fine Print 162

Choosing the Size of the Output Register 162

Complexity 163

Conditional Operations 163

Phase Estimation in Practice 163

Inside the QPU 164

The Intuition 165

Operation by Operation 167

Conclusion 169

Part III QPU Applications

9 Real Data 173

Noninteger Data 174

QRAM 175

Vector Encodings 179

Limitations of Amplitude Encoding 182

Amplitude Encoding and Circle Notation 184

Matrix Encodings 185

How Can a QPU Operation Represent a Matrix? 185

Quantum Simulation 186

10 Quantum Search 191

Phase Logic 192

Building Elementary Phase-Logic Operations 194

Building Complex Phase-Logic Statements 195

Solving Logic Puzzles 198

Of Kittens and Tigers 198

General Recipe for Solving Boolean Satisfiability Problems 202

Hands-on: A Satisfiable 3-SAT Problem 203

Hands-on: An Unsatisfiable 3-SAT Problem 206

Speeding Up Conventional Algorithms 208

11 Quantum Supersampling 211

What Can a QPU Do for Computer Graphics? 211

Conventional Supersampling 212

Hands-on: Computing Phase-Encoded Images 214

A QPU Pixel Shader 215

Using PHASE to Draw 216

Drawing Curves 218

Sampling Phase-Encoded Images 220

A More Interesting Image 223

Supersampling 223

QSS Versus Conventional Monte Carlo Sampling 227

How QSS Works 227

Adding Color 232

Conclusion 233

12 Shor's Factoring Algorithm 235

Hands-on: Using Shor on a QPU 236

What Shor's Algorithm Does 237

Do We Need a QPU at All? 238

The Quantum Approach 240

Step by Step: Factoring the Number 15 242

Step 1 Initialize QPU Registers 243

Step 2 Expand into Quantum Superposition 244

Step 3 Conditional Multiply-by-2 246

Step 4 Conditional Multipy-by-4 248

Step 5 Quantum Fourier Transform 251

Step 6 Read the Quantum Result 254

Step 7 Digital Logic 255

Step 8 Check the Result 257

The Fine Print 257

Computing the Modulus 257

Time Versus Space 259

Coprimes Other Than 2 259

13 Quantum Machine Learning 261

Solving Systems of Linear Equations 262

Describing and Solving Systems of Linear Equations 263

Solving Linear Equations with a QPU 264

Quantum Principle Component Analysis 274

Conventional Principal Component Analysis 274

PCA with a QPU 276

Quantum Support Vector Machines 280

Conventional Support Vector Machines 280

SVM with a QPU 284

Other Machine Learning Applications 289

Part IV Outlook

14 Staying on Top: A Guide to the Literature 293

From Circle Notation to Complex Vectors 293

Some Subtleties and Notes on Terminology 295

Measurement Basis 297

Gate Decompositions and Compilation 298

Gate Teleportation 300

QPU Hall of Fame 300

The Race: Quantum Versus Conventional Computers 301

A Note on Oracle-Based Algorithms 302

Deutsch-Jozsa 302

Bernstein-Vazirani 303

Simon 303

Quantum Programming Languages 303

The Promise of Quantum Simulation 305

Error Correction and NISQ Devices 305

Where Next? 306

Books 306

Lecture Notes 306

Online Resources 307

Index 309