A Note on Quantum Divide and Conquer for Minimal String Rotation
- URL: http://arxiv.org/abs/2210.09149v1
- Date: Mon, 17 Oct 2022 14:51:49 GMT
- Title: A Note on Quantum Divide and Conquer for Minimal String Rotation
- Authors: Qisheng Wang
- Abstract summary: Lexicographically minimal string rotation is a fundamental problem on string processing.
Near-optimal quantum algorithms have been proposed during its development, with new ideas such as quantum divide and conquer introduced.
- Score: 1.8275108630751844
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Lexicographically minimal string rotation is a fundamental problem on string
processing that has recently attracted a lot of attention in quantum computing.
Near-optimal quantum algorithms have been proposed during its development, with
new ideas such as quantum divide and conquer introduced. In this note, we
further study its quantum query complexity. Slightly improved quantum
algorithms by divide and conquer are proposed:
1. For the function problem, its query complexity is shown to be $\sqrt{n}
\cdot 2^{O\left(\sqrt{\log n}\right)}$, improving the recent result of
$\sqrt{n} \cdot 2^{\left(\log n\right)^{1/2+\varepsilon}}$ by Akmal and Jin
(2022).
2. For the decision problem, its query complexity is shown to be
$O\left(\sqrt{n \log^3 n \log \log n}\right)$, improving the recent result of
$O\left(\sqrt{n \log^5 n}\right)$ by Childs et al. (2022).
The purpose of this note is to point out some useful algorithmic tricks,
e.g., preprocessing and level-wise optimization, that can be used to improve
quantum algorithms, especially for those with a divide-and-conquer structure.
Related papers
- 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) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms.
The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$.
The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
arXiv Detail & Related papers (2024-04-08T02:13:40Z) - 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 $\text{MOD}_m^n$ and $\text{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) - 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) - 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) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems.
The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical.
We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
arXiv Detail & Related papers (2022-05-19T16:04:40Z) - 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 algorithms for escaping from saddle points [7.191453718557392]
We study quantum algorithms for escaping from saddle points with provable guarantee.
Our main contribution is the idea of replacing the classical perturbations in gradient descent methods.
We also show how to use a quantum gradient computation algorithm due to Jordan.
arXiv Detail & Related papers (2020-07-20T16:42:53Z)
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.