Quantum Implications of Huang's Sensitivity Theorem

• URL: http://arxiv.org/abs/2004.13231v1
• Date: Tue, 28 Apr 2020 00:54:23 GMT
• Title: Quantum Implications of Huang's Sensitivity Theorem
• Authors: Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
• Abstract summary: We show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity. We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture.
• Score: 4.970364068620607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = \Omega(n)$, which is also optimal.

Related papers

• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
  arXiv  Detail & Related papers  (2024-08-20T05:20:55Z)
• A generic quantum Wielandt's inequality [0.9975341265604578]
  It is conjectured that $k$ should be of order $mathcalO(n2)$ in general. We provide a generic version of quantum Wielandt's inequality, which gives the optimal length with probability one. We shed new light on a long-standing open problem for Projected Entangled Pair State.
  arXiv  Detail & Related papers  (2023-01-19T18:57:32Z)
• Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
  A quantum algorithm finds an $x*incal K$ such that $F(x*)-min_xincal K F(x)leqepsilon$ using $tildeO(n3)$ quantum evaluation queries to $F$. As an application, we give a quantum function algorithm for zeroth-order convex bandits with $tildeO(n5log2 T)$ regret, an exponential speedup in $T$ compared to the classical $
  arXiv  Detail & Related papers  (2022-09-26T03:19:40Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• 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)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  We show that for any total Boolean function $f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$: The degree of $f$ is at mosttrivial quadratic in the approximate degree of $f$. We show that if $f$ is a non monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrmQ(f)=Omega(n)$, which is also optimal.
  arXiv  Detail & Related papers  (2020-10-23T19:21:28Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14: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.