Groucho Marxism

Quantum computers are advanced computing systems that harness  quantum mechanics—specifically superposition and entanglement—to solve complex problems beyond the reach of classical computers. Unlike classical computers that use binary bits (0 or 1), quantum computers use quantum bits (qubits), allowing them to process vast amounts of data simultaneously. Qubits can exist in multiple states at once, allowing exponential increases in processing power compared to classical bits. Furthermore, entanglement of qubits, a quantum phenomenon where qubits become linked, allows for high-speed, complex calculations. Whilst still in development, this technology is accelerating towards practical applications in simulation, optimization, and security.

The simplest model of computation is something called a ‘finite state machine’. This is defined by a finite set of states, X; a finite input alphabet, A; and a transition function f() from XA to X. This is quite an abstract definition so let’s illustrate it with a simple example: a turnstile. This has two states, locked and unlocked, so we can take X = {0,1}, where 0 corresponds to ‘locked’ and 1 corresponds to ‘unlocked’. There are two possible inputs that affect its state: putting a coin in the slot, and pushing the arm. We can therefore take A = {0,1}, where 0 corresponds to putting a coin in the slot and 1 corresponds to pushing the arm. If a coin is put in the slot it becomes unlocked, and if the arm is pushed it becomes locked; the transition function is therefore given by f(0,0) = f(1,0) = 1, and f(0,1) = f(1,1) = 0.

A quantum computer may be modelled using something called a ‘quantum finite state machine’. As with an ordinary finite state machine, this is defined by a set of states, X; an input alphabet, A; and a transition function f() from XA to X. However, the set of states X is not longer finite but is instead assumed to be finite-dimensional a complex vector space. The transition function is represented by a collection of a ‘unitary matrices’, one for each element of the input alphabet A, which as before is assumed to be finite. A complex square matrix U is said to be unitary if its matrix inverse U^-1 equals its conjugate transpose U*; that is, if U*U = UU* = I, where I is the identity matrix. The conjugate transpose of U, in turn, is the matrix obtained by transposing U and applying complex conjugation to each entry.

Given an input letter a from the input alphabet A, the unitary matrix U(a) determines the transition of the machine from its current state x to its next state y, as follows: y = U(a)x. Thus, the transition function f() for the quantum finite state machine is given by f(x,a) = U(a)x. Again, this is quite an abstract definition so let’s illustrate it with a simple example: a quantum turnstile. This is a (theoretical!) quantum version of the turnstile described above. As there are just two underlying states, locked and unlocked, we can take the state space X to be the set of complex vectors of the form x = c₀x₀+c₁x₁, where x₀ = (1,0)’ corresponds to the locked state, x₁ = (0,1)’ corresponds to the unlocked state, and c₀,c₁ are complex numbers which are normalized so that c*c = 1, where c = (c₀,c₁)’.

The unitary transition matrices are given by: U_jk(0) = 1 if j = 0, U_jk(0)= 0 if j = 1; and U_jk(1) = 1 if j = 1, U_jk(1) = 0 if j = 0. The transition function is given by f(x,a) = U(a)x, thus: f(x₀,0) = U(0)x₀ = (0,1)’ = x₁; f(x₁,0) = U(0)x₁ = (0,1)’ = x₁; f(x₁,0) = U(0)x₁ = (1,0)’ = x₀; and f(x₁,1) = U(1)x₁ = (1,0)’ = x₀. Therefore in the case where x is a pure state (so x = x₀ or x = x₁), the result of running the machine will be exactly identical to the classical deterministic finite state machine described above. The non-classical case occurs if both c₀ and c₁ are nonzero, which captures the notion of a ‘qubit’. In this case, the probability of the machine being in state x₀ is given by |c₀|² and the probability of it being in state x₁ is given by |c₁|², where for a complex number a+bi we have |a+bi|² = a²+b².

If c₀ = a₀+b₀i and c₁ = a₁+b₁i, the probability of being in state x₀ is given by|c₀|² = a₀²+b₀² and the probability of being in state x₁ is given by |c₁|² = a₁²+b₁². We also have c* = (c₀*, c₁*) = (a₀-b₀i, a₁-b₁i), and therefore c*c = (a₀-b₀i, a₁-b₁i)(a₀+b₀i, a₁+b₁i)’ = a₀²+b₀²+a₁²+b₁². Since c*c = 1 by assumption, the probabilities of being in states x₀ and x₁ must sum to one. This can all be easily generalised to the case where the underlying machine has arbitrarily many states, as long as the number of states remains finite. Therefore, given any classical finite state machine, a corresponding quantum version can be defined. At the time of writing, most quantum computers are implementations of quantum finite state machines, which suggests that this model captures the essence of quantum computation.