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
- Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting.
Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
arXiv Detail & Related papers (2025-02-13T12:04:39Z) - 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 Algorithm for Minimizing the Maximal Loss [16.91814406135565]
We conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions.
We prove that quantum algorithms must take $tildeOmega(sqrtNepsilon-2/3)$ queries to a first order quantum oracle.
arXiv Detail & Related papers (2024-02-20T06:23:36Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Taming Quantum Time Complexity [45.867051459785976]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit.
Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry.
arXiv Detail & Related papers (2022-05-09T01:49:21Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order.
We propose an $O(n3/4)$ quantum query algorithm for LMSR.
arXiv Detail & Related papers (2020-12-17T03:13:45Z) - 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.