Quantum walks

In the preceding blog post, we examined the interconnection between quantum mechanics and the generation of random processes. The objective is to exploit this interconnection to enhance the efficacy of classical algorithms that employ random processes, such as random walks [1]. A random walk is a type of algorithmic process that involves taking random steps towards new points, with the probability of reaching a given point being dependent only on the previous point. Furthermore, a random walk can be classified as either pure or biased, depending on whether the probability of making all the movements is equal, or whether the algorithm assigns higher probabilities to certain movements.

In order to gain an understanding of the underlying mechanics, we will utilise an illustrative example. If our state space is the integer number line, then a move consists of adding or subtracting a number. For the sake of simplicity, we will restrict ourselves to two moves (±1) with the same probability. Consequently, if 0 is selected as the initial point, the outcome of the random walk will be the number of times 1 minus the number of times minus 1. Consider an example of five moves: +1 − 1 + 1 + 1 − 1 = 1 (Fig 1). In the event that a biased random walk is desired, it would be sufficient to either increase the probability of one outcome occurring in preference to another, or to select a larger move in one of the directions. For instance, a random walk analogous to the previous one, in which the moves instead of ±1 are (−1, +2) with equal probability.

Figure 1: Example of a quantum walk in the integer number line.   

In the case of the quantum walk [2], quantum physics is not only employed for the selection of motion, given that it is a random process. Furthermore, the principle of superposition is employed, rather than applying the quantum walk to a specific point. Instead, it is applied to a superposition of states. The objective now is to provide a quantum version of the simple random walk previously described. The state space is defined as the set of all possible positions within the integer number line, represented by |x⟩ ∈ {|0⟩, |±1⟩,|±2⟩,· · ·,|±N⟩}. In order to define the quantum walk, it is necessary to introduce an auxiliary qubit, which will be used to determine whether the movement is 1 or −1. This qubit is typically referred to as a coin, and it is represented by the state |C⟩ ∈ {|↑⟩,|↓⟩}. In this manner, the system is defined as |ψ⟩ = |C⟩⊗|x⟩. In order to give a step, a Hadamard gate will be applied to the coin. Subsequently, a gate is applied on |x⟩ which will act as a shift of +1 if the coin is |↑⟩ and -1 in the case |↓⟩. To illustrate, consider the initial state to be |↑⟩ ⊗ |0⟩, giving the first step leads us to:

                                   (1)

In order to proceed with the subsequent steps, it is sufficient to apply the same strategy, but this time to the state |ψ₁⟩.

                            (2)

After N steps, |ψN ⟩ will be a superposition of the different possible states (|x⟩) with different amplitudes and therefore different probabilities. One difference that can be easily seen is the appearance of the minus sign in the last term; the appearance of signs will cause interference, either destructive or constructive, which will make the quantum walk quadratically faster than the classical algorithm. The quantum walk can also be biased, for example by varying the gate applied to the coin, therefore conditioning the probabilities.

Although in both cases we have confined ourselves to the simple example of the integer number line, the generalisation of this concept applies to many problems, such as the modelling of financial assets [3]. In this case, the use of quantum mechanics gives us an advantage in computational speed for problems that could be solved by a random walk. Provided the technology is developed to run this algorithm on real quantum computers.

References

[1] Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random Walks: A Review of Algorithms and Applications. IEEE Transactions on Emerging Topics in Computational Intelligence, 4(2):95–107, April 2020. Conference Name: IEEE Transactions on Emerging Topics in Computational Intelligence.

[2] Julia Kempe. Quantum random walks - an introductory overview. Contemporary Physics, 44(4):307–327, July 2003. arXiv:quant-ph/0303081.

[3] Eugene F. Fama. Random Walks in Stock Market Prices. Financial Analysts Journal, 21(5):55–59, 1965. Publisher: CFA Institute.