quantum_walk

quantum_walk#

Functionality#

Quantum walks are the quantum analog of classical random walks, and have been widely studied in the context of quantum algorithms and quantum computing. They have applications in various areas such as search algorithms, graph traversal, and quantum simulation. The quantum_walk.py program implements a discrete-time quantum walk on a one-dimensional line, where the walker can move left or right based on the state of a coin qubit.

quantum_walk.py#

Callee: QuantumWalk

The evolution of a quantum walk in discrete time is specified by the product of two unitary operators: (1) a “coin flip” operator and (2) a conditional shift operator, which are applied repeatedly. The program defines the joint quantum state as
\(\ket{\text{coin}}_1 \otimes \ket{\text{node}}_{n-1}\), given the input argument \(n\) (\(n>1\)).

The coin state is determined by the coin_state_preparation argument, which is a quantum circuit acting on the coin qubit. If no circuit is provided, the coin qubit is initialized to the \(\ket{0}\) state. Physically, the coin degree of freedom can be interpreted as a two-level spin system, where \(\ket{1}\) corresponds to spin up and \(\ket{0}\) corresponds to spin down. Generally, the coin state can be denoted as

\[ \ket{\text{coin}}_1 \in \mathcal{H}_C = \left\{ a_{0}\ket{0} + a_{1}\ket{1} \,\middle|\, a_{0}, a_{1} \in \mathbb{C},\ |a_{0}|^2 + |a_{1}|^2 = 1 \right\}. \]

The node state is initialized to the \(\ket{0}^{\otimes (n-1)}\) state, and can be represented as

\[ \ket{\text{node}}_{n-1} \in \mathcal{H}_N = \left\{ \sum_{x\in\mathbb{Z}} \alpha_x \ket{x}_{n-1} \,\middle|\, \sum_{x\in\mathbb{Z}} |\alpha_x|^2 < \infty \right\}. \]

The conditional shift operator for the quantum walk on the line is defined as

\[ S = \sum_{x\in\mathbb{Z}} \left( \ket{0}_1\bra{0}_1 \otimes \ket{x-1}_{n-1}\bra{x}_{n-1} + \ket{1}_1\bra{1}_1 \otimes \ket{x+1}_{n-1}\bra{x}_{n-1} \right). \]

i.e. the particle jumps right if it has spin up and left if it has spin down. Under the above convention, this corresponds exactly to the computational basis used in the code: the coin state \(\ket{1}\) (spin up) controls a shift to the right, while the coin state \(\ket{0}\) (spin down) controls a shift to the left. Explicitly, the conditional shift operator acts on product states according to

\[\begin{split} S \left( \ket{0}_1 \otimes \ket{x}_{n-1} \right) = \ket{0}_1 \otimes \ket{x-1}_{n-1}, \\ S \left( \ket{1}_1 \otimes \ket{x}_{n-1} \right) = \ket{1}_1 \otimes \ket{x+1}_{n-1}. \end{split}\]

The argument depth specifies the number of steps the quantum walk takes. Each step consists of applying a Hadamard gate \(H\) to the coin qubit, followed by the conditional shift operator \(S\).

Test expectations:

Define the one-step evolution operator as

\[ W = S(H \otimes I) \]

where \(I\) is the identity on the node register. After \(d\) steps, the final quantum state is

\[ \ket{\phi_{final}} = W^{d}\ket{\phi_0} = \sum_{c\in \{0,1\}}\sum_{x}\alpha_{c,x}\ket{c}\otimes \ket{x} \]

where the amplitudes \(\alpha_{c,x}\) are determined by repeated application of the coin flip and conditional shift.

Doc references: [43]

Execution example:

Two-step quantum walk (\(d=2\), \(n=3\)):

We consider a discrete-time quantum walk on a one-dimensional line. The system consists of one coin qubit and two position qubits.

The initial state is given by \(\ket{\psi_0}=\ket{0}_1 \otimes \ket{0}_2\), where the coin qubit is initialized in the spin-down state and the walker is localized at position \(x = 0\).

Each step of the quantum walk is governed by the unitary operator \(U = S \cdot (H \otimes I)\), where \(H\) is the Hadamard gate acting on the coin subspace and \(S\) is the conditional shift operator defined as

\[ S = \ket{0}\!\bra{0} \otimes \sum_x \ket{x-1}\!\bra{x}+\ket{1}\!\bra{1} \otimes \sum_x \ket{x+1}\!\bra{x}. \]

Step 1: Applying the Hadamard gate to the coin qubit yields

\[ (H \otimes I)\ket{\psi_0} = \frac{1}{\sqrt{2}} \left( \ket{0}_1 + \ket{1}_1 \right) \otimes \ket{0}_2. \]

After applying the conditional shift operator \(S\), the state becomes

\[ \ket{\psi_1} = \frac{1}{\sqrt{2}} \left( \ket{0}_1 \otimes \ket{-1}_2 + \ket{1}_1 \otimes \ket{+1}_2 \right). \]

Step 2: Applying the Hadamard gate again to the coin qubit gives

\[ (H \otimes I)\ket{\psi_1} = \frac{1}{2} \Big[ (\ket{0}+\ket{1}) \otimes \ket{-1} + (\ket{0}-\ket{1}) \otimes \ket{+1} \Big]. \]

Rearranging terms, we obtain

\[ (H \otimes I)\ket{\psi_1}= \frac{1}{2} \Big( \ket{0}\otimes(\ket{-1}+\ket{+1}) + \ket{1}\otimes(\ket{-1}-\ket{+1}) \Big). \]

Applying the conditional shift operator \(S\) yields the final state

\[ \ket{\psi_2} = \frac{1}{2} \Big( \ket{0}_1 \otimes (\ket{-2}_2 + \ket{0}_2) + \ket{1}_1 \otimes (\ket{0}_2 - \ket{+2}_2) \Big). \]

Final state after two steps

\[ \ket{\psi_2} = \frac{1}{2} \left( \ket{0}_1 \otimes \ket{-2}_2 + \ket{0}_1 \otimes \ket{0}_2 + \ket{1}_1 \otimes \ket{0}_2 - \ket{1}_1 \otimes \ket{+2}_2 \right) \]

API#

qolumbina.programs.quantum_walk.quantum_walk#

Qwalk benchmark definition.

class QuantumWalk(input_qubits, depth, coin_state_preparation=None, name=None)[source]#

Bases: QuantumCircuit

Create a Quantum Walk circuit.

Parameters:

  • input_qubits (int) – The total number of qubits in the circuit, including one coin qubit and input_qubits - 1 node qubits. Must be at least 2.

  • depth (int) – The number of steps (\(d\)) the quantum walk takes.

  • coin_state_preparation (QuantumCircuit | Statevector | None) – A quantum circuit or statevector to prepare the initial state of the coin qubit. If None, the coin qubit is initialized to the \(\ket{0}\) state.

  • name (str | None) – Optional name of the circuit.

Contents