- SAP Managed Tags:
Neologism and Counter-intuition.
What makes a quantum-computer quantum? If the fundamental unit of the classical Turing machine is the bit, its quantum equivalent is the qubit, a portmanteau of quantum-bit (which itself is a portmanteau of binary-digit). Where a bit can be realized as a two-state concept (on/off, true/false, zero/one), Just like a classical bit if you measure a qubit, you will find it as either a one or as a zero. The difference is that these states are governed by chance with certain rules governing the probabilities which we will discuss in this blog entry. Two properties that occur at the scale of quantum mechanics are entanglement and superposition. We will deal with entanglement in a separate blog article. For now, it is enough to concern ourselves solely with superposition. Quantum computers also obey two fundamental laws; No cloning and no deleting. No cloning means you cannot take a quantum state and make and exact copy leaving the original state undisturbed. And no deleting means that you must always be able to recover the input to a qubit from the output. We say a quantum computer is perfectly reversible.
Superposition
“[I]n mathematics you don't understand things. You just get used to them.”
– John Von Neumann (1979)
Firstly, lets define the possible states of a qubit that correspond to our classical bit: zero and one. In a bit we call these states orthogonal. This means if the bit is in zero-state it cannot be in one-state and vice-versa. We can represent this as an abstraction in many ways. In fact, we represent this as two perpendicular directions that are mutually exclusive, like two streets at the corner of a building that we cannot enter. We can only travel down one street, or down the other street, but never on both.
Two orthogonal directions
Figure 1, Two perpendicular directions. If a vector can only lie on one of these two directions it must have no value in the other. This is because they are orthogonal. The zero-vector is illustrated in orange.
Why perpendicular? Well, if we travel in one direction, we make no movement in the other. So, if our vector points up, our bit is in the one state, and if it points to the right, it’s in the zero state. We could call them “on” or “off”, or “up” and “right”. But by convention we’ll call them 0 and 1. To signify that they are directions we could write them as 0̅ and 1̅ which might be familiar to those who’ve studied vectors before. However, by conventions[1] of modern physics we use |0⟩ and |1⟩.
Qubits
Qubits can point in a direction that has components of both |0⟩ and |1⟩. Mathematically, we write this as some arbitrary state, |ψ⟩ = α|0⟩ + β|1⟩. We can say that we superimpose[2] one state on the other. Here the Greek letters α (alpha) and β (beta) are coefficients of |0⟩ and |1⟩. Figure 2 below, extends the abstraction that we started talking about in Figure 1. Now, we also have negative directions (which we will need for destructive interference) and we can point our vector in any direction in the 2-D plane.
A 2-D unit circle
Figure 2. A 2-D unit circle showing an arbitrary state and its component vectors. This time there is no prohibition on traveling on the two orthogonal vectors at the same time.
Great so now we have a special bit that can have values like ½ and ¼ or anything in-between 0 and 1? Not quite, because there are two caveats.
The first is although you can measure at any angle; you can only the only possible outcomes will be orthogonal to each other (0 or 1, but not both). This is both a fundamental law of quantum mechanics (we say the state “collapses” to either 0 or 1), and with the fact that once you use a classical computer to store your measurement it can only record a bit value of 0 or 1. Here we will choose to measure in the |0⟩ and |1⟩ directions.
And the second…
It will always be in either the |0⟩ or |1⟩ directions when measured with a certain probability. The probability it will be found in the zero-state |0⟩, equal to the square of its coefficient (α²). Similarly, the odds it will be found in the one-state, |1⟩, will be the square of its coefficient (β²).
In words we might write, the probability, P, of finding the state |ψ⟩ in the zero-state when measured is alpha-squared, mathematically stated; P(|ψ ⟩ → |0⟩) = α². Similarly, P(|ψ ⟩ → |1⟩) = β².
N.B. for reasons of being able to distinguish between the actual vector space notation and its dual (bra-ket notation), physicists write the previous equation as follows:|⟨0|ψ⟩|² = α² and |⟨1|ψ⟩|² = β².
This leads us to what might seem like an obvious result, but the chances of finding the qubit in any state are guaranteed, α² + β² = 1.
How to write down qubit states?
As hard as it is to think of quantum states between |0⟩ and |1⟩ we must also manipulate them in our minds and communicate these manipulations to others. Is it okay to use angles to do this? Perhaps, but for multiple qubits we have a better solution, vectors. We read these vectors as “zero-ket” and “one-ket” respectively or “psi-ket” in figure 2.
A |+⟩-state in the unit circle
Figure 3, A 2-D unit circle showing a |+⟩-state and its component vectors.
All the vectors are fixed to a length of 1, probabilities cannot be greater than 1 (or 100% certainty if you prefer). Superposition involves the addition of vectors. In figure 4 we’ve redrawn out two The basis vectors are added together, the resultant vector must be normalised, so we multiply both |0⟩+|1⟩ by 1/√2. This vector is so common we give it a special label |+⟩ and we call it the “plus-state”. Another commonly used state is |-⟩ or “minus-state”. This is achieved by reversing the direction of the one-state, |-⟩=1/√2) |0⟩-|1⟩. These new states are so important its worth restating them.
The house always wins
Let us take a closer look at what these equations mean in the real world as it’s worth getting an intuitive sense for qubits if we want to dive in further. Remember here we only look or measure in the |0⟩ or |1⟩ state. Remember the coefficients α and β? In the case of the |+⟩-state these are both equal to 1/√2. Squaring these as this is how we obtain the probabilities gives us a fifty-fifty chance of finding our qubit in either state.
In traditional mathematical lexicography for those who are interested.
|⟨0|+⟩|² = α² = (1/√2)² = 1/2 := 50 %
Read this as, “the probably of measuring a qubit in|0⟩-state from a given |+⟩-state is 50%.”
Likewise,
|⟨1|+⟩|² = β² = (1/√2)² = 1/2 := 50 %
Time to make a heap of all our winnings.
As we venture deeper into quantum computing, we transition from the realm of classical bits to the world of qubits. Unlike classical bits, qubits possess the remarkable ability of superposition, allowing them probabilistically to incorporate a mixture of states. This challenges our classical intuition. However, it also holds the key to unlocking the immense computational power of quantum systems.
It’s hard to see why superposition could be useful. In 1985 David Deutsch came up somewhat contrived problem that he showed a quantum computer could solve in fewer steps than a classical computer. We will take a deeper look at this problem now and despite its unavailing nature it’s important not to understate its impact. Prior to this quantum computers had been hypothesized to be better at certain algorithms than classical computers. This was the first time anyone had come up with an algorithm that could show it.
The Deutsch problem
Suppose you have a black box (or oracle) that performs a function on a single bit binary input, and it gives you a single bit binary output. i.e., f:{0,1} →{0,1}. There are four possible functions that the black box can perform:
- Identity (Nothing): Zero in; Zero out. One in; One out.
- Negation: Zero in; One out. One in; Zero out
- Constant Zero: Zero in; Zero out. One in; Zero out.
- Constant One: Zero in; One out. One in; One out
Identity and Negation are called balanced functions, i.e., they out put zero and one with equal probability. Constant zero and constant one is called constant functions for obvious reasons. The figure below illustrates the concept. Here there is only one input and one output in each box.
Constant and Balanced Functions
Remember we have no idea what function the box performs. We wish to investigate is whether the function is constant or balanced. We can investigate this classically by trial and error: Input one? Output one, we’ve narrowed the function to either a constant one (constant) or identity (balanced), to differentiate between the two, we must try again but with a zero as our input. Then if we get a zero, we know it’s identity and therefore balance and if it’s a one again it’s a constant function with certainty. The number of steps we need is two. How could we attempt to do this faster with a quantum computer? Firstly, we need our oracle to be a quantum oracle. To do this we need to consider that the oracle must be reversible (no cloning and no deleting). The constant functions in figure 4 are not reversible, therefore we need a method to preserve the inputs. Such an oracle needs two inputs: x and y. And two outputs: x and the bitwise addition (modulo 2) of y and f(x). Also known as y XOR f(x).
A reversible quantum oracle
Figure 5 An oracle that preserves the input information in all cases. i.e., it is time reversible.
Classically we can construct a Boolean truth table for each of the possible oracles. For now, we need only concern ourselves with the case when y = 0.
Firstly, here the balanced functions.
X | y | x’ = x | y Ꚛ x |
0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
Table 1, Truth table for identity, f(x)=x
x | y | x’ = x | y Ꚛ ¬x |
0 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
Table 2, Truth table for negation, f(x)=¬x
Secondly, the constant functions.
x | y | x’ = x | y Ꚛ 1 |
0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
Table 3, Truth table for constant one, f(x) = 1
x | y | x’ = x | y Ꚛ 0 |
0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
Table 4, Truth table for constant one, f(x) = 0
Each input can be reconstructed from the output. I suggest you try do this on your own and satisfy your mind of this. You’ll notice that we still need two attempts to know whether f(x) is balanced or constant.
Superposition to the rescue
Now were ready to use what we’ve learned. We’ve seen what happens when we enter the values 1 and 0. What happens if we enter a superposition? Remember the |+⟩ = |0⟩ + |1⟩, and |-⟩ = |0⟩ - |1⟩ states? If we enter both |x⟩ and |y⟩ in superposition we get the following truth tables.
x | y | x’ = x | y Ꚛ x |
|+⟩ | |-⟩ | |-⟩ | |-⟩ |
Table 5, Truth table for identity, f(x)=x, on a superposition state
x | Y | x’ = x | y Ꚛ ¬x |
|+⟩ | |-⟩ | -|-⟩ | |-⟩ |
Table 6, Truth table for negation, f(x)=¬x, on a superposition state
x | Y | x’ = x | y Ꚛ 1 |
|+⟩ | |-⟩ | -|+⟩ | |-⟩ |
Table 7, Truth table for constant-one, f(x)=1, on a superposition state
x | y | x’ = x | y Ꚛ 0 |
|+⟩ | |-⟩ | |+⟩ | |-⟩ |
Table 8, Truth table for constant-zero, f(x)=0, on a superposition state
We can see now that we can in some way differentiate between balanced oracles superimposed outputs, y Ꚛ f(x) = |+⟩, and constant oracles superimposed outputs , y Ꚛ f(x) = |-⟩. For now, it’s enough to know that this demonstrates the concept of how superposition can distinguish between balanced and constant states with one query. Remember if we were to measure the output states, we will get 0 or 1 with equal probability of ½ for both the |+⟩-state (and |-⟩-state) making them indistinguishable without some further operations. We will further explore the Deutsch algorithm when we look at gates and how to set quantum states into a superposition. We will also see how we can extract information from a superposition state.
In this blog we've explored the fundamental concepts of qubits and the elusive nature of superposition. As we continue this journey in subsequent blog entries, we will delve further into the principles of gate operations and quantum circuits, laying the groundwork for understanding the transformative potential of quantum computing in the form of algorithms that have the potential to revolutionize computation as we know it.
Acknowledgements: Peter Wieland and Michael Schroedl-Baumann for their work initially presented during SAP's quantum eXplorers' bootQamp 2023
[1] The |x⟩ notation has a special significance; it’s called Dirac notation after Paul Dirac. You might infer from the arrow-like nature, that ⟨0| points the opposite direction to |0⟩, it doesn’t, that would be |-0⟩ or -|0⟩. We’ll dive deeper into the meaning in later blog posts.
[2] It’s worth digressing here for a small history lesson. The concept of superposition comes from wave mechanics.[3] You might have seen it before, staring at the dynamic patterns made in a water pond when two sets of ripples collide, you’d have noticed that crests superimpose on top of one another to form larger waves troughs become deeper troughs and a trough and a wave can cancel each other out. We can build our intuition on this observation. The notes of a guitar are waves like those on the surface of a pond albeit a one-dimensional string rather than a two-dimensional surface. As they are constrained at both ends then form “standing waves” of a particular frequency. We can come up with a new state by summing together existing states.
[3] In fact, wave mechanics took it from geology, but that’s not what’s important.
