Quantum random walks in Q#
This article presents a quantum circuit implemented in Q# simulating a random walk in an effort to showcase this new way of thinking in the world of quantum computing. A random walk is a stochastic process resulting in a path, within a domain space, constructed from a succession of random steps following certain constraints. The most trivial of examples is the random walk within the integer space Z. This walk starts from an integer in Z and taking a number of steps, with a specific step size, and following a probability distribution, ends up in another integer in Z.
To learn more about how to setup the environment needed for this example please refer to our article: Microsoft.Quantum — Implementing Quantum Fourier Neural Networks in Q# and Tensorflow.
The classical approach
How would we write a random walk in a classical computer? It is really a trivial problem, here’s a python function solving it:
def random_walk(initial_value, steps, probabilities=[0.5, 0.5]):
walk = [initial_value]
random_walk_probabilities= np.random.random(steps - 1)
random_walk= [-1] * (steps - 1)
for ix, probability in enumerate(random_walk_probabilities):
if probability > 0.5:
random_walk[ix] = 1
walk.append(walk[-1] + random_walk[ix])
return walkLet’s visualise this and talk a little more about probabilities during the walk.
I have highlighted two possible walk paths, we can construct a joint probability of all the steps in a path. For example in the orange path:
P(t3|x=3) = P(t1=+1)*P(t2=+1)*P(t3=+1)= 0.5 * 0.5 * 0.5 = 0.125.
If we were to encode the walk in a bit string, we could write something like orange_walk=111 with 1 being an up-step and 0 a down-step.
Using the beforementioned function, lets create a thousand random walks starting from 0 and taking 12, 1-sized steps, with a 50% up or down probability:
initial_value = 0
steps = 12
epochs = range(1000)
random_walk_endpoints = []
for shot in epochs:
random_walk_endpoints.append(random_walk(initial_value,steps)[-1])If we plot the resulting collection of 1000 random walks we get something like this:
Quantum structures
To understand the quantum approach we need to first briefly touch on some of the basic structures of quantum computers, like the qubit, the equivalent of the classical bit.
Any qubit, when measured, will collapse into one of two classical states, 0 or 1, exactly as we are used to in classical computing. However, by definition a qubit is a linear combination of its basis states |0> or |1>. This means that a qubit can be written as:
If we were to expand this a bit further, we would write:
Where θ and φ can be seen in the following schematic. The probability of a qubit collapsing to either 0 or 1 is dependent on θ measuring the distance of |Ψ> from |0> or |1>. While φ does not affect the final collapsed value of the qubit, it is a very important parameter used in many algorithms to achieve what is called phase kickback and amplification.
The Quantum circuit
Superposition is a very important attribute of Quantum computing, that and entanglement. When a qubit is brought in superposition, it can store information about more than one state. This is part of the advantage of quantum computing.
Moving forward, lets consider a four steps quantum walk. To implement the quantum circuit in Q# we would write:
operation QuantumRegisterRandomWalk() : Unit {
use qubits = Qubit[4];
within {
for index in 0 .. Length(qubits) - 1 {
H(qubits[index]);
}
} apply {
DumpMachine();
}
}We visualise the quantum circuit in Jupyter notebook using the magic command %trace QuantumRegisterRandomWalk:
Using the magic command %debug QuantumRegisterRandomWalk, we can see that all paths are inherently covered in this four qubit quantum circuit and by definition the probability constraints of the classical walk are met due to the default superposition behaviour. All states have the same probability of collapse. This means that the problem of the random walk is solved just by circuit design. Simulating the circuit we get the classical result:
We can see that they follow the same behaviour as the classical approach with all walk paths having the same probability to materialise.
Conclusions
In this article, we implement a quantum circuit in Q# to tackle a classical mathematical problem, that of the random walk.
The scientific community of quantum computing has made significant progress this last few years, and the roadmap ahead is expected to lead us from Noise Intermediate Scale Quantum (NISQ) devices to error corrected devices and a universal quantum computer bringing significant value through unprecedented computational capabilities to many disciplines in the industry.
If you would like to explore more complex Quantum use cases please read our relevant articles on Quantum computing on our Developer Portal!
References
SOURCE CODE
RELATED APIS
RELATED ARTICLES
