Quantum advantage and lower bounds in parallel query complexity
- URL: http://arxiv.org/abs/2410.02665v1
- Date: Thu, 3 Oct 2024 16:50:00 GMT
- Title: Quantum advantage and lower bounds in parallel query complexity
- Authors: Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati,
- Abstract summary: We investigate quantum, randomized and deterministic (sequential) query complexities for total functions.
We find that significantly larger separations between the parallel generalizations of these measures are possible.
We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular, (1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of Jeffery et al. 2017 (arXiv:1309.6116). (2) We strengthen (1) by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism. (3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of Montanaro in 2010 (arXiv:1001.0018) that there is at most a constant separation for 1-round (nonadaptive) algorithms. (4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them. We also provide separations between randomized and deterministic parallel query complexities analogous to items (1)-(3).
Related papers
- 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 Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
We study the query complexity of Boolean functions under general higher order quantum computations.
We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity.
We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
arXiv Detail & Related papers (2023-07-18T13:12:55Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity.
A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances.
The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z) - Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks [0.0]
We show that a simple telescoping sum trick, together with the triangle inequality and a tensorisation property of expected-contractive coefficients of random channels, allow us to achieve general simultaneous decoupling for multiple users via local actions.
We obtain bounds on the expected deviation from ideal decoupling either in the one-shot setting in terms of smooth min-entropies, or the finite block length setting in terms of R'enyi entropies.
This leads to one-shot, finite block length, and simultaneous achievability results for several tasks in quantum Shannon theory.
arXiv Detail & Related papers (2023-04-24T14:17:32Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function.
For an alphabet size, we have a constant versus separation complexity.
arXiv Detail & Related papers (2023-01-22T22:08:28Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Bounds on quantum evolution complexity via lattice cryptography [0.0]
We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators.
Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
arXiv Detail & Related papers (2022-02-28T16:20:10Z) - On query complexity measures and their relations for symmetric functions [0.0]
We show how to give lower bounds on quantum query complexity using Boolean and adversary methods.
We also look at the quantum query complexity of Gap Majority, a partial symmetric function.
We show how large certificate complexity and block sensitivity can be as compared to sensitivity for symmetric functions.
arXiv Detail & Related papers (2021-10-25T02:55:39Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself.
We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
arXiv Detail & Related papers (2021-06-23T16:33:33Z)
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.