Chapter 1 Introducing Quantum Computing

Quantum computing has been an increasingly popular research field and source of hype over the last few years. There seem to be news articles daily discussing new breakthroughs and developments in quantum computing research, promising that we can solve any number of different problems faster and with lower energy costs. Quantum computing can make an impact across society, making it an exciting time to get involved and learn how to program quantum computers and apply quantum resources to solve problems that matter.

In all of the buzz about the advantages quantum computing offers, however, it is easy to lose sight of the real scope of the advantages. We have some interesting historical precedent for what can happen when promises about a technology outpace reality. In the 1970s, machine learning and artificial intelligence suffered from dramatically reduced funding, as the hype and excitement around AI outstripped its results; this would later be called the "AI winter." Similarly, Internet companies faced the same danger trying to overcome the dot-com bust.

One way forward is by critically understanding what the promise offered by quantum computing is, how quantum computers work, and what they can do, and what is not in scope for quantum computing. Also it’s just really cool to learn about an entirely new computing model! To develop that understanding, as you read this book you’ll learn how quantum computers work by programming simulations that you can run on your laptop today. These simulations will show many of the essential elements of what we expect real commercial quantum programming to be like, while useful commercial hardware is coming online.

1.1 WHO THIS BOOK IS FOR

This book is intended for people who are interested in quantum computing and have had little to no experience with quantum mechanics, but some programming background. As we learn to write quantum simulators in Python and quantum programs in Q#, Microsoft’s specialized language for quantum computing, we’ll use traditional programming ideas and techniques to help us out. A general understanding of programming concepts like loops, functions, and variable assignments will be helpful. Similarly, we will be using some mathematical concepts from linear algebra such as vectors and matrices, to help us describe the quantum concepts — if you’re familiar with computer graphics or machine learning, many of the concepts we need here will be similar. We’ll use Python to review the most important mathematical concepts along the way, but familiarity with linear algebra will be helpful.

1.2 WHO THIS BOOK IS NOT FOR

Quantum computing is a wondrous and fascinating new field that offers new ways of thinking about computation, and new tools for solving difficult problems — this book can help you get your start in quantum computing, so that you can continue to explore and learn. That said, this book isn’t a textbook, and isn’t intended to prepare you for quantum computing research all on its own. As with classical algorithms, developing new quantum algorithms is a mathematical art as much as anything else; while we touch on the math in this book and use it to explain algorithms, there’s a variety of different textbooks available that can help you build on the ideas that we cover here.

If you’re already familiar with quantum computing, and want to go further into the physics or mathematics, we suggest one of the following resources:

1.2.1 Textbooks and other resources for learning further

1.3 HOW THIS BOOK IS ORGANIZED

The goal of this text is to enable you to start exploring and using the practical tools we have now for quantum computing. The text of this book is broken up into three main parts that build on each other.

1.4 WHY DOES QUANTUM COMPUTING MATTER?

Computing technology advances at a truly stunning pace. Three decades ago, the 80486 processor would allow users to execute 50 MIPS (million instructions per second), but today, small computers like the Raspberry Pi can reach 5,000 MIPS, while desktop processors can easily reach 50,000 to 300,000 MIPS. If you have an exceptionally difficult computational problem you’d like to solve, a very reasonable strategy is to simply wait for the next generation of processors to make your life easier, your videos stream faster, and your games more colorful.

For many problems that we care about, however, we’re not so lucky. We might hope that getting a CPU that’s twice as fast lets us solve problems twice as big, but just as with so much in life, more is different. Suppose we want to sort a list of 10 million numbers and find that it takes about 1 second. If we later want to sort a list of 1 billion numbers in one second, we’ll need a CPU that’s 130 times faster, not just 100 times. Some problems make this even worse: for some problems in graphics, going from 10 million to 1 billion points would take 13,000 times longer.

Problems as widely varied as routing traffic in a city and predicting chemical reactions get more difficult much more quickly still. If quantum computing were simply a computer that runs 1,000 times as fast, we would barely make a dent in the daunting computational challenges that we want to solve. Thankfully, quantum computers are much more interesting than that. In fact, we expect that quantum computers will likely be much slower than classical computers, but that the resources required to solve many problems scale differently, such that if we look at the right kinds of problems we can break through "more is different." At the same time, quantum computers aren’t a magic bullet, in that some problems will remain hard. For example, while it is likely that quantum computers can help us immensely with predicting chemical reactions, it is possible that they won’t be of much help with other difficult problems.

Investigating exactly which problems we can obtain such an advantage in and developing quantum algorithms to do so has been a large focus of quantum computing research. Understanding where we can find advantages by using quantum computers has recently become a significant focus for quantum software development in industry as well. Software platforms such as the Quantum Development Kit make it easier to develop software for solving problems on quantum computers, and in turn to assess how easy different problems are to solve using quantum resources.

Up until this point, it has been very hard to assess quantum approaches in this way, as doing so required extensive mathematical skill to write out quantum algorithms and to understand all of the subtleties of quantum mechanics. Now, industry has started developing software packages and even new languages and frameworks to help connect developers to quantum computing. By leveraging the entire Quantum Development Kit, we can abstract away most of the mathematical complexities of quantum computing and help people get to actually understanding and using quantum computers. The tools and techniques taught in this book allow developers to explore and understand what writing programs for this new hardware platform will be like.

Put differently, quantum computing is not going away, so understanding what scale of what problems we can solve with them matters quite a lot indeed! There are already many governments and CEOs that are convinced that quantum computing will be the next big thing in computing. Some people care about quantum attacks on cryptography, some want their own quantum computer next year. Independent of the whether or not a quantum "revolution" happens, quantum computing has and will factor heavily into decisions about how to develop computing resources over the next several decades.

1.4.1 Decisions that are strongly impacted by quantum computing.

For those of us working in tech or related fields, we increasingly must make or provide input into these decisions. We have a responsibility to understand what quantum computing is, and perhaps more importantly still, what it is not. That way, we will be best prepared to step up and contribute to these new efforts and decisions.

All that aside, another reason that quantum computing is such a fascinating topic is that it is both similar to and very different from classical computing. Understanding both the similarities and differences between classical and quantum computing helps us to understand what is fundamental about computing in general. Both classical and quantum computation arise from different descriptions of physical laws such that understanding computation can help us understand the universe itself in a new way.

What’s absolutely critical, though, is that there is no one right or even best reason to be interested in quantum computing. Whether you’re reading this because you want to have a nice nine-to-five job programing quantum computers or because you want to develop the skills you need to contribute to quantum computing research, you’ll learn something interesting to you along the way.

1.5 WHAT CAN QUANTUM COMPUTERS DO?

As quantum programmers we would like to know:

If we have a particular problem, how do we know it makes sense to solve it with a quantum computer?

We are still learning about the exact extent of what quantum computers are capable of, and thus we dont have any concrete rules to answer this question yet. So far, we have found some examples of problems where quantum computers offer significant advantages over the best known classical approaches. In each case, the quantum algorithms that have been found to solve these problems exploit quantum effects to achieve the advantages, sometimes referred to as a quantum advantage.

1.5.1 Some useful quantum algorithms

Though we’ll see several more in this book, both Grover’s and Shor’s are good examples of how quantum algorithms work: each uses quantum effects to separate correct answers to computational problems from invalid solutions. One way to realize a quantum advantage is to find ways of using quantum effects to separate correct and incorrect solutions to classical problems.

Quantum computers also offer significant benefits to simulating properties of quantum systems, opening up applications to quantum chemistry and materials science. For instance, quantum computers could make it much easier to learn about the ground state energies of chemical systems. These ground state energies then provide insight into reaction rates, electronic configurations, thermodynamic properties, and other properties of immense interest in chemistry.

Along the way to developing these applications, we have also seen significant advantages in spin-off technologies such as quantum key distribution and quantum metrology, as we will see in the next few chapters. In learning to control and understand quantum devices for the purpose of computing, we also have learned valuable techniques for imaging, parameter estimation, security, and more. While these are not applications for quantum computing in a strict sense, they go a long way to showing the values of thinking in terms of quantum computation.

Of course, new applications of quantum computers are much easier to discover when we have a concrete understanding of how quantum algorithms work and how to build new algorithms from basic principles. From that perspective, quantum programming is a great resource to learn how to discover entirely new applications.

1.6 WHAT IS A QUANTUM COMPUTER?

Let’s talk a bit about what actually makes up a quantum computer. To facilitate this, let’s briefly talk about what the term "computer" means. In a very broad sense, a computer is a device that takes data as input and does some sort of operations on that data.

There are many examples of what we have called a computer, see for some examples.

When we say the word "computer" in conversation, though, we tend to mean something more specific. Often, we think of a computer as an electronic device like the one we are currently writing this book on (or that you might be using to read this book!). For any resource up to this point that we have made a computer out of, we can model it with classical physics — that is, in terms of Newtons’s laws of motion, Newtonian gravity, and electromagnetism.

Following this perspective, we will refer to computers that are described using classical physics as classical computers. This will help us tell apart the kinds of computers we’re used to (e.g.: laptops, phones, bread machines, houses, cars, and pacemakers) from the computers that we’re learning about in this book.

Specifically, in this book, we’ll be learning about quantum computers. By the way we have formulated the definition for classical computers, if we just replace the term classical physics with quantum physics we have a suitable definition for what a quantum computer is!

The distinction between classical and quantum computers is precisely that between classical and quantum physics. We will get in to this more later in the book, but the primary difference is one of scale: our everyday experience is largely with objects that are large enough and hot enough that even though quantum effects still exist, they don’t do much on average. Quantum physics still remains true, even at the scale of everyday objects like coffee mugs, bags of flour, and baseball bats, but we can do a very good job of describing how these objects interact using physical laws like Newton’s laws of motion.

Quantum computing is the art of using small and well-isolated devices to usefully transform our data in ways that cannot be described in terms of classical physics alone. We will see in the next chapter, for instance, that we can generate random numbers on a quantum device by using the idea of rotating between different states. One way to build quantum devices is to use small classical computers such as digital signal processors (DSPs) to control properties of exotic materials.

Quantum operations are applied by sending in small amounts of microwave power and amplifying very small signals coming out of the quantum device.

Other qubit devices may differ in the details of how they are controlled, but what remains consistent is that all quantum devices are controlled from and read out by classical computers and control electronics of some kind. After all, we are ultimately interested in classical data, and so there must eventually be an interface with the classical world.

By applying quantum operations using embedded classical hardware, we can manipulate and transform quantum data. The power of quantum computing then comes from carefully choosing which operations to apply in order to implement a useful transformation that solves a problem of interest.

1.7 HOW WILL WE USE QUANTUM COMPUTERS?

It is important to understand both the potential and the limitations of quantum computers, especially given the hype surrounding quantum computation. Many of the misunderstandings underlying this hype stem from extrapolating analogies beyond where they make any sense — all analogies have their limits, and quantum computing is no different in that regard.

Indeed, any analogy or metaphor used to explain quantum concepts will be wrong if you dig deep enough. Simulating how a quantum program acts in practice can be a great way to help test and refine the understanding provided by analogies. Nonetheless, we will still leverage analogies in this book, as they can be quite helpful in providing intuition for how quantum computation works.

One especially common point of confusion regarding quantum computing is the way in which users will leverage quantum computers. We as a society now have a particular understanding of what a device called a computer does. A computer is something that you can use to run web applications, write documents, and run simulations to name a few common uses. In fact, classical computers are present in every aspect of our lives, making it it easy to take computers for granted. We don’t always even notice what is and isn’t a computer. Cory Doctorow made this observation by noting that "your car is a computer you sit inside of" (https://www.youtube.com/watch?v=iaf3Sl2r3jE).

Quantum computers, however, are likely to be much more special-purpose. Just as not all computation runs on graphical processing units (GPUs) or field-programmable gate arrays (FPGAs), we expect quantum computers to be somewhat pointless for some tasks.

Classical computing will still be around and will be the main way we communicate and interact with each other as well as our quantum hardware. Even to get the classical computing resource to interface with the quantum devices we will also need in most cases a digital to analogue signal processor as shown in .

Moreover, quantum physics describes things at very small scales (both size and energy) that are well-isolated from their surroundings. This puts some hard limitations to what environments we can run a quantum computer in. One possible solution is to keep our quantum devices in cryogenic fridges, often near absolute 0 K (-459.67 °F, or -273.15 °C). While this is not a problem at all to achieve in a data center, maintaining a dilution refrigerator isn’t really something that makes sense on a desktop, much less in a laptop or a cell phone. For this reason, it’s very likely that quantum computers will, at least for quite a while after they first become commercially available, be used through the cloud.

Using quantum computers as a cloud service resembles other advances in specialized computing hardware. By centralizing exotic computing resources in data centers, it’s possible to explore computing models that are difficult for all but the largest users to deploy on-premises. Just as high-speed and high-availability Internet connections have made cloud computing accessible for large numbers of users, you will be able to use quantum computers from the comfort of your favorite WiFi-blanketed beach, coffee shop, or even from a train as you watch majestic mountain ranges off in the distance.

1.7.1 Exotic cloud computing resources

1.8 WHAT CAN’T QUANTUM COMPUTERS DO?

Like other forms of specialized computing hardware, quantum computers won’t be good at everything. For some problems, classical computers will simply be better suited to the task. In developing applications for quantum devices, it’s helpful to note what tasks or problems are out of scope for quantum computing.

The short version is that we don’t have any hard-and-fast rules to quickly decide between which tasks are best run on classical computers, and which tasks can take advantage of quantum computers. For example, the storage and bandwidth requirements for Big Data–style applications are very difficult to map onto quantum devices, where you may only have a relatively small quantum system. Current quantum computers can only record inputs of no more than a few dozen bits, a limitation that will become more relevant as quantum devices are used for more demanding tasks. Although we expect to eventually be able to build much larger quantum systems than we can now, classical computers will likely always be preferable for problems which require large amounts of input/output to solve.

Similarly, machine learning applications that depend heavily on random access to large sets of classical inputs are conceptually difficult to solve with quantum computing. That said, there may be other machine learning applications exist that map much more naturally onto quantum computation. Research efforts to find the best ways to apply quantum resources to solve machine learning tasks are still ongoing. In general, problems that have small input and output data sizes, but large amounts of computation to get from input to output are good candidates for quantum computers.

In light of these challenges, it might be tempting to conclude that quantum computers always excel at tasks which have small inputs and outputs, but have very intense computation between the two. Notions like "quantum parallelism" are popular in media, and quantum computers are sometimes even described as using parallel universes to compute.

What this fails to communicate, however, is that it isn’t always obvious how to use quantum effects to extract useful answers from a quantum device, even if it appears to contain the desired output. For instance, one way to factor an integer classically is to list each potential factor, and to check if it’s actually a factor or not.

1.8.1 Factoring N classically.

We can speed this classical algorithm up by using a large number of different classical computers, one for each potential factor that we want to try. That is, this problem can be easily parallelized. A quantum computer can try each potential factor within the same device, but as it turns out, this isn’t yet enough to factor integers faster than the classical approach above. If you run this on a quantum computer, the output will be one of the potential factors chosen at random. The actual correct factors will occur with probability about , which is no better than the classical algorithm above.

As we’ll see in Chapter 11, though, we can improve this by using other quantum effects, however, to factor integers with a quantum computer faster than the best-known classical factoring algorithms. Much of the heavy lifting done by Shor’s algorithm is to make sure that the probability of measuring a correct factor at the end is much larger than measuring an incorrect factor. Cancelling out incorrect answers in this way is where much of the art of quantum programming comes in; it’s not easy or even possible to do for all problems we might want to solve.

To understand more concretely what quantum computers can and can’t do, and how to do cool things with quantum computers despite these challenges, it’s helpful to take a more concrete approach. Thus, let’s consider what a quantum program even is, so that we can start writing our own.

1.9 WHAT IS A PROGRAM?

Throughout this book, we will often find it useful to explain a quantum concept by first re-examining the analogous classical concept. In particular, let’s take a step back and examine what a classical program is.

We can write classical programs to break down a wide variety of different tasks for interpretation by all sorts of different computers.

Let’s take a look at what a simple "hello, world" program might look like in Python:

At its most basic, this program can be thought of as a sequence of instructions given to the Python interpreter, which then executes each instruction in turn to accomplish some effect — in this case, printing a message to the screen.

We can make this way of thinking more formal by using the dis module provided with Python to disassemble hello() into a sequence of instructions:

Each line consists of a single instruction that is passed to the Python virtual machine; for instance, the LOAD_GLOBAL instruction is used to look up the definition of the print function. The print function is then called by the CALL_FUNCTION instruction. The Python code that we wrote above was compiled by the interpreter to produce this sequence of instructions. In turn, the Python virtual machine executes our program by calling instructions provided by the operating system and the CPU.

At each level, we have a description of some task that is then interpreted by some other program or piece of hardware to accomplish some goal. This constant interplay between description and interpretation motivates calling Python, C, and other such programming tools languages, emphasizing that programming is ultimately an act of communication.

In the example of using Python to print "Hello, world!," we are effectively communicating with Guido von Rossum, the founding designer of the Python language. Guido then effectively communicates on our behalf with the designers of the operating system that we are using. These designers in turn communicate on our behalf with Intel, AMD, ARM, or whomever has designed the CPU that we are using, and so forth. As with any other use of language to communicate, our choice of programming language affects how we think and reason about programming. When we choose a programming language, the different features of that language and the syntax used to express those features mean that some ideas are more easily expressed than others.

1.10 WHAT IS A QUANTUM PROGRAM?

Like classical programs, quantum programs consist of sequences of instructions that are interpreted by classical computers to perform a particular task. The difference, however, is that in a quantum program, the task we wish to accomplish involves controlling a quantum system to perform a computation.

The instructions available to classical and quantum programs differ according to this difference in tasks. For instance, a classical program may describe a task such as loading some cat pictures from the Internet in terms of instructions to a networking stack, and eventually in terms of assembly instructions such as mov (move). By contrast, quantum languages like Q# allow programmers to express quantum tasks in terms of instructions like M (measure).

When run using quantum hardware, these programs may instruct a digital signal processor such as that shown in to send microwaves, radio waves, or lasers into a quantum device, and to amplify signals coming out of the device.

If we are to achieve a different ends, however, it makes sense for us to use a language that reflects what we wish to communicate! We have many different classical programming languages for just this reason, as it doesn’t make sense to use only one of C, Python, JavaScript, Haskell, Bash, T-SQL, or any of a whole multitude of other languages. Each language focuses on a subset of tasks that arise within classical programming, allowing us to choose a language that lets us express how we would like to communicate that task to the next level of interpreters.

Quantum programming is thus distinct from classical programming almost entirely in terms of what tasks are given special precedence and attention. On the other hand, quantum programs are still interpreted by classical hardware such as digital signal processors, so a quantum programmer writes quantum programs using classical computers and development environments.

Throughout the rest of this book, we will see many examples of the kinds of tasks that a quantum program is faced with solving or at least addressing, and what kinds of classical tools we can use to make quantum programming easier. We will build up the concepts you need to write quantum programs chapter by chapter, you can see a road map of how these concepts will build up in.

1.11 SUMMARY

In this chapter you learned: