Quantum random walk search on satisfiability problems

Stephan Hoyer

Published Jan 1, 2008• 6 citations

Abstract

Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.

Related papers

Quantum-Inspired Random Walk Algorithms for Graph Search

Jincheng Zhang

This paper explores the potential of quantum-inspired algorithms for graph search problems. Traditional random walk approaches often suffer from inefficiencies, particularly in complex graphs. We propose a novel framework that leverages concepts from quantum walks – specifically interference and tunneling – within a classical computational environment. Our algorithms dynamically adjust the probability distribution of node visits based on graph connectivity and the history of previous steps, mimicking the probabilistic nature of quantum mechanics. We demonstrate that this approach can, in certain scenarios, outperform standard random walks, offering a more adaptable and potentially faster search strategy. The core of the method lies in approximating the quantum effects through carefully designed classical simulations, without requiring actual quantum hardware. We present a mathematical formulation of the core algorithm and discuss its key parameters, focusing on the balance between classical simulation fidelity and computational cost. The results suggest a promising direction for graph search optimization, drawing inspiration from the principles of quantum mechanics.

Sep 6, 20260 citations

Quantum Walk Algorithms

Robert Hundt

A quantum walk algorithm is the quantum analog to a classical random walk with potential applications in search problems, graph problems, quantum simulation, and even machine learning. In this section, we describe the basic principles of this class of algorithms on a simple one-dimensional topology.

Cambridge University Press eBooksNov 20, 20250 citations

Coined quantum walks

Nguyen, Long

Quantum computing is a developing field that applies the properties of quantum mechanics to develop solutions to complex problems that the most powerful classical computers cannot solve or cannot solve efficiently. Solving difficult tasks requires sophisticated and efficient algorithms that can utilize stochastic processes as the primary techniques. The typical models of these stochastic processes include discrete-time random walks and continuous ones. Quantum walks represent a quantum extension of discrete random walks, whose demonstrated utility in algorithm design has motivated signi cant interest in quantum computational research. Therefore, the purpose of this thesis is to explore the potential of discrete-time coined quantum walks using the Python package with high-performance computing (HPC) compared to classical walks by conducting a literature review. To supplement this research, some simulations are implemented to analyze the spreading behavior of coined quantum walks, compare them with classical walks, and demonstrate their application in search tasks, such as binary hypercube search algorithm. These simulations aim to clarify the extent to which quantum walks can be effectively modeled and applied in computational contexts. The results gained show that coined quantum walks exhibit faster spreading than classical random walks, which contributes to a deeper understanding of potential applications of quantum walks, such as quantum simulation, in the future.

Sep 5, 20250 citations

A random walk approach to quantum algorithms

Viv M. Kendon

The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.

arXiv:quant-ph/0609035Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering SciencesOct 18, 2006116 citations

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

Dec 8, 20030 citations

Quantum Speed-ups for Boolean Satisfiability and Derivative-Free Optimization

Srinivasan Arunachalam

In this thesis, we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical techniques for solving satisfiability. We compute the approximate time it would take to solve SAT instances using quantum techniques and compare it with state-of-the heart classical heuristics employed annually in SAT competitions. In the second part of the thesis, we consider a few classically well known algorithms for derivative free optimization which are \nubiquitously employed in engineering problems. We propose a quantum speedup to this classical algorithm by using techniques of the quantum minimum finding algorithm. In the third part of the thesis, we consider practical applications in the fields of bio-informatics, petroleum refineries and civil engineering which involve solving either satisfiability or derivative free optimization. We investigate if using known quantum techniques to speedup these algorithms directly translate to \nthe benefit of industries which invest in technology to solve these problems. In the last section, we propose a few open problems which we feel are immediate hurdles, either from an algorithmic or architecture perspective to getting a convincing speedup for the practical problems considered.

Apr 21, 20146 citations