Introduction
The question whether social distancing works is settled - but we also know it cannot continue indefinitely. Worldwide lockdowns eventually have to be eased in a way that reduces the resurgence of infections, the so called second wave. Currently, the most promising method of limiting the spread of infection is contact tracing where exposed people are quickly identified and quarantined. While the citizens of China, South Korea, Taiwan, Singapore and many other countries may be ambivalent towards the state keeping tabs on where they've been and whom they've been in contact with, the populace of many other countries, especially the US, will be hard pressed to submit to such intrusions of privacy. Further, as recently reported, trying to manually chase down those who came in contact with whom is a losing battle. To keep the spread of infection in check, then, clearly another solution is called for.
Recently, Google and Apple released an Exposure Notification framework that uses your phone's bluetooth feature to exchange IDs with nearby phones. Protocols, such as the Decentralized Privacy-Preserv ing ProtectionTracing (DP-3T), implement these frameworks to warn users if they have come in contact with an infected person. Your phone compares these IDs against a database of IDs from infected people and alerts the user if they need to isolate themselves. The infected person and the exposed people's identities are never revealed to any authority. This protocol is appealing and has all the hallmarks of gaining widespread attention. The method, though, does have a few shortcomings in that the citizens have to work through an approved government healthcare agency.The method may also be vulnerable to spoofing attacks.
Quantum computing offers an alternative that makes it virtually impossible for any system to maintain any kind of record of the IDs and also impervious to any attacks. Entanglement - arguably one of the most mysterious phenomena of quantum mechanics that baffled even Einstein -undergirds a mechanism that makes free-from-prying-eyes contact tracing a reality. To pull entanglement up from the microscopic world of subatomic particles and coax it for a real world computer application requires us to step back and get our arms around quantum computing.
This article gets into more detail than what you may be used to seeing. The reason is that a certain amount of reader-fatigue has set in from hearing the same "awesomeness" refrains of quantum computing - quantum mechanics offers a new way to model bits that considers all possible solutions at the same time, yada yada yada - over and over again. So I'll give a deeper and more intuitive glimpse of this new technology and show you why it can solve problems that challenge the best classical computers. To this end, as explained in my forthcoming book on quantum computing, I propose a new way of looking at qubits that is visual and familiar to both computer scientists and programmers. I describe how to think of qubits like their classical equivalents but with some special properties that are easier to work with than the typical way using Bloch Spheres. You'll see how computers based on quantum mechanics can do everything that a classical computer can and also things that have no classical equivalent. You'll learn that these quantum specific features gives quantum computers an edge over classical computing.
The quantum programs you'll write with this new conceptual model behave exactly like those you would write using the standard textbook methods. But, your intuition for when and how to introduce quantum effects is greatly boosted. Although mastering the mathematics of quantum computing is important, it's even more crucial to intuitively understand the subject matter so that you can work out algorithms for your own applications. Thus, using these principles, I'll show you how to design an algorithm to make contact tracing secure and safe from government intrusion.
NOTE: Content and figures adapted and excerpted from my forthcoming book: Quantum Computing: Program Next-Gen Computers for Hard, Real-World Applications https://pragprog.com/book/nmquantum/quantum-computing Copyright @ 2020 The Pragmatic Programmers LLC. Reproduced with the permission of the publisher.
A Foolproof Way to Not Get Spooked by Quantum Computing
Qubits, or quantum bits are the equivalent of classical bits that drives quantum computing. But, unlike their classical counterparts, quantum bits are tricky to describe. Almost all textbooks, articles or explainer videos immediately jump to math to define qubits as if the key to understanding them lies in unraveling abstruse equations. The usual approach makes quantum computing feel as an alien landscape for most computer programmers even though it's applied to traditional computational tasks. Without properly motivating the intuition quantum mechanics brings to bear, designing algorithms that capitalize on them to solve hard problems that are out of reach of today's computers is frustrating.
Although the behavior of quantum bits are governed by quantum mechanics, from a quantum computing standpoint, their actions can be boiled down to commonplace operations. To fix ideas, I use a pentagon for a |0> qubit:
And, a triangle for a |1> qubit:
When these shapes represent classical bits, their orientations are always fixed.
A classical NOT gate, for example, toggles a pentagon with a triangle as shown below:
With quantum bits, these shapes rotate. For example, a triangle that's rotated, say, 45 degrees anti-clockwise is shown below:
Although we'll learn that rotations of qubits play a crucial role in quantum computing, the defining characteristic of qubits is their ability to be in both states at the same time - that is, they are suspended in a superposition of both |0> and |1> states.
What does this really mean? How can something be two things at the same time?
You may have heard of Schrodinger's cat in a closed box. Someone outside the box wouldn't have a clue whether the cat is dead or alive. So, for this person, their lack of knowledge allows them to think of the cat as being in two states - dead or alive. It's only when the box is opened would they know if the cat is breathing.
This concept of superposition sounds thrilling but it's not apparent how it could solve problems. So how exactly does one go about making any sense of superposition when designing a computer algorithm to solve a real world application, such as contact tracing?
Quantum Superposition
As described in my forthcoming book, the pentagons and triangles give a way to get past these esoteric philosophical arguments to more practical considerations. Specifically, to model these superposition states from a computational viewpoint, think of a quantum bit that is both |0> and |1> at the same time as shown below:
The pentagons and triangles indicate that the quantum bit is in two states at the same time. But, as with the cat in the box, the moment you try to ascertain its state, it randomly collapses to either a pentagon, the |0> state, or a triangle, the |1> state.
The quantum state shown above has a single pentagon and a single triangle. In general, however, a quantum state can have several pentagons and triangles, and some may even be rotated. For example, the quantum state below has seven |0> pentagons and three inverted |1> triangles:
The only restriction is that quantum states are made up of only pentagons and triangles. No other shapes are allowed.
Basic Idea of Quantum Instructions
The essential objective in quantum computing is to apply physical effects - such as a precisely timed burst of a magnetic field - to tilt the odds that favor the quantum bit collapsing to one or the other state. A quantum program is a sequence of these physical effects that takes qubits from some initial state to one that solves the computational problem.
Fortunately, you don't need to know quantum mechanics to implement these physical effects. A standard set of devices, called quantum gates, encapsulate the quantum principles. These principles essentially amount to rotation of qubits. Like classical logic gates, these form the building blocks of quantum circuits that manipulate qubits to perform computational tasks. A quantum program encodes this circuit so that it runs on a quantum computer.
For example, if a quantum bit has both a pentagon |0> and a triangle |1>, then the Z-gate only rotates the triangle |1> by 180 degrees but leaves the pentagon |0> alone as shown in the following figure:
(On the right qubit, the faded triangle |1> behind the triangle |1> in the foreground indicates its original position.)
A T-gate, on the other hand, rotates the triangle |1> by 45 degrees anti-clockwise as shown below:
(On the right qubit, the faded triangle |1> behind the triangle |1> in the foreground indicates its original position.)
There are several other quantum gates, such as the S, S-dagger and T-dagger gates, that rotate the triangle |1> by other amounts.
In quantum computing, rotations underpin effects that have no classical equivalent. For example, if a quantum bit has 2 triangles, one inverted and the other in the original orientation, they cancel out as shown in the figure below:
Quantum gates do more than just rotate qubits though. A signature operation is to take a "pure" qubit, such as one having only a pentagon |0>, and splitting it so that the qubit ends up with both pentagons and triangles. For example, when the H, or Hadamard gate, acts on a pentagon |0> qubit, it splits it into a pentagon|0> and triangle |1> as shown below:
Thus, starting from a "pure" state - for example, |0> - the H-gate puts the qubit in a quantum state having both a pentagon and a triangle.
Although you cannot directly see the qubit in two states, you can write a computer program that validates the notion that the state is not single-valued like a classical state.
For example consider the quantum circuit that acts on a qubit initialized to a pure state - for instance, |0> - as shown below:
This circuit has only a single quantum register, q[0] , initialized with a |0> qubit, and a single-bit classical register, c[0]. The Measure-gate collapses the quantum state after the H-gate acts on the it and records the corresponding binary value that it settles down to in the classical register c[0].
To run this circuit on a quantum computer, you translate the circuit to a set of executable instructions, the program.There are several vendors that let you execute quantum programs including Amazon, Google, IBM and Microsoft. (If you are just starting out with quantum computers, IBM lets you master quantum concepts by letting you write programs using a drag-and-drop interface.)
When you run this program on a quantum computer, the Measure-gate collapses the qubit after its acted on by the H-gate and records the collapsed state in the classical register c[0]. When the qubit collapses, as the qubit has a pentagon and a triangle, one of them is randomly selected as the collapsed state. Thus, if you run this program once, you'll only see of them - either a 0 or a 1 - in the classical register. If you run this program several times, you'll see a 0 in about half the runs and a 1 in the other half as shown in the output below:
These are the results of running the above program on IBM's quantum computer. Since we ran this program on an actual quantum computer as opposed to a simulator, there is a slight difference in the number of times a 0 is recorded versus that of a 1.
Admittedly, at this point it seems that the H-gate is nothing but a glorified binary coin toss and the significance of the qubit holding both a pentagon and a triangle at the same time may not be fully appreciated. But, starting from the next section, you'll see the pivotal role that qubits holding pentagons and triangles simultaneously as well as rotating them plays in quantum computing.
Boolean Logic Operations with Qubits
The H-gate takes a "pure'" |0> and puts the qubit into a state that holds both pentagons and triangles. Although, when you measured the state you only see one of them. In this section you'll learn that qubits holding both pentagons and triangles at the same time allows them to perform standard logic operations. That is, a quantum computer can do whatever a classical computer can do. But, because quantum computers are based on quantum mechanics, I'll also show you how quantum computers can do things that can never be done with classical computers leading to truly new ways to solve hard and challenging problems.
As you saw in the previous section, the H-gate is a qubit splitter. But, it acts differently on a |0> qubit than a |1> qubit. When it splits a |1> qubit, the triangle is inverted as shown in the figure below:
This seemingly minor detail strikes at the root of what makes quantum computing possible.
Consider the following quantum circuit:
In this circuit, the |0> qubit in the quantum register q[0] is acted on by a sequence of quantum gates - H, Z and H. The resulting state of the qubit is inspected by the Measure-gate on the right and recorded in the classical register c[0].
We'll use pentagons and triangles to analyze this circuit and figure out what state the |0> in quantum register q[0] ends up in.
The first H-gate on the left splits the |0> qubit as shown below:
Next, the Z-gate rotates the triangle |1> by 180 degrees:
Finally, the H-gate on the right splits both the pentagon |0> and the triangle |1> as follows:
On the left is the quantum state of the qubit after it's acted on by the H and Z gates. The second H-gate then splits both the pentagon |0> and the triangle |1> ending up with 4 shapes: the first two from the splitting of the pentagon |0>, and the latter two from the splitting of the inverted triangle |1>.
Since the H-gate splits a |1> into a pentagon |0> and an inverted triangle |1>, it'll split an inverted triangle |1> into an inverted pentagon |0> and an inverted-inverted triangle |1>. That is, a triangle that goes back to its non-inverted orientation.
Key Concept: The inverted pentagon cancels with the non-inverted one leaving a quantum state with 2 triangles as shown below:
So, the final quantum state of the qubit is 2 triangles. Note that all of this canceling happens immediately and without the need to invoke any special quantum instruction.
When the Measure-gate inspects the state of the qubit, it'll only find a triangle. Hence, it logs a 1 in the classical register c[0] even though the quantum state ended up with 2 triangles.
Had you started out with a |1> instead, you'd find that the sequence of gates - H-Z-H - results in the qubit ending up with 2 pentagons. And, the Measure-gate would record a 0 in the classical register c[0].
In other words, this sequence of gates operates takes a |0> qubit to |1>, and vice-versa. That is, this sequence of quantum gates performs a logical NOT operation. (Since the NOT operation is common in quantum programming, you can use a specially designated gate, X, instead of the sequence of H-Z-H gates.)
For multi-bit logical operations, such as AND, OR, XOR, SWAP and others, the Controlled-NOT or CNOT-gate and the Controlled-Controlled-NOT or CCNOT-gate are used. These gates perform a NOT operation on a designated qubit, the target, if the quantum state on another qubit, the control, is |1>. If the quantum state on the control is |0>, the quantum state on the target is left alone.
The CNOT-gate is represented as follows:
The following figure summarizes the operation of the CNOT-gate:
The target qubits, in the two bottom circuits highlight that they have been switched because the control qubit is |1>.
The CCNOT-gate is a CNOT-gate with an additional control qubit, as shown in the following figure:
For the $CCNOT$-gate, both control qubits must be |1> for the target qubit to switch states. If either control qubit is|0>, the target qubit is not affected. So, as in the CNOT-gate case, the CCNOT-gate behaves like a NOT-gate when both control bits are |1>.
The CNOT-gate can be configured to perform the XOR (exclusive OR) operation. And, the CCNOT-gate forms the basis for the logical AND and logical OR operations. (See my book for details on how to make the CNOT and CCNOT-gates perform Boolean logic operations.)
Thus, by splitting, rotating and canceling pentagons and triangles, phenomena that are purely quantum and have no classical counterparts, quantum computers can do everything that a classical computer can do.
If all that quantum computers did was do the same computations but in a different way, they wouldn't be terribly exciting. In the next section, you'll begin to see the reason why quantum computers deliver high-octane computational performance.
Multi-Qubit Quantum Superposition
In the previous section, you saw that the Hadamard or H-gate takes a "pure" qubit - |0> or |1> - and splits it putting the qubit in a quantum state that now contains both pentagons and triangles - a superposition - although in the case of splitting the |1> qubit, the triangle is inverted or rotated by 180 degrees.
Just as the seemingly minor difference in the way the H-gate splits a |0> qubit versus a |1> qubit, splitting two qubits considerably thickens the plot. Unlike classical computers where operations on one bit doesn't affect others in the system, in quantum computing an action on one influences the states of others. To handle this characteristic of quantum bits, we must think of all possible states of the quantum bits at once instead of the classical way of thinking of one-solution-at-a-time approach. To help us get comfortable with this shift in mindset, consider the following circuit in which two qubits are split as follows:
Key Concept: Each H-gate splits the |0> qubit. But, in quantum computing, you don't treat these split pentagons and triangles as individual units. Rather, each shape in the top qubit pairs up with each shape in the bottom qubit forming the four combinations as shown below:
These combinations, called qubelet combinations, form a mega-qubit.
If we feed these qubits to other gates, then those gates operate on the entire mega-qubit. That is, the quantum gates act on all four combinations simultaneously.
When more qubits are split, the mega-qubit automatically holds the combinations formed from the pentagons and triangles from all the split qubits. For example, when 3 qubits are split by the H-gate, the resulting mega-qubit is shown below:
Each combination is formed by taking a shape from each of the three qubits in turn. This gives 8 combinations in the mega-qubit on the right in the above figure.
In general, as the number of qubits you split becomes large, the number of combinations in the mega-qubit becomes astronomical and well beyond the means of classical computers. But, this gigantic increase in complexity has no impact for quantum computers which is hard-wired to deal with all combinations simultaneously regardless of how many there are.
This ability to simultaneously deal with all combinations or possible quantum states of the qubits offers a spectacular way to routinely solve industrial-scale applications that even today's supercomputers find impossible to tackle: in a quantum computer all Boolean operations are applied to possible states at the same time unlike a classical computer in which only one combination of states at a time are operated on.
Quantum Entanglement
The mega-qubit is not just a nifty bookkeeping device to track how gates affect all possible states at the same time. It underpins a central tenet of quantum mechanics that makes a quantum computer not just another hyper-fast computer but one that solves problems in ways that cannot be duplicated on classical computers.
To understand this uniquely quantum phenomena and how it forms the linchpin for a foolproof contact tracing algorithm, consider the following quantum circuit:
The H-gate splits the pentagon in the top qubit so that it now has a pentagon and a triangle. These pair up with the pentagon in the bottom qubit to form a mega-qubit with two pairs, as shown on the left mega-qubit in the following figure:
To work out the mega-qubit after the CNOT-gates, analyze each combination individually even though the actual quantum gate acts on them simultaneously. The new mega-qubit is the aggregate of the CNOT-gate acting on each input combination.
The top shape in each combination is fed to the CNOT-gate’s control qubit and the bottom shape is passed to its target qubit. Since the left pair has a pentagon on the top, it won’t be affected by the CNOT-gate. The right pair, however, has a triangle. Thus, the CNOT-gate will switch the bottom pentagon to a triangle. As a result, the mega-qubit on the right, after the CNOT-gate has operated on it, will have two pairs: one with both pentagons and the other with both triangles.
When the Measure-gates inspect the state of these qubits, they effectively select one of the two combinations from the mega-qubit. So, either a 0 is logged in both classical registers or a 1.
Key Concept: In each case, though, if you know the state recorded in one register, you can deduce the state in the other without actually measuring the second qubit. In other words - and this is the key concept - the quantum circuit shown previously entangles the states of the two qubits.
In fact, if you look at each qubit individually, there is nothing to suggest that one is influencing the other. For example, in the above figure, restrict your attention to the bottom qubit:
This qubit contains a pentagon and a triangle. If this qubit existed on its own, then when measured, it'll randomly collapse to one or the other and log a 0 or a 1 in the classical register. But, the mega-qubit couples it with the top qubit. So, if the top qubit collapses to the triangle, the second combination in the mega-qubit is selected. And, the bottom qubit is forced to collapse to the triangle. In other words, the act of measuring one qubit forces the state of the other. This oddball behavior where the states of different qubits are tied to each other is called entanglement.
Because the states of different qubits are intimately in lockstep without any apparent physical linkage between them, this phenomena is also called spooky action at a distance. As weird as it may sound, entangled qubits are a central concept in quantum mechanics and is the root of frustration for many scientists. But, it's a real phenomena that has been confirmed experimentally. As you'll see in the next section, we'll use this strange behavior of qubits to design a contact tracing algorithm.
Using just two shapes - pentagons and triangles - and a few basic operations, we actually get to the core of quantum computing phenomena. In fact, these are not just superficial concepts that skirt around the central principles of quantum computing. In my book, I show how they are intimately tied with the standard mathematical treatment of quantum effects. These concepts are pivotal to build a strong intuition of quantum effects so that you can design algorithms for real world applications.
So, despite no one ever actually seeing a quantum state packing two states simultaneously, you write programs that imply multi-state qubits exist and can design algorithms to solve ultra-hard problems.
Contact Tracing and Quantum Entanglement
To arrest the spread of COVID-19, the wildly infectious disease that has forced the whole world into a lockdown, governments have resorted to a low-tech approach: locate and quarantine people that were in the vicinity of an infectious person.This approach is maddeningly tedious and fraught with errors. It relies on people who are infected to contact the authorities. The authorities in turn employ an army of people who interview the person and chalk up a list of people the infected may have been in contact with. Then, get in touch with those people to also isolate themselves. For this approach to be successful, it relies on the infected person having perfect recall and know the individuals they've brushed by - hard to expect in public settings like grocery stores, restaurants and bars.
To get around deploying vast armies of foot soldiers interviewing infected people, several organizations are tinkering with technology based solutions. These techniques use features of smart phones to track and share cryptic codes via bluetooth and geolocation technology. These operate in the background, with the user's permission and keep track of who meets whom and update a central registry with just the cryptic codes or IDs. If someone is infected, they update the central registry.
Everyone checks in daily with the central registry to see if an ID that they have been in contact over the previous 14 days - the duration within which if you are going to get infected. If so, they would self-isolate. In some implementations, the central registry can match the IDs and send notifications to those that may have been infected.
Although these methods eliminate the tedium and error-prone nature of manual contact tracing, many people are uncomfortable with sharing IDs with a central agency even though it contains no direct personal information. In some countries, government agencies match IDs with credit card transactions and facial recognition making this method even more intrusive.
Quantum Computing's Killer Feature
The ability to control the state of a physically separate computing unit of information without any direct intervention using quantum entanglement offers a compelling mechanism to design a contact tracing protocol. With these quantum based methods, a central agency is at best a facilitator of but has no way of actually knowing who is infected and who they have been in contact with.
To conceptually understand a protocol of contact tracing based on quantum entanglement, assume a futuristic world where smart phones are quantum devices. Once you get the basic picture of how quantum effects are used, I'll outline a way to implement this method with today's smartphones and quantum computers.
When two people get close to each other, each person's device creates a bunch of entangled pairs of quantum bits as follows:
- Each device keeps one and shares the other from each pair with the other device;
- If a person is infected, they'll collapse their quantum bits. Instantaneously, the state of other qubit in the pair, now with another person, is fixed even if the quantum bit hasn't collapsed;
Each day, everyone does the following:
- Discards any quantum older than 14 days, the incubation period for COVID-19 since the contacts associated with those quantum bits are no longer a threat;
- Collapse 1/14-th of the entangled quantum bits from each contact within the past 14 days.
The pivotal step in this method is the last one where everyday everyone collapses a fraction of the quantum bits that are still valid on each day. By looking at the states of the collapsed quantum bits, each person would know whether they have been in contact with an infected individual:
- If all the quantum bits associated with any individual show the same state, then the states of these quantum bits must were determined when its entangled twin was collapsed earlier by the infected person;
- On the other hand, if the quantum bits associated with any individual collapses to either of the two states, then their entangled twins haven't been previously collapsed and that individual is symptom free so far.
By every person scanning a fraction of the quantum bits associated with every individual that a person came in contact with in the past 14 days, everyone knows whether they should quarantine themselves. No one needs to share their locations with any one or any organization, nor any other kind of personal information. The entangled nature of the quantum bits takes care of signaling if a person was near an infected person.
But, handheld or portable quantum devices don't yet exist. Today's quantum computers are gigantic behemoths that are housed in carefully designed facilities that protect the quantum hardware from random disturbances and cool them to a few degrees above absolute zero. So, in the next section, I describe a way to use today's quantum machines with the smartphones we carry in our pockets.
Contact Tracing with Today's Quantum Computers
Although the smartphones we carry around with us don't deal with quantum bits, they can interact with cloud-based programs that run on quantum computers. Thus when two people get close to each other, instead of the devices exchanging quantum bits, they would do the following:
- One of the devices would first generate an GUID (Globally Unique Identifier) and share it with the other;
- Then, both devices would contact a cloud-based quantum computer passing the shared ID to it.
Upon receiving a GUID, the cloud-based quantum computer, in turn, does the following:
- Spin up a bunch of entangled qubit pairs;
- Initiate two quantum programs - one for each device - and seed each one with an entangled qubit from every pair.
In today's cloud-based quantum computers, quantum bits are not shared across programs. This feature, though, is not dictated by quantum principles. Rather, it's the way that the quantum computer vendor isolates one program from another. This restriction can be lifted without compromising any security consideration.
Thus, instead of each device managing the qubits themselves, the quantum bits are stored on the cloud-based quantum computer. Each day, every device goes through the same steps described in the previous section but instructs the quantum programs associated with it to collapse a fraction of the quantum bits according to the protocol outlined earlier.
Although the entangled qubits are managed on a central cloud-based computer, there is no information linking one GUID with another as with the current classical protocols stated in the beginning of this article. Each device just keeps a list of GUIDs of its own quantum programs. No one or no organization, including the vendor of the cloud-based quantum computer has any record that ties one program with that of another user. The linking is safely hidden from everyone by the nature of quantum entanglement.
What's Next
While most people think of applying quantum computers to highly complex problems, contact tracing with quantum computers turns out be one of the simplest applications of quantum principles yet offers a tremendously robust way of guaranteeing privacy and helping curb the spread of COVID-19 or other infectious diseases.
So although Quantum computing is still in its infancy, it offers tantalizing features such as quantum entanglement that may make it a hands down shoo-in to implement contact tracing in a safe yet private manner.
Acknowledgements
I would like to thank my editor, Brian MacDonald, at Pragmatic Bookshelf for his guidance helping make the book exceed what I ever imagined it could be. I would also like to express my deep gratitude to my publisher at the Pragmatic Bookshelf for taking on this project.