Quantum walks through generalized graph composition

• URL: http://arxiv.org/abs/2510.04973v1
• Date: Mon, 06 Oct 2025 16:07:20 GMT
• Title: Quantum walks through generalized graph composition
• Authors: Arjan Cornelissen,
• Abstract summary: We generalize the recently-introduced graph composition framework to the non-boolean setting.<n>For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs.<n>We provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator.
• Score: 0.30458514384586405
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, where each hyperedge is adjacent to multiple vertices. The input and output to the quantum algorithm is represented by a set of boundary vertices, and the hyperedges act like switches, connecting the input vertex to the output that the algorithm computes. Apart from generalizing the graph composition framework, our new proposed framework unifies the quantum divide and conquer framework, the decision-tree framework, and the unified quantum walk search framework. For the decision trees, we additionally construct a quantum algorithm from an improved weighting scheme in the non-boolean case. For quantum walk search, we show how our techniques naturally allow for amortization of the subroutines' costs. Previous work showed how one can speed up ``detection'' of marked vertices by amortizing the costs of the quantum walk. In this work, we extend these results to the setting of ``finding'' such marked vertices, albeit in some restricted settings. Along the way, we provide a novel analysis of irreducible, reversible Markov processes, by linear-algebraically connecting its effective resistance to the random walk operator. This significantly simplifies the algorithmic implementation of the quantum walk search algorithm, achieves an amortization speed-up for quantum walks over Johnson graphs, avoids the need for quantum fast-forwarding, and removes the log-factors from the query complexity statements.

Related papers

• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Quantum spatial best-arm identification via quantum walks [0.5541644538483946]
  We propose a quantum algorithm for best-arm identification in graph bandits.<n>We employ quantum walks to encode superpositions over graph-constrained actions.<n>Our results highlight the potential of quantum walks to accelerate exploration in constrained environments.
  arXiv  Detail & Related papers  (2025-09-07T01:53:09Z)
• Graph theory-based automated quantum algorithm for efficient querying of acyclic and multiloop causal configurations [0.0]
  We present the Minimum Clique-optimised quantum algorithm (MCA), an automated quantum algorithm designed to efficiently query the causal structures within the Loop-Tree Duality.<n>The MCA quantum algorithm is optimised by exploiting graph theory techniques, specifically, by analogy with the Minimum Clique Partition problem.
  arXiv  Detail & Related papers  (2025-08-06T02:18:08Z)
• Quantum algorithms through graph composition [0.40792653193642503]
  We introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms.<n>We show how the st-connectivity framework subsumes the learning graph framework, the weighted-decision-tree framework, and a zero-error version of the latter.<n>We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.
  arXiv  Detail & Related papers  (2025-04-02T20:20:51Z)
• Simple Quantum Gradient Descent Without Coherent Oracle Access [0.0]
  We develop an alternative quantum framework for the gradient descent problem, based on the seminal quantum singular value transformation framework.<n>We show that given only classical information of function of interest, it is possible to construct a quantum gradient descent algorithm with a running time logarithmical in the number of variables.
  arXiv  Detail & Related papers  (2024-12-24T09:48:38Z)
• Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
  This paper examines the quantum walk search algorithm on complete multipartite graphs. We employ the coined quantum walk model and achieve quadratic speedup. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
  arXiv  Detail & Related papers  (2024-10-07T11:13:41Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.