Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions

• URL: http://arxiv.org/abs/2008.06317v5
• Date: Sun, 16 May 2021 13:35:55 GMT
• Title: Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions
• Authors: Chandra Sekhar Mukherjee, Subhamoy Maitra
• Abstract summary: We first obtain optimal exact quantum query algorithms ($Q_algo(f)$) for a direct sum based class of $Omega left( 2fracsqrtn2 right)$ non-symmetric functions. We show that query complexity of $Q_algo$ is $lceil frac3n4 rceil$ whereas $D_oplus(f)$ varies between $n-1$ and $lceil frac3n4 rce
• Score: 3.652509571098291
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Exact Quantum Query model, almost all of the Boolean functions for which non-trivial query algorithms exist are symmetric in nature. The most well known techniques in this domain exploit parity decision trees, in which the parity of two bits can be obtained by a single query. Thus, exact quantum query algorithms outperforming parity decision trees are rare. In this paper we first obtain optimal exact quantum query algorithms ($Q_{algo}(f)$) for a direct sum based class of $\Omega \left( 2^{\frac{\sqrt{n}}{2}} \right)$ non-symmetric functions. We construct these algorithms by analyzing the algebraic normal form together with a novel untangling strategy. Next we obtain the generalized parity decision tree complexity ($D_{\oplus}(f)$) analysing the Walsh Spectrum. Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4} \rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4} \rceil+1$ for different classes, underlining linear separation between the two measures in many cases. To the best of our knowledge, this is the first family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. We also implement these techniques for a larger (doubly exponential in $\frac{n}{4}$) class of Maiorana-McFarland type functions, but could only obtain partial results using similar algorithmic techniques.

Related papers

• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint [0.0]
  Two deterministic approximation algorithms are presented for the problem of non-monotone $k$-submodular complexity under a knapsack constraint. Our algorithms provide constant approximation ratios within only $O(nk)$ query complexity for the non-monotone objective.
  arXiv  Detail & Related papers  (2023-09-21T12:42:52Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12: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)
• Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
  We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$. Our algorithm is based on non-binary span programs and their efficient implementation.
  arXiv  Detail & Related papers  (2021-05-18T06:51:11Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• 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)

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.