Quantum Query-Space Lower Bounds Using Branching Programs

• URL: http://arxiv.org/abs/2407.06872v2
• Date: Sat, 5 Oct 2024 12:29:13 GMT
• Title: Quantum Query-Space Lower Bounds Using Branching Programs
• Authors: Debajyoti Bera, Tharrmashastha SAPV,
• Abstract summary: We show the first explicit query-space lower bound for our restricted version of GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance. Our results produce an alternative proof of the $Omega(sqrtn)$-lower bound on the query complexity of any non-constant symmetric Boolean function.
• Score: 0.18416014644193066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Branching programs are quite popular for studying time-space lower bounds. Bera et al. recently introduced the model of generalized quantum branching program aka. GQBP that generalized two earlier models of quantum branching programs. In this work we study a restricted version of GQBP with the motivation of proving bounds on the query-space requirement of quantum-query circuits. We show the first explicit query-space lower bound for our restricted version. We prove that the well-studied OR$_n$ decision problem, given a promise that at most one position of an $n$-sized Boolean array is a 1, satisfies the bound $Q^2 s = \Omega(n^2)$, where $Q$ denotes the number of queries and $s$ denotes the width of the GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance; this gives us query-space lower bounds on problems such as Parity and Majority. Our results produce an alternative proof of the $\Omega(\sqrt{n})$-lower bound on the query complexity of any non-constant symmetric Boolean function.

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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Space-bounded quantum state testing via space-efficient quantum singular value transformation [2.647089498084052]
  We present a novel complete characterization for space-bounded quantum computation. We consider settings with one-sided error (unitary coRQL) and two-sided error (BQL) Our results reveal that the space-bounded state testing problems all correspond to the same class.
  arXiv  Detail & Related papers  (2023-08-09T17:16:19Z)
• A Generalized Quantum Branching Program [0.5584060970507505]
  We propose a quantum branching program model, referred to as GQBP, with the ability to query different variables in superposition. We show several equivalences, namely, between GQBP and AQBP, GQBP and NQBP, and GQBP and query complexities.
  arXiv  Detail & Related papers  (2023-07-21T07:27:51Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  We present a time analogue quantum algorithm making a single query (in superposition) to a classical oracle. We prove that every $n$-qubit state can be constructed to within 0.01 error by an $On/n)$-size circuit over an appropriate finite gate set.
  arXiv  Detail & Related papers  (2023-06-02T17:49:35Z)
• Approximate degree lower bounds for oracle identification problems [19.001036556917818]
  We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
  arXiv  Detail & Related papers  (2023-03-07T14:30:28Z)
• 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)
• 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)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• 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)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs. For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
  arXiv  Detail & Related papers  (2019-12-29T01:42:31Z)

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.