The Quantum State

“Of the three main areas of quantum technologies, quantum computing continues to attract the most investment, with $3 billion raised by the end of 2021, which makes sense given it also represents the largest potential market, estimated to be upward of $90 billion annually by 2040.”

McKinsey & Company, Quantum Technology Monitor, June 2022

I know these McKinsey guys are some of the smartest in the room, but let’s just back up a bit shall we? 

In order for these projections to be even remotely possible two things have to happen: we have to build a quantum computer that works properly, and we have to find something useful for it to do. 

So, to the first point, how do we build a quantum computer?

A digital computer has a kind of conceptual, logical design based on a circuit of  ‘bits’ and ‘gates’. A bit is something that symbolically represents a binary value - 0 or 1. A gate is something that acts on bits in a specific way to produce other bits. For example, an ‘OR’ gate outputs a value of 1 if either of its inputs is 1; otherwise it outputs 0. An ‘AND’ gate outputs a 0 unless both of its inputs are 1. And so on. 

As long as we have a way of storing bits, this basic conceptual model is completely general - it allows anything computable to be computed. It’s truly remarkable that all of the computer applications we see around us today are fundamentally built on this very simple ‘digital logic’.

A quantum computer has a similar, or at least analogous, logical design, based on ‘qubits’ and (quantum)  ‘gates’. 

A qubit is a quantum version of a bit. When it’s measured it also symbolically represents a binary value - 0 or 1, but it has a kind of underlying structure that means that if we leave it alone for a while it can also exist in a ‘superposition’. Digital bits can’t do this. A superposition is what happens when, for example, you add pure musical notes of different frequencies together to create ‘beats’. It’s also what happens when you combine a latitude and a longitude to represent any direction on a map, instead of just ‘north’ or ‘east’. Digital bits 0 and 1 just represent numbers but the qubits 0 and 1 are more like due north and due east. In this sense at least, superposition is not really mysterious. More to the point, despite what you might have read somewhere, this doesn’t really mean that the qubit is  “0 (dead) and 1 (alive) at the same time”, except in the sense that Newcastle is north and east at the same time.

Multiple qubits can also be put in a combined state. Actually, so can digital bits, but the difference is that the bits can always be separately identified. With qubits this isn’t always the case - they can be combined into an ‘entangled’ state in which the states of the individual qubits can’t be ‘factored out'. This is curious, and potentially an extremely distracting rabbit hole, so let’s sidestep it for now. 

A quantum gate is analogous to a classical, digital gate. It can do similar logic functions, and it can also create these superpositions.

That’ll do for our purposes, but for the curious I’ve included some more commentary on how qubits work and the sorts of things that can be done with them in the afterword, ‘Qubits in Pieces’.

So the logical design of digital and quantum circuits is fairly similar, but to build a working machine they have to be physically implemented, and at this level they couldn’t be more different.

Nowadays we’ve lost all sense of how hard it was to get the earliest computers to work properly. Cogs would slip, valves would constantly blow, that sort of thing. But for well over half a century now we’ve had transistors - microscopic digital switches that can be used to create representations of bits by manipulating clearly distinguishable high and low voltages, and which can easily be combined so as to make gates. This system is so robust and reliable that almost no one is seriously trying to use a fundamentally different architecture, and ‘error correction’ is no longer a thing that computer engineers have to worry about.

There is as yet no single, preferred method for implementing qubits and their attendant gates, and all of the current architectures have drawbacks. Qubits tend to decay quickly; gates aren’t sufficiently accurate (they have inadequate ‘fidelity’); there aren’t enough qubits to do something useful with. And although there has been a brilliant, theoretical, error-correction solution for quantum circuits for over a quarter of a century, no one has managed to make it work in practice yet. 

These are all mammoth engineering problems. It’s possible that one or more of them will never be solved. In fairness though there have been huge advances in each of these areas in recent years, and for the purposes of the rest of this article we’ll assume that, one day, we will have a functioning, fault-tolerant quantum computer with sufficient ‘volume’ that we can do something useful with it. Maybe even within my lifetime.

What then?

"Imagination is the only weapon in the war with reality."

Lewis Carroll

Alice's Adventures In Wonderland.

Perhaps the ‘least insanely hard’ thing that could be done with such a beast isn’t so much ‘computation’ as ‘simulation’. In fact it might even be possible to do this without completely cracking all the engineering problems above. The idea here is that the quantum computer is a physical system, and its behaviour evolves according to a set of differential equations which essentially represent the same mathematical model as that representing other physical systems, such as molecules. So in principle it could simulate their behaviour, and that may in turn lead to important discoveries.

An imperfect analogy might be the RLC (‘resistor-inductor-capacitor’) circuit and the pendulum. If we build a simple electrical circuit using a resistor, a capacitor and an inductance coil, attached to an alternating current source, then the electrical charge on the capacitor will fluctuate fairly wildly until it settles down into a rhythmic pattern of charging and discharging continuously. Similarly, if we take a pendulum and wiggle it at a consistent frequency, it will also gyrate wildly for a while before settling down to a rhythmic, continuous oscillation. And, rather pleasingly,  it turns out that the mathematical model that describes the changing electrical charge on the capacitor is exactly the same as that which describes the movement of the weight on the end of the pendulum, despite them being very different physical systems. So, in principle at least, by tweaking a few parameters we could use one of these systems to simulate the other.

Well okay, but what about actual computation?

Nowadays if you’re writing a computer program, let’s say in Python (a programming language), you don’t actually do a hell of a lot of coding yourself. What you do is to ‘import’ into your program a library of functions which you can tweak to do what you need for your particular application. Those library functions might prepare graphs for you, manipulate matrices, search databases efficiently, and so on. Let’s call these ‘platform algorithms’. One of the biggest challenges in coding these days isn’t learning how to write code, it’s familiarising yourself with the relevant platform algorithms. There are countless thousands of these things, built up over decades.

In quantum computing there are two. They were both discovered over a quarter of a century ago. And no one has discovered any more since. Let that sink in for a minute.

You can nit-pick about whether that’s a fair representation. There have been lots of algorithms developed which are applications of these two, for example, and it's not quite a like-for-like comparison in the first place. But the reality is that if you’re trying to figure out a ‘use case’, a commercial application for your quantum computer, these two platform algorithms are really all you’ve got to play with. 

So let’s see what they can do.

“As part of its 14th five-year plan for quantum technology (2021–2025), China has announced the most public funding to date of any country, more than double the investments by EU governments ($15.3 billion compared to $7.2 billion) and eight times more than US government investments”

McKinsey & Company, Quantum Technology Monitor, June 2022

The first platform algorithm tackles the ‘hidden subgroup problem’. It’s not possible even to frame this intelligibly without a grounding in some fairly obscure mathematics[1], and it’s probably not worth making the effort because, with one glaring exception that we’ll come back to, the applications tend to be highly contrived. It’s possible that one day someone will figure out some arcane connection between an addressable hidden subgroup problem in number theory and an actual practical application in commercial life, but it’s very tough to envisage such a thing, no matter how hard you squint at it. 

The exception that proves the rule though is a humdinger. 

Shor’s algorithm applies the hidden subgroup problem to that of breaking down big numbers into their prime factors (that is to say, into prime numbers which multiply together to give the original number). For a classical computer this problem is ‘hard’, which is a computer science euphemism meaning ‘pretty much impossible within the lifetime of the current universe’. Shor’s algorithm however can achieve an ‘exponential’ improvement over a classical one, meaning that the problem becomes ‘tractable’. 

This may also look like an obscure problem in number theory with no practical application, and indeed it would be, except for one monumental piece of bad luck - almost all the world’s digital encryption technology is based on the assumed impossibility of factoring big numbers into primes. Given a properly functioning quantum computer, this is the algorithm that breaks the internet. And the Pentagon.

No doubt it’s this fact above all others that has driven governments (in particular) to throw their taxpayers’ hard-earned readies into the quantum computing bubble. It’s almost literally an arms race.

On the other hand, there are plenty of potential solutions - different means of encryption which would be secure even against Shor’s algorithm. The problem of ‘post quantum cryptography’ is one of selecting and implementing workable standards, not devising radically new technologies from scratch (although new technologies, such as secure ‘quantum key distribution’, are also being brought to bear). The problem is more immediate than you’d think though  - encrypted databases are currently being copied and warehoused with a view to cracking them some time in the future (‘Harvest Now, Decrypt Later’) -  but overall the potential future vulnerability looks like an addressable issue.

And in any case, alarming as this problem may sound, it still doesn’t really constitute a broadly useful commercial application of quantum computing. It is very much the exception that proves the rule.

So what about the second platform algorithm?

This is sometimes called the search algorithm, a bit misleadingly, but more commonly ‘Grover’s algorithm’, after its discoverer. And, on the face of it, it’s much more promising. 

Let’s say we have a big ‘dataset’ of possible supply chain configurations, with performance criteria like marginal cost, set up cost, lead times, carbon emissions, and so on. Let’s also say there’s a hundred million of these configurations, and we want to find those that match a certain criterion. Maybe those with lead times below a particular threshold. The database is indexed, so we can identify a particular configuration with a number, but otherwise has no ‘structure’ which might simplify the problem. In other words, we can do no better than walk through each one in turn and see if it fits our criterion. 

Using a classical computer, we might have to walk through all 100 million entries looking for matches. If each check takes a hundredth of a second, it could still take twelve days to complete the search.

An application of Grover’s algorithm running on a fault-tolerant quantum computer could potentially complete this task with something like 10 thousand checks rather than 100 million. If each check takes a roughly comparable time to the classical program, that’s under an hour and a half. 

And this is just one (made up, granted) example. In principle the model that Grover’s algorithm works on (an unstructured data set with some records ‘marked’) could conceivably apply to a vast range of commercial problems - airline routing, FMCG inventory management, program trading, fleet management, and so on. 

There are a few issues though. 

The first is that, whereas Shor’s algorithm promises exponential speedup compared to a classical computer, Grover’s performance improvement is ‘merely’ quadratic. If the problem size is ‘N’ (which is 100 million in the above example), the classical algorithm performs O(N), meaning that the time and computing resources required go up linearly with the size of the problem. Grover’s algorithm reduces this to the square root of N - of the order of ten thousand in our example. This sounds like a massive saving, but it’s not nearly as impressive as Shor’s exponential improvement.

And that might be important, because the second issue is that the competing classical solution is assumed to be ‘dumb’. The projected improvement is predicated on the dataset being ‘unstructured’, effectively random, but in practice it’s possible to bring all sorts of ingenuity to bear to optimise the (classical)  algorithm, including clever structuring or re-indexing of the data, parallel processing, and so on. It’s entirely possible that the putative performance gain might prove to be short-lived, or disappointing, or both. 

And the last issue is the actual implementation of the algorithm. The second afterword below, Finding a Needle in a Quantum Haystack, seeks to give a picture of how this works. The basic idea is this:

• Collect enough qubits to cover all the potential index values[2]. To address 100 million numbers requires 27 bits (or qubits) for example[3].
• Put all the qubits into a single state of equal superposition of all the possible index values. By ‘equal’ superposition, we mean that each basis state has the same amplitude, or ‘signal strength’. At this stage, none is louder than any other.
• Use this massively superposed state to run a single, quantum query on an ‘oracle’. The oracle is basically a quantum circuit which implements the dataset. 
• The result of the query is that any of the components of the superposition that meet our criterion - they represent ‘marked’ index values - are themselves marked. Unfortunately, we can’t directly access these marked states.
• The next bit of the circuit ‘amplifies’ the marked components - think of one or more of those pure musical frequencies being made louder than the others.
• If necessary, repeat this process until the marked components are really ‘loud’ - they have a much stronger amplitude than the others. 

At this point, we ‘measure’ the quantum state. It turns out that for something as small and delicate as a qubit, which might be a single photon, a pair of electrons or an atom for example, this is not a gentle process. However we measure it, we’ll crash the superposition and we’ll get out a string of 0s and 1s. It’s like trying to measure the direction of a weathervane by driving a truck into it, so that it only ever gets stuck on the front bumper pointing either left or right.

If we’d measured the original, equal superposition, we’d get a single, completely random number between 0 and 100 million, and any of the possible 100 million index numbers would be equally likely. However, Grover’s algorithm amplifies the amplitudes of the numbers we want. This makes it much more likely that we’ll end up with a string of 0s and 1s which represent, in binary, a ‘correct’ index number (although we’ll still only get one of them). It’s as if we’d amplified one of the pure frequencies in a musical chord to the point that it drowned out all the others. 

I appreciate that all of this is very confusing if you’re unfamiliar with the quantum world, and I’m sorry to have inflicted it on you, but the relevant point is that buried amongst all that flannel is a ‘here magic happens’ step. Which is the oracle itself. 

Grover’s algorithm only works by having an oracle to query. And that oracle has to be (a) a quantum circuit; or (b) at the very least a quantum-addressable dataset; and ( c) already ‘flagged’, so that all the algorithm does is check that flag - 0 or 1. In practice, for any kind of realistic and worthwhile problem,  this is pretty much science fiction as yet. It’s another insanely hard, optimism shredding problem.

"When I used to read fairy-tales, I fancied that kind of thing never happened, and now here I am in the middle of one!"

Lewis Carroll

Alice's Adventures In Wonderland

In summary then, assuming that it’s possible to solve the issues of qubit stability, gate fidelity, volume and error correction, and if we can somehow figure out how to configure oracles for real world applications, then Grover’s algorithm might work for some optimisation-type problems, and might result in a  significant speed up in performance, although innovation in  classical software engineering, particularly machine learning and concurrent processing, may narrow or close that gap in some cases.

And, given all of that, I have to give the McKinsey team full marks for chutzpah.

[1]  “Let f be a function from a finitely generated group G to a finite set X such that f is constant on the cosets of a subgroup K, and distinct on each coset. Given a quantum black box for performing the unitary transform U|g|h = |g|h⊕f(g), for g ∈ G, h ∈ X, and ⊕ an appropriately chosen binary operation on X, find a generating set for K.” (Neilsen & Chuang, 2010)

[2] Strictly speaking this means ‘logical qubits’. Quantum error correction requires a bunch of physical qubits to ‘model’ a single logical qubit, so the actual number of qubits required might be tens or hundreds of times larger than this.

[3] With 2 bits you can index four numbers: 00, 01, 10, 11. Add another bit and you have 8, and so on, like amoeba dividing. 27 bits gives you up to 134,217,728 values.

Afterword: Qubits in Pieces

This ability to distinguish clearly between two distinct states is what gives the transistor its computational power. Binary logic in a sense provides an abstract model of the physics of the system, but it also provides a model of computation, which is independent of the underlying technology. In this model, the values ‘0’ and’1’, which symbolise a low or high output voltage, are ‘scalars’. That is to say that they represent simple numbers, with no other structure.

Similarly, the mathematics of qubits can be used to model a wide variety of atomic and subatomic systems, the common feature of which is that they are, in a sense, discrete two-state systems. As with bits, the qubits also provide a model of computation which is largely independent of the physical systems used to realise them. The difference is that qubits cannot be represented as scalars - simple values. Qubits have structure. In practice this means that they are best represented as ‘vectors’.

If we ‘measure’ the state of a single qubit, what we get is one of the two basis vectors of that qubit with respect to that measurement. (What we mean by ‘measurement’ is a subject of some controversy within quantum physics, and is essentially an unresolved issue, but for all practical purposes it’s exactly what it sounds like.) It’s as if, whenever we try to find some place on a map, we always get ‘due north’ or ‘due east’. We’ll call these basis vectors 0 and 1. They’re in bold to remind us that they’re vectors, not scalars, and we’ll see what that means shortly. In particular, 0 symbolises a vector - it’s not the same as the value 0. If you multiply 0 by a number, you don’t end up with nothing in the same way as you do if you multiply with the scalar 0.

If 0 meant ‘1 km north’ and 1 meant ‘1km east’, then we could get anywhere on a map by adding together distances north (multiples of 0) and distances east (multiples of 1). To identify a point on the map we need both a distance and a direction. If we just needed distance, we could make do with a scalar, but because we need both distance and direction we need a vector. 

For a map, all of this is literally true. For a qubit it’s more of a figurative picture of the underlying mathematical structure. All the same, between measurements we can create quantum states which can be represented just like points on a map: by adding together multiples of the two basis vectors. 

There’s an additional constraint on qubit states which simplifies this picture a little: the ‘distance’ (which in quantum parlance is dubbed ‘amplitude’) can only be one unit. On a map, this would mean we can only ever be 1km from the origin. Somewhere on a unit circle, in other words. 

Take a look at the diagram below. The vector ψ (‘psi’) is one unit long. It can be reached by going 0.6 units in the 0 direction (‘north’) and 0.8 units in the 1 direction (‘east’). If you don’t want to use a picture to visualise it you could just say ψ = 0.6x0 + 0.8x1 instead. 

Now this illustration is just a single qubit. As with bits, you can’t do much with a single qubit, but in principle you can do more than with a bit. A bit can be left alone, flipped, or constant (e.g. output 0 irrespective of whether the input is 0 or 1). We can do all this with a qubit too, but we can also move it around the unit circle at will, as long as we do it in between measurements. 

Take the state ψ in the illustration above. A key point to note is that we can never access this state directly. Our measurement can only access 0 or 1. If we do measure ψ, then we will randomly end up with 0 or 1.

Well, that’s not strictly true. You’ll note that ψ is in a sense weighted more towards 1 than 0: 0.8 as against 0.6. The consequence of this is that we’re more likely to measure 1 than 0 (in fact we’re likely to get 1 64% of the time, and 0 36% of the time). So not completely random. If ψ had been at 45 degrees to 0 and 1 then the outcome would have been 50-50 (this is termed an ‘equal superposition’, and it’s a useful state in quantum computing).

This is the basis of quantum computation. By ‘rotating’ the qubit state vector towards a basis vector (or, equivalently, varying the weightings in favour of that basis vector), we can increase the probability of getting that particular outcome on a measurement. If we rotate the qubit all the way onto that basis vector, then we are certain to get it on a measurement. 

Amongst other things, this is essentially the idea behind Grover’s algorithm.

A note for pedants - Yes, I know,  I’ve ignored  complex coefficients, Dirac notation, unitary transformations and the Bloch sphere.

Another Afterword: Finding a Needle in a Quantum Haystack

A single qubit has two basis vectors, which we’ve called 0 and 1. Every time we add a qubit to the system the number of basis vectors doubles. So a two qubit system has four basis vectors, and we can call these 00, 01, 10 and 11. (You may have noticed that these symbols can represent the binary numbers for 0, 1, 2 and 3, which can come in handy, but they’re still vectors, not scalars). If we measure the state of a two qubit system, we get one of these basis vectors, which themselves just represent all the possible combinations of two qubits, each in one of two states. So if we measure 01 we get the first qubit in the 0 state and the second in the 1 state, for example.

For Grover’s algorithm to be practically useful, we’d need a lot of qubits, so that we have a lot of basis vectors that can represent index values, but let’s look at how it would work with just two qubits, which can only address four index values - the principles are exactly the same.

First of all we create an equal superposition of all the basis vectors. This means that we create a state in which all the basis vectors have equal weighting. In the single qubit illustration above, the resulting vector would be at 45 degrees to the two basis vectors: 0 plus 1; going north and then the same distance east. (In fact we have to adjust the weightings so that the amplitude of the vector is 1. If you can remember Pythagoras’ Theorem from school, you’ll know how to do this - the hypotenuse has to be 1 - but it’s not really important for our purposes, so we’ll ignore this point).

An equal superposition of the two qubit system can be written as 00 + 01 + 10 + 11 (and remembering that these are vectors, so the superposition is another vector: it’s not the same as 0 + 1 + 2 + 3 = 6). Again, I’m ignoring the fact that this vector doesn’t have unit length, and should really be scaled so that it does.

This superposition is then handed to an oracle which ‘marks’ the correct answer (for simplicity we’ll assume there’s only one correct answer in this example). It does this by ‘flipping’ the relevant basis vector: multiplying it by -1. 

Let’s suppose that the correct index value is 2, so that 10 is the marked basis vector. Once our superposition has been through the oracle, our new vector is 00 + 01 - 10 + 11. Note the new minus sign. 

On the face of it this looks like ‘job done’: we know that the answer is 2. The problem is that we can’t access this result. All that we can do is measure this new state, and if we do we end up with exactly equal probabilities of getting any of the basis vectors. A weighting of -1 points the vector in a different direction, but it’s still (figuratively) at 45 degrees to each of the basis vectors, so it’s still an equal superposition and we only have a 25% chance of getting the right answer.

We can’t really visualise our new vector in the same way we did with a single qubit, but we can do something similar. We can notionally take the correct answer and designate that as one basis vector on a new map. We wouldn’t know what it is yet, so we’d have to call it ‘x’ or something. Then we can designate a superposition of all the other basis vectors, which is after all just a vector itself, as a second, new, notional basis vector on the new map, say ‘not x’. In our illustration x would turn out to be 10 and not x would turn out to be 00 + 01 + 11, but we don't need to know this yet.

With this new illustration, our initial equal superposition is shown as s. It’s closer to not x than to x because x only represents a quarter of 00 + 01 + 10 + 11 (and this would be true whichever of the four possible answers is the correct one). 

So what the oracle does is to turn the x component of s into a negative, -x component. The effect is to reflect the state vector about the not x line, to give the new vector labelled s’.

Grover’s algorithm then reflects this new vector about the original s, to give yet another new vector g.

In the general case, g is much closer to x than it was, increasing the probability that we’ll get the right answer if we take a measurement. In fact, in this special, two qubit case it turns out that g is exactly x (it’s shown slightly displaced in the illustration, but the g arrow should really lie exactly on top of x.) That means that when we measure the system we’ll get the right answer, 10 (representing 2), with certainty, with just one query to the oracle. A classical computer might have to make four queries until it stumbles on the right answer. 

With bigger datasets, we have to repeat the process (using the vector g as the starting point) until the x component is sufficiently strong to give a high probability of it being a right answer, but still with far fewer queries than in the classical case.

Another note for pedants - See my first note for pedants.