A Distributed Computing View Of Quantum State

Performing a quantum computation requires building a quantum system, or circuit, from quantum bits and extracting information from it by measuring its state. Given the non-deterministic nature of measurement, the computation has to be repeated a number of times to reveal a pattern of outcomes, which in turns provides answers we are looking for. Quantum Algorithms drastically reduce the number of times, called "shots", a computation is repeated, making the building of quantum circuits a complex combination of science and art.

However, it turns out that the domain of Quantum Computing is quite simple to implement as a simulator, and it is a perfect match for Distributed Computing, as all computations involved have a perfect symmetry associated to them. Despite the vast amount of data to be processed, quantum state is highly distributable and its processing is embarrassingly parallelizable. We are going to explore an implementation of a Quantum Computing simulator that uses parallel and distributed computing to maximum extent. Quantum Computing simulators are essential in exploring and discovering algorithms and patterns that can be later run on real Quantum Computers.

In my 2018 Quantum Computing Modeling in Scala presentation I showed the similarity between evolving quantum state and the more familiar contexts of rebalancing portfolios, or updating probabilities using the Bayes' Rule. Each transformation of the state follows simple rules, and have to maintain some obvious invariants, e.g. in the context of rebalancing a portfolio, the total balance has to stay the same. In the Quantum Computing context, the values corresponding to balances are complex numbers, which can be visualized as colors whose hues and intensities relate to the phases and magnitudes of complex numbers.

Complex numbers can be represented as colored pixels, and quantum state can be viewed as a strip of pixels, essentially an image. Evolving it can be seen as image processing, with only a few simple processing rules being allowed.

This brings us to the first type in the Quantum Computing domain: the Amplitude.

Amplitudes/Colors

In the Go language the Amplitude type is simply a complex number.

type Amplitude = complex128

Quantum Bits

Even though they are important in physical realizations of Quantum Computers, there is no direct implementation of qubits, short for quantum bits, in simulators. They are simply dimensions, or positions inside other entities.

Back to the portfolio balancing context, in the simplest case when only 2 accounts are involved, a state transformation is a transfer from one account to another. Similarly, the gate based model of Quantum Computing is based on single-dimensional transformations, involving 2 complex numbers, or 2 colors if we use the pixel based representation. A single qubit can be thought of as a set of 2 pixels, labeled 0 and 1, whose squared intensities add up to 100%. Below are some of the infinitely many possibilities for the state of one qubit.

We can also think of a qubit as a spinning coin with colored sides. The probability of the coin landing on a side is equal to the squared intensity of that side's color. The hue does not influence that probability. Real numbers correspond to a red hue.

A classical bit can only hold 0 or 1 as a value, and that value is consistently read when desired. In contrast, a quantum bit can hold infinitely more information in its state. However, that state is not accessible, and measuring it will result in the same possible outcomes of 0 or 1. We will discuss measurement later, for now we will focus on state processing.

Quantum Gates

The state of a quantum bit can be changed by blending the colors of its two pixels. Such a transformation is called a gate in the context of building a quantum circuit. It is similar to a balance transfer between two accounts.

We are showing here a simple transformation, called the Hadamard gate, which replaces the colors of two pixels by the (normalized) sum and difference of the original colors. In Quantum Computing, these are the only state transformations allowed to use in building circuits. Pixels are paired up and a blending formula is used to assign new colors to them. There is no need to go into Linear Algebra and unitary matrices to understand this.

Without going into the description of all gates, their domain representation is very simple.

type Gate struct {
   name string
   f    func(Amplitude, Amplitude) (Amplitude, Amplitude)
}

As an example, the Z gate is defined like this:

var Z = Gate{
   "Z",
   func(a Amplitude, b Amplitude) (Amplitude, Amplitude) {
      return a, -b
   },
}

And here is the implementation of the phase gate:

func R(theta float64) Gate {
   return Gate{
      "R(" + fmt.Sprintf("%.2f", theta) + ")",
      func(a Amplitude, b Amplitude) (Amplitude, Amplitude) {
         return a, b * complex(math.Cos(theta), math.Sin(theta))
      },
   }
}

Quantum Systems and their state

In a multi-qubit Quantum System, each pixel can be paired with another pixel multiple ways, one way for each qubit from which the system is built from. Remember that a qubit represents a dimension of the system. A 2-qubit system has 4 pixels, a 3-qubit system has 8 pixels, and in general a system consisting of n qubits has 2^n pixels/amplitudes. Each pixel corresponds to a possible measurement outcome, a binary string of length n.

In terms of quantum state implementation, a natural idea is to use a Go language map. But the default map data structure in Go does not allow concurrent access, assuming that insertions and removals may take place. However, by its nature, the amplitude based representation of quantum state only requires updates, and each gate operation generally updates all values. Using a binary tree seems a better option.

type Node struct {
   left  *Node
   right *Node
   level int
   label Key
   value *Amplitude
}

type Tree struct {
   root   *Node
   levels int
}

type State struct {
   bits       int
   amplitudes *Tree
}

Quantum State transformation

A single-qubit gate takes 2 pixels and changes their colors according to a blending formula. The state of a multi-qubit system is transformed using the same single-qubit gates, but each pixel can be paired with another in multiple ways. A pixel is pared with the pixel whose label differs only in the position corresponding to the target qubit.

For example, in a 3-qubit system, applying a gate to the last qubit results in the following pairing:

The labels of the paired pixels differ only in the last position. If the target pixel is the first one instead, the pairing looks like this:

Gates can be applied to a subset of pixels, by specifying control qubits. A controlled transformation restricts the gate application to pixels whose labels have a fixed value of 1 (or 0) in the positions corresponding to the control qubits.

Applying controlled gates is very expensive in real quantum computers, but easier in simulators. This is one example of the counterintuitive nature of Quantum Theory, where massive changes are easier than surgical ones, in contrast to what we are used to in classical computing.

In Go, state transformations can be represented as:

type Transformation struct {
   control map[int]bool
   target  int
   gate    Gate
}

The parallel application of a transformation can use goroutines and channels:

func Apply(state *State, transformation *Transformation) {
   count := state.bits - len(transformation.control) - 1
   N := pow2(count)

   for i := uint(0); i < procs; i++ {
      go process(i*N/procs, (i+1)*N/procs, count, transformation, state)
   }

   for i := uint(0); i < procs; i++ {
      _ = <-c
   }
}

Each goroutine processes a subtree of the quantum state. The core of the process method relies on processing pairs of pixels/amplitudes:

func processPair(state *State, pair KeyPair, gate Gate) {
   // read
   a0, a1 := state.GetAmplitude(pair.zero), state.GetAmplitude(pair.one)
   // calculate
   b0, b1 := gate.f(a0, a1)
   // update
   state.SetAmplitude(pair.zero, b0)
   state.SetAmplitude(pair.one, b1)
}

Distributing the state

Parallel processing takes advantage of all processors on a single machine, but it is limited by the computing power of that machine. Practically, one cannot go beyond simulating systems of 15-25 qubits on a single server. Each qubit represents a dimension, and will require doubling the computing requirements. An additional number of qubits can be added by scaling horizontally, similarly to sharding. For example, using a cluster of 256 machines will add 8 qubits.

One simple way to handle the distribution is to assign each node in the cluster the set of labels that start with a given prefix. This is similar to range-based sharding. The in-memory, or on-disk, binary tree processed on each node is a subtree of the whole tree representing the system state. We can visualize the state as a grid, with columns corresponding to nodes.

The implementation has to account for all subtrees, called AmplitudeStores:

type AmplitudeStore interface {
   GetAmplitude(key Key) Amplitude
   SetAmplitude(key Key, value Amplitude)
}

type AmplitudeStoreResolver interface {
   GetStoreForPrefix(prefix Key) AmplitudeStore
}

type PrefixedState struct {
   prefix string
   State  *State
   Stores AmplitudeStoreResolver
}

An AmplitudeStoreResolver is needed to access remote nodes. When a gate is applied to a target qubit that is in the suffix, there is no remote processing, pixels are paired with other pixels on the same node, and only parallel processing is needed on each node. When the target is a position in the prefix, then paired pixels are chosen from nodes whose prefixes differ only in that position.

This kind of simplicity makes the distributed implementation very efficient. Using gRPC, connections are easily reused, and streaming is possible. Here is what the ProtoBuf definition of the remote interface for each node looks like:

service QuantumState {
   rpc GetAmplitude (Location) returns (Amplitude) {}
    rpc SetAmplitude (LocationAmplitude) returns (google.protobuf.Empty) {}
    rpc H(Transformation) returns (google.protobuf.Empty) {}
    rpc R(Transformation) returns (google.protobuf.Empty) {}
    rpc CR(Transformation) returns (google.protobuf.Empty) {}

}

As an optimization for remote processing, the node holding the 0-side of a pair can request the colors of the first half of pixels from the 1-side node, do local updates and send back the new remote values. The other node processes the other half, leading to a perfect symmetry in compute and network processing.

Kubernetes can be used to manage the distributed computing, with a container being created for a driver node, and many others for the worker nodes. The driver sends gate requests to all worker nodes, and waits for acknowledgement before sending subsequent requests.

Measuring

When the state of a quantum circuit is measured, the outcome is a binary string randomly chosen based on the intensity of the corresponding pixel. One can think of the state being hidden inside a slot machine, and the measurement corresponding to pulling the lever of the slot machine. For example, the typical initial state of a quantum circuit results in the all-zero outcome when measured:

If the first qubit/dimension is put in superposition, allowing both 0 and 1 as outputs, then two possible outcomes are possible:

Given that the state of a quantum circuit is represented by a large number of pixels, hundreds of billions for a reasonably useful number of qubits, it may make sense to only retrieve the top intensities from each node. This is in line with the goal of efficient quantum computations increasing the probability of certain outcomes of interest.

Conclusion

The domain of Quantum Computing is simple to express computationally, and is a perfect match for parallel and distributed computing. Transforming the state of a quantum circuit is in essence image processing, just like building frames in an animation. Kubernetes and gRPC are ideal tools for implementing a distributed Quantum Computing simulator.