A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions

• URL: http://arxiv.org/abs/2006.16523v1
• Date: Tue, 30 Jun 2020 04:39:20 GMT
• Title: A quantum algorithm to estimate the Gowers $U_2$ norm and linearity testing of Boolean functions
• Authors: C. A. Jothishwaran, Anton Tkachenko, Sugata Gangopadhyay, Constanza Riera, Pantelimon Stanica
• Abstract summary: We propose a quantum algorithm to estimate the Gowers $U$ norm of a Boolean function. We extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $epsilon$-far from the set of linear Boolean functions.
• Score: 6.8072479152471566
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a quantum algorithm to estimate the Gowers $U_2$ norm of a Boolean function, and extend it into a second algorithm to distinguish between linear Boolean functions and Boolean functions that are $\epsilon$-far from the set of linear Boolean functions, which seems to perform better than the classical BLR algorithm. Finally, we outline an algorithm to estimate Gowers $U_3$ norms of Boolean functions.

Related papers

• A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions [1.6574413179773761]
  The algorithm is a modified version of the permutation PSO by Hu, Eberhart and Shi. The parameters for the PSO velocity equation are tuned by means of two meta-optimization techniques.
  arXiv  Detail & Related papers  (2024-01-09T14:08:42Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
  arXiv  Detail & Related papers  (2021-05-10T13:07:44Z)
• Quantum and Randomised Algorithms for Non-linearity Estimation [0.5584060970507505]
  Non-linearity of a function indicates how far it is from any linear function. We design highly efficient quantum and randomised algorithms to approximate the non-linearity additive error.
  arXiv  Detail & Related papers  (2021-03-14T14:13:50Z)
• Non-Boolean Quantum Amplitude Amplification and Quantum Mean Estimation [0.0]
  This paper generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-boolean oracles. The eigenvalues $exp(ivarphi(x)$ of a non-boolean oracle are not restricted to be $pm 1$. Two new oracular algorithms based on such non-boolean oracles are introduced.
  arXiv  Detail & Related papers  (2021-02-09T17:48:38Z)
• Parameter-free Stochastic Optimization of Variationally Coherent Functions [19.468067110814808]
  We design and analyze an algorithm for first-order optimization of a class of functions on $mathbbRdilon. It is the first to achieve both these at the same time.
  arXiv  Detail & Related papers  (2021-01-30T15:05:34Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  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
  arXiv  Detail & Related papers  (2020-08-14T12:17:48Z)

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.