Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms

• URL: http://arxiv.org/abs/2203.00212v1
• Date: Tue, 1 Mar 2022 03:42:24 GMT
• Title: Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
• Authors: Nikhil Bansal and Makrand Sinha and Ronald de Wolf
• Abstract summary: 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.
• Score: 3.9156637371363874
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every $d$-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a $\mathrm{poly}(d)$-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-$d$ block-multilinear form with constant variance, there always exists a variable with influence at least $1/\mathrm{poly}(d)$. In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Bri\"et and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance $k$-fold Forrelation. Our main technical result relies on connections to free probability theory.

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)
• 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)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  The Unitary Synthesis Problem asks whether any $n$qubit unitary $U$ can be implemented by an efficient quantum $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In this work, we prove unitary synthesis as an efficient challenger-ad game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $Af$.
  arXiv  Detail & Related papers  (2023-10-13T05:39:42Z)
• Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms [0.0]
  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.
  arXiv  Detail & Related papers  (2023-04-13T17:58:36Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• The principle of majorization: application to random quantum circuits [68.8204255655161]
  Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable. We verified that all the families of circuits satisfy on average the principle of majorization. Clear differences appear in the fluctuations of the Lorenz curves associated to states.
  arXiv  Detail & Related papers  (2021-02-19T16:07:09Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)

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.