The Power of Adaptivity in Quantum Query Algorithms

• URL: http://arxiv.org/abs/2311.16057v2
• Date: Thu, 7 Dec 2023 16:34:14 GMT
• Title: The Power of Adaptivity in Quantum Query Algorithms
• Authors: Uma Girish, Makrand Sinha, Avishay Tal, Kewen Wu
• Abstract summary: We study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with $r$ versus $r-1$ rounds of adaptivity.
• Score: 0.5702169790677977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where the depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with $r$ versus $r-1$ rounds of adaptivity. We do so by using the $k$-fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP'18). For $k=2r$, this problem can be solved using an $r$ round quantum algorithm with only one query per round, yet we show that any $r-1$ round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.

Related papers

• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator. Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel. Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• 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)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• 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 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)
• Variational learning algorithms for quantum query complexity [3.980076328494117]
  We develop variational learning algorithms to study quantum query complexity. We apply our method to analyze various cases of quantum query complexity. Our method can be readily implemented on the near-term Noisy Intermediate-Scale Quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2022-05-16T05:16:15Z)
• 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)
• Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
  We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-12-23T15:36:59Z)
• 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)

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.