- SAP Managed Tags
Building on from the foundations
In our last article, we briefly mentioned superposition and entanglement as quantum phenomena that cannot be replicated on classical processors. (They can be simulated but not replicated and neither at scale.) We briefly touched on the Deutsch algorithm as the first algorithm that demonstrated a task that a quantum computer could do faster than a classical computer, albeit a contrived task. It’s worth dwelling more on the Deutsch algorithm and its successor the Deutsch-Jozsa algorithm to further understand qubits and to venture further into the concept quantum gates.
Cows and Gates.
Classical logic gates are a work horse of electronics and classical computer science. A logic gate is a device that performs a Boolean Function. These are just a set of rules that simplify logical expressions. We use logic when we make statements like; cows have an even number of toes AND are ruminants (chew the cud), cows are a uniform colour OR are white with patches of a single colour, cows do NOT have patches of two colours. The AND, OR, and NOT combine to reveal truths. If a cow cannot have black AND brown patches, then the animal you are trying to milk is therefore NOT a cow!
For binary inputs, like in electronics and computer science, where 1 is true and 0 is false, we use logic gates as an abstraction. If you are inexperienced with logic gates, then it’s worth familiarising yourself with them before reading on.
Below is a logic symbol for an XOR or exclusive OR gate.
Figure 1, A logic symbol for a classical XOR or exclusive OR gate, with inputs A and B on the left and output on the right.
Input (A) | Input (B) | Output (AꚚB) |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Table 1, The truth table for the classical XOR gate shown in figure 1.
Quantum gates gave similar properties but are subject to the constraints (and opportunities) of quantum mechanics. One of the constraints is that all operations must be reversible. That means that given an output Q, we must be able to construct the original inputs. With the XOR-gate above it is impossible since there are two possible outputs and four possible inputs. The only classical gate where reversibility is possible is the NOT gate.
NOT (Again)
The classical NOT gate, or negation function, has only one input and one output. We can easily construct the input if we have the output, so it is completely reversible. Therefore, we do not need to construct a different one for a quantum operation. All we need to do is change the symbol we use. Below, in Figure 2, is the symbol for the quantum NOT-gate or X-gate.
Figure 2, A (quantum) NOT gate also known as an X-gate. Input A is inverted, and output is ¬A
A truth table for a NOT gate should be easy for you to construct for inputs of 0 and 1. But what about a superposition of 0 and 1? Firstly, since superposition is a quantum phenomenon, we would need a gate to convert our input state into a superposition,
Neatly, we have a gate for this, we call it the Hadamard gate, named after French mathematician Jacques Hadamard, who gave his name to the matrix which performs this operation. (We will delve into linear algebra and matrices in later blog articles, for now it is enough to understand the concepts.) Figure 3 below illustrates the Hadamard gate.
Figure 3, A (quantum) Hadamard gate.
Below we have constructed the truth table for a Hadamard gate for some common inputs. Remember, the |+⟩-state and | ̶ ⟩-state are an equal superposition of |0⟩ and |1⟩.
Input |A⟩ | Output |Q⟩ |
|0⟩ | |+⟩ |
|1⟩ | | ̶ ⟩ |
|+⟩ | |0⟩ |
| ̶ ⟩ | |1⟩ |
Table 2, A truth table for the Hadamard gate with some common inputs (and outputs).
NOT NOT (again) again
Like the X-gate, a Hadamard gate’s inputs can be reconstructed from its outputs. In fact, applying a Hadamard gate twice will return the output state to its original state. This is because a Hadamard gate is its own inverse (as is the X-gate, or “an X-gate is not not its own inverse”). There are other possible inputs and outputs to a Hadamard gate but for now it’s simpler to deal with equal superposition.
So, by first applying a Hadamard gate we can create a superposition, we can then apply an X-gate to construct the truth table for an X-gate.
Input |A⟩ | Output |¬A⟩ |
|0⟩ | |1⟩ |
|1⟩ | |0⟩ |
|+⟩ | |+⟩ |
| ̶ ⟩ | ̶ | ̶ ⟩ |
Table 3, A truth table for quantum NOT-gate or X-gate with some common inputs (and outputs)
Quantum Gates
Remember we said that any quantum gate must be reversible? This is not possible for the classical XOR gate in Figure/Table 1. If we have the output 1 we can’t tell if the input was (1,0), or (0,1). If we know one of the inputs, we can use this together with the output to reveal the remaining input, but we would need to preserve this. To construct an XOR quantum gate we need two output wires. One for the output, and one to preserve one of the inputs. This is sometimes referred to as an ancilla.
Controlled-NOT gate (CNOT)
Such a gate would input the quantum state |A⟩ and |B⟩, then output both |A⟩ and |A Ꚛ B⟩, see the diagram in Figure 4. We call such a gate, a Controlled-Not gate: as the output is |¬B⟩ if, |A⟩ = |1⟩.
Figure 4, A quantum Conditional-Not gate or CNOT-gate. Notice the input A is preserved to allow for a fully reversible operation.
The logical truth table for the CNOT gate can be easily constructed from what we know already. One can see that output (|A Ꚛ B⟩) is only negated if the input |A⟩ equals |1⟩.
Input |A⟩ | Input |B⟩ | Output |A’⟩ | Output |A Ꚛ B⟩ |
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 |
Table 4, The logical truth table for a CNOT-gate
The above table is equivalent to a classical XOR gate with an ancilla bit preserving input |A⟩. Of interest to us is the input for equal quantum superposition (also known as the Hadamard basis). Below is the table for equal superposition. We will go through the mathematics of how we arrived at this quantum truth table in the next blog article. Notice that this time the second output qubit is the one unchanged and the first qubit only changes if the two inputs differ. This is known as ‘phase kickback’.
Input |A⟩ | Input |B⟩ | Output |A’⟩ | Output |AꚚB⟩ |
|+⟩ | |+⟩ | |+⟩ | |+⟩ |
|+⟩ | | ̶ ⟩ | | ̶ ⟩ | | ̶ ⟩ |
| ̶ ⟩ | |+⟩ | | ̶ ⟩ | |+⟩ |
| ̶ ⟩ | | ̶ ⟩ | |+⟩ | | ̶ ⟩ |
Table 5, The quantum truth table for a CNOT-gate with both input states in equal superposition.
Deutsch’s Problem
Let’s use what we know and revisit the Deutsch problem from our last blog article. Remember our problem consisted of determining whether a function, f, was constant or balance. Constant means the function’s output is always either 0 or 1 regardless of the input; balanced means the function’s output is 0 or 1 in equal number. (For the simple case the only two balanced functions are negation or identity).
In summary the classical Approach:
- Requires two evaluations of f(x): once for f(0) and once for f(1).
- Constant function: f(0) = f(1)
- Balanced function: f(0) ≠ f(1)
A quantum approach
We can use the Hadamard gate to input a superposition state to our functions. We said in our last article that a device that performs a function like this is called an ‘oracle’. (This is a nod to the oracle at Delphi, whose patrons would ask a question and get an [often cryptic] answer.)
Figure 5, A black-box schematic of Deutsch’s Oracle. Note the difference in the output of the second qubit |y Ꚛ f(x)⟩, versus from figure 4; |A Ꚛ B⟩.
We can work our way through another quantum truth table now. We can convert out inputs using two Hadamard gates as shown in Figure 6.
Figure 6, A Schematic of the Oracle with its input in a superposition. Creating a superposition of states as an input to our oracle allows us to probe many states.
The trouble is, this will still give an output of states in superposition, and measuring a state in superposition in the computational basis will yield either a |0⟩ or |1⟩ with equal probability. This is true for both superpositions |+⟩ and | ̶ ⟩. In order to detect which superposition the output is in, we need to apply another Hadamard gate to flip | ̶ ⟩ to |1⟩, and |+⟩ to |0⟩. For the purposes of the Deutsch algorithm, we want to input a | ̶ ⟩ to the second input. Since the convention is to start our qubits in the |0⟩-state we need an X-gate to flip the second qubit to a |1⟩-state.
Figure 7, The schematic for the Deutsch Quantum algorithm. Adding a Hadamard gate to the superposition output of the oracle allows us to decipher that superposition. The intermediate states are unavailable to the observer; however, we have included them in table 6 below.
Remember the input x = |0⟩ and y = |0⟩ (which is then flipped by the X-gate). So, let’s enter our initial state of |00⟩ and take a measurement. The table below (Table 6) illustrates the four possible outcomes. It also shows the intermediate steps, but this is for explanation and cannot be accessed by an observer. We can see that for both balanced functions |x’⟩ = |1⟩ which when measured, yields one with 100% probability. And for both constant functions |x’⟩ = |0⟩, similarly, when measured, yields zero with 100% probability.
Input |x⟩ | Input |y⟩ | H|x⟩ | H|y⟩ | Function | Output |x’⟩ | Output |yꚚf(x)⟩ | H|x’⟩ | |y’⟩ = |yꚚf(x)⟩ |
|0⟩ | |1⟩ | |+⟩ | | ̶ ⟩ | Identity | | ̶ ⟩ | | ̶ ⟩ | |1⟩ | | ̶ ⟩ |
|0⟩ | |1⟩ | |+⟩ | | ̶ ⟩ | Negation | | ̶ ⟩ | ̶ | ̶ ⟩ | |1⟩ | ̶ | ̶ ⟩ |
|0⟩ | |1⟩ | |+⟩ | | ̶ ⟩ | Constant 0 | | ̶ ⟩ | |+⟩ | |0⟩ | | ̶ ⟩ |
|0⟩ | |1⟩ | |+⟩ | | ̶ ⟩ | Constant 1 | | ̶ ⟩ | |+⟩ | |0⟩ | | ̶ ⟩ |
Table 6, A quantum truth table for figure 7. One input/output for the circuit described by Figure 7 where the oracle, the shaded intermediate superposition states are hidden from the user. The answer were are looking for is in the column labelled H|x’⟩.
This is what we set out to achieve. This left me with a lot of questions when I first learned about it. Namely why did Deutsch think of a problem with no practical value? I mean, after all; the world is literally full of problems, why construct another one that affects absolutely nobody? I can’t answer these questions (perhaps David Deutsch can), but I can say that this was the first quantum algorithm that could be proven to solve a problem faster than a classical computer could solve it. From this, David Deutsch and Richard Jozsa extrapolated to the case where the unknown function has n bits as it’s input and returns one bit as its output. f{0,1}ⁿ → {0,1}. The task is the same to determine whether the output is constant, or balanced meaning the same number of inputs give the output one as zero. We restrict the problem to these two cases as the algorithm cannot give us information if the outputs could be one or zero but an equal number of times. Below we illustrate some possible cases for n = 2.
Example of multiple input Deutsch-Jozsa Oracle that is constant or balanced, and an example of an unbalanced output which, by definition of the problem, is not allowed.
| Constant zero |
| Balance |
| Unbalanced |
f(0,0) | = 0 | f(0,0) | = 0 | f(0,0) | = 0 |
f(0,1) | = 0 | f(0,1) | = 1 | f(0,1) | = 0 |
f(1,0) | = 0 | f(1,0) | = 0 | f(1,0) | = 0 |
f(1,1) | = 0 | f(1,1) | = 1 | f(1,1) | = 1 |
Table 7, An example of a constant, balanced, and unbalanced output. There are other possibilities, for example constant 1, NAND etc,
We will only concern ourselves with the question of whether the function is constant or balanced.
There are 2n possible input values. Classically, in the worst case, especially if f is constant, we must call f for just over half of the possible inputs, i.e., 2ⁿ⁻¹ +1 times. If f is balanced and we are lucky, we need only two queries in the best case. We say that the problem scales exponentially with the input.
Can we do better with a quantum computer?
If we set our inputs to the oracle in a superposition, we can perform a similar trick as above. Figure 8 shows and expanded view of a diagram of gates needed. We can see the set-up is similar to that needed for the simple Deutsch algorithm described above in Figure 7.
Figure 8. A schematic of the expanded Deutcsh-Jozsa algorithm. It shows the quantum gates needed to input and detect whether a function f{0,1}ⁿ → f{0,1} is constant or balanced.
Similar to the Deutsch algorithm, when we measure any qubit from |x₁⟩ to |xₙ₋₁⟩, if the function is constant, we will measure 0 and if the function is balanced, we will measure 1. For either case we only need to perform the measurement once! This is fantastic result. The speed up is independent of the size of the problem and it is always solved in just one step. We call this reduction from exponential to constant, an exponential speed-up.
But what about the mathematics?
No explanation of quantum computers is complete without a mathematical explanation. And what I have described above is to give a flavour, based primarily on truth tables and a quantum treatment of truth tables. I chose this approach to hopefully give a familiar feeling to an unfamiliar topic. In the next entry, we will deal with the mathematical description of quantum computing, but I promise the mathematics is very simple. It consists of nothing more difficult than complex numbers (√(-1)=i) and their linear algebra (matrices). These are mathematical concepts which I am convinced any highschooler is capable of understanding. Many people are suddenly anxious when they see a page of equations, and I understand this. My advice is to remember that mathematical expression is a language, just like the one you are reading now.
N.B. some readers have commented on the confusion between the states |0⟩ and |1⟩ and the numerical values zero and one. Both states are identifiers, they could just as easily be written as |↑⟩ or |’up’⟩, and |↓⟩ or |’down’⟩. The |0⟩-state it is decided (when measured) gives value zero 100% of the time, likewise the |1⟩-is chosen to be the value one.
| User | Count |
|---|---|
| 13 | |
| 11 | |
| 7 | |
| 7 | |
| 6 | |
| 6 | |
| 6 | |
| 6 | |
| 6 | |
| 5 |
