Quantum Walks and Search Algorithms On NISQ

Quantum walks, the quantum mechanical analogue of classical random walks, offer potential computational advantages for tasks such as search algorithms and graph traversal. Realising these benefits requires scalable quantum hardware, a current limitation prompting investigation into emulators based on near-term technologies. Researchers from C12 Quantum Electronics and Aix-Marseille Université detail a method for simulating quantum walks and associated search algorithms using quantum cellular automata (QCA) mapped onto circuit Quantum Electrodynamics (cQED) hardware. In their paper, ‘Noisy simulations of Quantum Walk and Quantum Walk search via Quantum Cellular Automata on a semiconducting spin processor emulator’, A. Mammola et al. present both idealised and noise-affected simulations, utilising the Aer simulator and C12 Quantum Electronics’ in-house emulator, Callisto, to benchmark performance metrics including state count distributions and search success probability.

Quantum Walks Demonstrate Potential on Near-Term Quantum Hardware

Recent research demonstrates successful implementation of quantum walks on circuit Quantum Electrodynamics (cQED) hardware, indicating a potential avenue for utilising early-stage Noisy Intermediate-Scale Quantum (NISQ) devices. The study focuses on the one-particle sector of Quantum Cellular Automata (QCA) – a mathematical framework modelling complex systems through local interactions – and specifically employs the quantum walk algorithm on both N-cycle and NxN torus graph topologies. This work extends beyond theoretical modelling to explore the application of the quantum walk to the search problem, providing quantitative data supporting the feasibility of algorithm execution on current hardware.

Researchers mapped implementations of non-interacting QCA onto cQED hardware, establishing a platform for early NISQ implementations. cQED utilises superconducting circuits to create and manipulate quantum states. Performance evaluation involved a dual simulation strategy. Noiseless simulations were initially conducted using the Aer simulator, providing a baseline for comparison. Crucially, these were complemented by noisy simulations employing the Callisto in-house emulator developed by C12 Quantum Electronics. This approach facilitates a direct assessment of the impact of noise – inherent in all physical quantum systems – on algorithm fidelity and provides a realistic performance evaluation.

Performance benchmarks centred on several key metrics. State count distributions were analysed to provide insight into the complexity of the simulated quantum states. Hellinger Fidelity and (l_1) distance – measures of the similarity between two probability distributions – quantified the deviation between ideal and simulated quantum states. Researchers also determined the hitting time – the average number of steps required to reach a target state – and success probability, directly assessing the efficiency of the quantum walk and its application to the search problem. These metrics offer a nuanced understanding of performance limitations and potential areas for optimisation.

The combination of a carefully chosen hardware platform, a dual simulation strategy incorporating realistic noise modelling, and a focus on key performance metrics demonstrates a methodical and rigorous approach to evaluating the potential of QCA on NISQ devices. This work provides valuable data for assessing the viability of implementing more complex quantum algorithms on near-term quantum hardware.