Some Other Directions for Quantum Computing

This book is about gate-based quantum computing. In each example, we prepare qubits and apply operations with gates. Most of the gates perform reversible quantum operations. The main exceptions to the reversibility rule are the measurement gates, which destroy superposition and yield solutions to our intricate, mathematical problems.

Gate-based quantum computing is great for certain problems such as cracking RSA encryption, but, as far as we know, many other problems are more easily solved using classical computing. To search for a value in an unsorted list, you can run Grover’s algorithm on a quantum computer, but to find out how much tax you owe the government this year, you should run a Java program on a classical computer. (In fact, doing all your tax calculations by hand would probably be more efficient than relying on any kind of quantum computer for help.)

Nevertheless, gate-based quantum computing is an example of general...

What is reducibility?

In The Karate Kid (Sony Pictures, 1984), Mr. Miyagi teaches Daniel to do defensive blocks by having him repeatedly wax Miyagi’s car. The idea is to learn how to block an attack, starting by training yourself to apply and remove car wax. Start with the problem you want to solve (blocking an attacker’s approach) and turn it into a different problem (rubbing metal to make it shine). At first sight, the two problems seem to be unrelated, but in the movie, Daniel learns that the skills underlying both problems are identical. A solution to the waxing problem tells Daniel how to solve the defensive blocking problem.

In the formal terminology of algorithms, we might say that the defensive blocking problem is reducible to the car-waxing problem. The word reducible suggests that, in some way, waxing a car is simpler than defensive blocking. Indeed, the simplicity of polishing metal is what helps Daniel to learn movements so naturally.

In the same way...

Quantum simulation

Wouldn’t it be nice if we could move current through materials with no resistance at all? The implications for the world’s energy needs would be enormous. We could deliver energy to homes with no loss along the way. Batteries would be able to store their charges for indefinite amounts of time.

In fact, we have created electricity with no resistance, but the only materials that we know can do this require temperatures near absolute zero. The energy we need to cool these materials to very low temperatures far outweighs the benefits we’d gain in any widely used applications. So, for now, our techniques for dealing with electricity involve lots of wasteful energy loss.

The holy grail for electricity would be a high-temperature superconductor – a kind of material that conducts electricity with no resistance at temperatures that are practical for everyday use. We know a lot about the physics behind superconductivity. We have a formula...

Quantum annealing

With rising concerns about climate change, it’s useful to think about the way temperature varies by geographic location. Figure 10.1 has a fictional map of temperatures in a particular region.

Figure 10.1 – A temperature map

Our goal is to find the coldest spot on this map. One strategy would be to start at an arbitrary point and work our way to points of ever-decreasing temperature. This is called a greedy method because the algorithm always moves in a direction that yields a better value.

The arrow in Figure 10.1 shows a possible path using the greedy approach. The arrow starts at the top of the map, moves downward until it hits the center of the northernmost region, and then stops. The arrow stops because, having reached this point, movement in any direction would raise the temperature. The algorithm has found a local extreme point without ever getting near the coldest spot on the map.

Annealing is a way of moving slowly toward and...

Quantum neural nets

Your brain is made up of approximately 200 billion cells, of which about half are neurons. Figure 10.3 illustrates an interaction between two neurons.

Figure 10.3 – Communicating neurons

A neuron communicates with a neighboring neuron by sending a chemical substance (a neurotransmitter) out of its axon. The neurotransmitter leaps across a synapse – a little gap between the sending and receiving neuron. On the other side of the synapse, a dendrite receives the neurotransmitter and then forwards a signal to the receiving neuron’s soma. Receipt of this signal may cause an electrical spike inside the receiving neuron. If the receiving neuron spikes, it sends a signal along its own axon, and the process continues.

In 1943, researchers named McCulloch and Pitts [1] described an electrical device whose behavior modeled that of a neuron. An artificial neuron has variable weights, as shown in Figure 10.4.

Figure...

Solving unsolvable problems

In 1936, Alan Turing wrote a landmark paper [4] in which he showed that a particular well-defined mathematical problem is impossible to solve. In this case, the word “impossible” means that no classical algorithm running for a finite amount of time will ever reach a final, concluding step. To prove his claim, Turing created a precise definition of what it means to be an algorithm and went on to devise a problem that contains its own circular knot.

Consider the following sentence:

Is “no” the correct answer to the question that you’re reading right now?

This sentence is like a double-edged sword:

• If you answer “yes” to the sentence, you’re saying “Yes. It’s true that “no” is the correct answer.” But, if “no” is really the correct answer, your utterance of the word “yes” is incorrect.
• If you answer “no” to...

Summary

Here you are in the last section of this book! I congratulate you on your effort (even if you skipped over many of the sections). Quantum computing isn’t easy to understand, and you’ve taken the first step. You’ve explored algorithms using matrix algebra, and now you’re ready for more.

There’s no shortage of published information about quantum computing. With a quick search of the web, you can find blogs, videos, papers, and much more. For elegant descriptions of this book’s algorithms, focus your attention on linear algebra. For insight into the science underlying quantum computing, read more about quantum physics. For information about the engineering challenges facing quantum computing professionals, learn about error detection and error correction. To practice writing quantum computing code, check the Qiskit documentation pages. And don’t forget to investigate some other platforms for programming quantum computing algorithms...

References

[1] McCulloch, W.S., Pitts, W, (1943). A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics 5, pp. 115-133 https://doi.org/10.1007/BF02478259.

[2] Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), pp. 386-408. https://doi.org/10.1037/h0042519.

[3] Krizhevsky, A., Sutskever, I., Hinton, G.E. (2017-05-24). ImageNet classification with deep convolutional neural networks (PDF) available at https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf. Communications of the ACM. 60 (6): pp. 84-90. doi:10.1145/3065386. ISSN 0001-0782. S2CID 195908774.

[4] Turing, A. M. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Volume s2-42, Issue 1, pp. 230-265, https://doi.org/10.1112/plms/s2-42.1.230.

[5] Davis, M. (1973...