Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms

• URL: http://arxiv.org/abs/2304.06713v2
• Date: Wed, 28 Jun 2023 12:39:58 GMT
• Title: Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms
• Authors: Francisco Escudero Guti\'errez
• Abstract summary: We show that quantum query algorithms are characterized by a new class of Fourier completely boundeds. We conjecture that all suchs have an influential variable. Our proof is simpler, obtains better constants and does not use randomness.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a new presentation of the main result of Arunachalam, Bri\"et and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms. We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials. This implies that if the output of $d$-query quantum algorithm is a homogeneous polynomial $p$ of degree $2d$, then it has a variable with influence at least $Var[p]^2$. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.

Related papers

• Quantum Advantage via Solving Multivariate Quadratics [12.62849227946452]
  We show that there is a quantum-time algorithm that simultaneously solves $p_i(x_n)=y_i_iin [m]$ over $mathbbF$. While a solution exists with high probability, we conjecture that it is hard to find one based on classical cryptanalysis.
  arXiv  Detail & Related papers  (2024-11-22T03:10:10Z)
• 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)
• Complementary polynomials in quantum signal processing [0.0]
  To implement a given $P$, one must first construct a corresponding complementary $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementarys using complex analysis.
  arXiv  Detail & Related papers  (2024-06-06T16:47:11Z)
• 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)
• The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
  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.
  arXiv  Detail & Related papers  (2023-11-27T18:21: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)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• On converses to the polynomial method [0.0]
  A surprising 'converse to the method' of Aaronson et al. shows that any bounded quadratic can be computed exactly up to a universal multiplicative factor related to the Grohendieck constant. We show that the result still holds when we allow for a small additive error.
  arXiv  Detail & Related papers  (2022-04-26T13:32:02Z)
• Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms [3.9156637371363874]
  We prove the Aaronson-Ambainis conjecture (Theory of Computing '14) In every completely bounded degree-$d$ block-multilinear form with constant variance, there always exists a variable with influence at least $1/mathrmpoly(d)$. We obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms.
  arXiv  Detail & Related papers  (2022-03-01T03:42:24Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.