Quantum divide and conquer

• URL: http://arxiv.org/abs/2210.06419v1
• Date: Wed, 12 Oct 2022 17:14:28 GMT
• Title: Quantum divide and conquer
• Authors: Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang
• Abstract summary: Divide-and-conquer framework is used extensively in classical algorithm design. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ that characterizes the quantum query complexity.
• Score: 6.527258283771695
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size $n$ into smaller subproblems (say, $a$ copies of size $n/b$ each), along with some auxiliary work of cost $C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) + C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) \leq \sqrt{a} \, C_Q(n/b) + O(C^{\textrm{aux}}_Q(n))$$ that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.

Related papers

• Quantum Data Structure for Range Minimum Query [30.186099880107964]
  We propose a quantum data structure that supports RMQ queries and range updates.<n>We obtain a time-efficient quantum algorithm for $k$-minimum finding without the use of quantum random access memory.
  arXiv  Detail & Related papers  (2026-01-19T16:19:44Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder. We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Quantum Algorithm for the Multiple String Matching Problem [0.0]
  We consider a sequence of $m$ strings, denoted by $S$, which we refer to as a dictionary. The objective is to identify all instances of strings from the dictionary within the text. We propose a quantum algorithm with $O(n+sqrtmLlog nlog n)$ query complexity and $O(n+sqrtmLlog n)=O*(n+sqrtmL)$ time complexity.
  arXiv  Detail & Related papers  (2024-11-22T10:50:43Z)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Decision Processes (MDs) with finite state spaces.<n>We demonstrate that the step sizes for both the actor and critic must decay as ( O(k-Pfrac12) ) with $k$ diverging from the conventional ( O(k-Pfrac12) ) rates commonly used in (non- optimal) Markov framework optimization.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
  We consider the two most common distances: Hamming distance in Pattern Matching with Mismatches and edit distance in Pattern Matching with Edits. We present quantum algorithms with a time complexity of $tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatches and $hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Edits.
  arXiv  Detail & Related papers  (2024-10-09T12:05:26Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
  We present a quantum property testing algorithm for recognizing a context-free language that is a concatenation of two palindromes $L_REV$.
  arXiv  Detail & Related papers  (2024-06-17T07:19:20Z)
• Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization [2.684542790908823]
  We present a quantum $tildeO(sqrtnk+k2)$-time algorithm that uses $tildeO(sqrtnz)$ queries, where $tildeO(cdot)$ hides polylogarithmic factors. Our second main contribution is a quantum algorithm that achieves the optimal time complexity of $tildeO(sqrtnz)$.
  arXiv  Detail & Related papers  (2023-11-03T09:09:23Z)
• On the exact quantum query complexity of $\ ext{MOD}_m^n$ and $\ ext{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

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.