Quantum algorithms through graph composition

• URL: http://arxiv.org/abs/2504.02115v1
• Date: Wed, 02 Apr 2025 20:20:51 GMT
• Title: Quantum algorithms through graph composition
• Authors: Arjan Cornelissen,
• Abstract summary: 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.
• Score: 0.40792653193642503
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms, where the availability of each of the graph's edges is computed by a span program. We provide an exact characterization of the resulting witness sizes in terms of effective resistances of related graphs. We also provide less-powerful, but easier-to-use upper bounds on these witness sizes. We give generic time-efficient implementations of algorithms generated through the graph composition framework, in the quantum read-only memory model, which is a weaker assumption than the more common quantum random-access model. Along the way, we simplify the span program algorithm, and remove the dependence of its analysis on the effective spectral gap lemma. We unify the quantum algorithmic frameworks that are based on span programs or the quantum adversary bound. In particular, 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. We show that the graph composition framework subsumes part of the quantum divide and conquer framework, and that it is itself subsumed by the multidimensional quantum walk framework. Moreover, we show that the weighted-decision-tree complexity is quadratically related to deterministic query complexity, and to the GT-bound with polynomial exponent 3/2. For the latter, we also provide a matching separation. We apply our techniques to give improved algorithms for various string-search problems, namely the Dyck-language recognition problem of depth 3, the 3-increasing subsequence problem, and the OR $\circ$ pSEARCH problem. We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.

Related papers

• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Quantum Algorithm for Maximum Biclique Problem [11.96554895748371]
  Identifying a biclique with the maximum number of edges bears considerable implications for numerous fields of application. We propose a ground-breaking algorithm qMBS with time complexity O*(2(n/2)), illustrating a quadratic speed-up in terms of complexity compared to the state-of-the-art. We detail two variants tailored for the maximum biclique problem and the maximum balanced biclique problem.
  arXiv  Detail & Related papers  (2023-09-08T04:43:05Z)
• 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)
• 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)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Near-term Efficient Quantum Algorithms for Entanglement Analysis [5.453850739960517]
  Entanglement plays a crucial role in quantum physics and is the key resource in quantum information processing. This work proposes three near-term efficient algorithms exploiting the hybrid quantum-classical technique to address this difficulty.
  arXiv  Detail & Related papers  (2021-09-22T15:15:58Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• 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 algorithm for Feynman loop integrals [0.0]
  We present a novel benchmark application of a quantum algorithm to Feynman loop integrals. The two on-shell states of a Feynman propagator are identified with the two states of a qubit. A quantum algorithm is used to unfold the causal singular configurations of multiloop Feynman diagrams.
  arXiv  Detail & Related papers  (2021-05-18T17:41:56Z)
• Entropic barriers as a reason for hardness in both classical and quantum algorithms [2.062593640149623]
  We study both classical and quantum algorithms to solve a hard optimization problem, namely 3-XORSAT on 3-regular random graphs. By introducing a new quasi-greedy algorithm that is not allowed to jump over large energy barriers, we show that the problem hardness is mainly due to entropic barriers.
  arXiv  Detail & Related papers  (2021-01-30T07:58:24Z)
• Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
  We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models. We additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al. for a "gapped" version of the group testing problem.
  arXiv  Detail & Related papers  (2020-11-17T13:12:43Z)

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.