Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0903.3465 · Quantum Information and Computation

Efficient circuits for quantum walks

C.-F. Chiang, Daniel Nagaj, Paweł Wocjan

Published May 1, 2010• 31 citations
arXivHTMLPDF

Abstract

We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph's method for preparing coherent versions of efficiently integrable probability distributions \cite{GroverRudolph}. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk \cite{Szegedy}, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents \cite{Vigoda, Vazirani} and sampling from binary contingency tables \cite{Stefankovi}. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required.

DOI
10.26421/qic10.5-6-4

Related papers

The Power Of Quantum Walk Insights, Implementation, And Applications

Chen Fu Chiang

In this thesis, I investigate quantum walks in quantum computing from three aspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two reflections in the walk operator provides a quadratic speed-up, in comparison to the classical counterpart. For the implementation of quantum walks, I show the construction of an efficient circuit for realizing one single step of the quantum walk operator. Furthermore, I devise a more succinct circuit to approximately implement quantum phase estimation with constant precision controlled phase shift operators. From an implementation perspective, efficient circuits are always desirable because the realization of a phase shift operator with high precision would be a costly task and a critical obstacle. For the applications of quantum walks, I apply the quantum walk technique along with other fundamental quantum techniques, such as phase estimation, to solve the partition function problem. However, there might be some scenario in which the speed-up of spectral gap is insignificant. In a situation like that that, I provide an amplitude amplification-based iii approach to prepare the thermal Gibbs state. Such an approach is useful when the spectral gap is extremely small. Finally, I further investigate and explore the effect of noise (perturbation) on the performance of quantum walks

Journal of International Crisis and Risk Communication Research•Jan 1, 2011•0 citations

Quantum circuits for the Metropolis–Hastings algorithm

Baptiste Claudon, Pablo Rodenas-Ruiz, Jean‐Philip Piquemal +1 more

Abstract Szegedy’s quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis–Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy’s approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.

arXiv:2506.11576•Journal of Physics A Mathematical and Theoretical•Jul 14, 2026•9 citations

A quantum algorithm for simulating non-sparse Hamiltonians

Chunhao Wang, Leonard Wossnig

We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H}\,\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.

arXiv:1803.08273•Quantum Information and Computation•Jun 1, 2020•29 citations

An Efficient Algorithm for Sparse Quantum State Preparation

Niels Gleinig, Torsten Hoefler

Generating quantum circuits that prepare specific states is an essential part of quantum compilation. Algorithms that solve this problem for general states generate circuits at grow exponentially in the number of qubits. However, in contrast to general states, many practically relevant states are sparse in the standard basis. In this paper we show how sparsity can be used for efficient state preparation. We present a polynomial-time algorithm that generates polynomial-size quantum circuits (linear in the number of nonzero coefficients times number of qubits) that prepare given states, making computer-aided design of sparse state preparation scalable.

ACM/IEEE Design Automation Conference (DAC)•Nov 8, 2021•61 citations

Resource-Efficient Synthesis of Sparse Quantum States

Renaud Vilmart, Sunheang Ty, Chetra Mang

Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches $\mathcal O\left(s+\log_2(1/ε)\right)$ T gates for error $ε$. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.

arXiv:2508.05386•Aug 7, 2025•3 citations

Black-box Hamiltonian simulation and unitary implementation

Andrew M. Childs, Dominic William Berry

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness $\sparseness$ (the maximum number of nonzero elements in a column) and the evolution time $t$, whereas previous methods had complexity scaling as $\sparseness^4$ and were superlinear in $t$. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified $\UN\times\UN$ unitary operation use $\tilde O(\UN^2)$ elementary gates, we show that a black-box unitary can be performed with bounded error using $O(\UN^{2/3} (\log\log \UN)^{4/3})$ queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only $\tilde O(\sqrt{\UN})$ queries, which is optimal.

Quantum Information and Computation•Jan 1, 2012•111 citations
We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph's method for preparing coherent versions of efficiently integrable probability distributions \cite{GroverRudolph}. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk \cite{Szegedy}, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents \cite{Vigoda, Vazirani} and sampling from binary contingency tables \cite{Stefankovi}. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required.
In this thesis, I investigate quantum walks in quantum computing from three aspects: the insights, the implementation, and the applications. Quantum walks are the quantum analogue of classical random walks. For the insights of quantum walks, I list and explain the required components for quantizing a classical random walk into a quantum walk. The components are, for instance, Markov chains, quantum phase estimation, and quantum spectrum theorem. I then demonstrate how the product of two reflections in the walk operator provides a quadratic speed-up, in comparison to the classical counterpart. For the implementation of quantum walks, I show the construction of an efficient circuit for realizing one single step of the quantum walk operator. Furthermore, I devise a more succinct circuit to approximately implement quantum phase estimation with constant precision controlled phase shift operators. From an implementation perspective, efficient circuits are always desirable because the realization of a phase shift operator with high precision would be a costly task and a critical obstacle. For the applications of quantum walks, I apply the quantum walk technique along with other fundamental quantum techniques, such as phase estimation, to solve the partition function problem. However, there might be some scenario in which the speed-up of spectral gap is insignificant. In a situation like that that, I provide an amplitude amplification-based iii approach to prepare the thermal Gibbs state. Such an approach is useful when the spectral gap is extremely small. Finally, I further investigate and explore the effect of noise (perturbation) on the performance of quantum walks
Abstract Szegedy’s quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis–Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy’s approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.
We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is O(t\sqrt{N}\norm{H}\,\polylog(N, t\norm{H}, 1/\epsilon)), where t is the evolution time, NNN is the dimension of the system, and ϵ\epsilonϵ is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving \widetilde{O}(\sqrt{N}) dependence for both applications.
Generating quantum circuits that prepare specific states is an essential part of quantum compilation. Algorithms that solve this problem for general states generate circuits at grow exponentially in the number of qubits. However, in contrast to general states, many practically relevant states are sparse in the standard basis. In this paper we show how sparsity can be used for efficient state preparation. We present a polynomial-time algorithm that generates polynomial-size quantum circuits (linear in the number of nonzero coefficients times number of qubits) that prepare given states, making computer-aided design of sparse state preparation scalable.
Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches O(s+log⁡2(1/ε))\mathcal O\left(s+\log_2(1/ε)\right)O(s+log2​(1/ε)) T gates for error εεε. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.
We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness $\sparseness$ (the maximum number of nonzero elements in a column) and the evolution time ttt, whereas previous methods had complexity scaling as $\sparseness^4$ and were superlinear in ttt. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified $\UN\times\UN$ unitary operation use $\tilde O(\UN^2)$ elementary gates, we show that a black-box unitary can be performed with bounded error using $O(\UN^{2/3} (\log\log \UN)^{4/3})$ queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only $\tilde O(\sqrt{\UN})$ queries, which is optimal.