Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer

• URL: http://arxiv.org/abs/2401.08355v2
• Date: Tue, 7 May 2024 21:21:42 GMT
• Title: Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
• Authors: Stacey Jeffery, Galina Pass,
• Abstract summary: We introduce an object called a emphsubspace graph that formalizes the technique of multidimensional quantum walks. We show how to combine a emphswitching network with arbitrary quantum subroutines, to compute a composed function.
• Score: 0.5064404027153093
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce an object called a \emph{subspace graph} that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a \emph{switching network} with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide \& Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch's algorithm for directed $st$-connectivity.

Related papers

• How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
  We show that advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model. We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.
  arXiv  Detail & Related papers  (2024-10-24T17:11:37Z)
• Hybrid Quantum-Classical Machine Learning with String Diagrams [49.1574468325115]
  This paper develops a formal framework for describing hybrid algorithms in terms of string diagrams. A notable feature of our string diagrams is the use of functor boxes, which correspond to a quantum-classical interfaces.
  arXiv  Detail & Related papers  (2024-07-04T06:37:16Z)
• Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions [0.0]
  We introduce an elementary form of the quantum recursion, called the fast quantum recursion, and formulate $EQS$ of elementary' quantum functions. This class captures exactly quantum polylogarithmic-time computability, which forms the complexity class BQPOLYLOGTIME. We also consider an algorithmic scheme that implements the well-known divide-and-conquer strategy.
  arXiv  Detail & Related papers  (2023-11-27T14:53:45Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• 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)
• Quantum Circuits in Additive Hilbert Space [0.0]
  We show how conventional circuits can be expressed in the additive space and how they can be recovered. In particular in our formalism we are able to synthesize high-level multi-controlled primitives from low-level circuit decompositions. Our formulation also accepts a circuit-like diagrammatic representation and proposes a novel and simple interpretation of quantum computation.
  arXiv  Detail & Related papers  (2021-11-01T19:05:41Z)
• 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)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Creating and manipulating a Laughlin-type $\nu=1/3$ fractional quantum Hall state on a quantum computer with linear depth circuits [0.0]
  We present an efficient quantum algorithm to generate an equivalent many-body state to Laughlin's $nu=1/3$ fractional quantum Hall state. Our algorithm only uses quantum gates acting on neighboring qubits in a quasi-one-dimensional setting.
  arXiv  Detail & Related papers  (2020-05-05T18:00:01Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.