Quantum and Randomised Algorithms for Non-linearity Estimation
- URL: http://arxiv.org/abs/2103.07934v2
- Date: Mon, 27 Dec 2021 11:47:42 GMT
- Title: Quantum and Randomised Algorithms for Non-linearity Estimation
- Authors: Debajyoti Bera, Tharrmashastha Sapv
- Abstract summary: 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.
- Score: 0.5584060970507505
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Non-linearity of a Boolean function indicates how far it is from any linear
function. Despite there being several strong results about identifying a linear
function and distinguishing one from a sufficiently non-linear function, we
found a surprising lack of work on computing the non-linearity of a function.
The non-linearity is related to the Walsh coefficient with the largest absolute
value; however, the naive attempt of picking the maximum after constructing a
Walsh spectrum requires $\Theta(2^n)$ queries to an $n$-bit function. We
improve the scenario by designing highly efficient quantum and randomised
algorithms to approximate the non-linearity allowing additive error, denoted
$\lambda$, with query complexities that depend polynomially on $\lambda$. We
prove lower bounds to show that these are not very far from the optimal ones.
The number of queries made by our randomised algorithm is linear in $n$,
already an exponential improvement, and the number of queries made by our
quantum algorithm is surprisingly independent of $n$. Our randomised algorithm
uses a Goldreich-Levin style of navigating all Walsh coefficients and our
quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude
amplification and amplitude estimation to improve upon the existing quantum
versions of the Goldreich-Levin technique.
Related papers
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective.
We construct a zeroth-order quantum estimator for the surrogate oracle function.
arXiv Detail & Related papers (2024-10-21T16:52:26Z) - Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt.
We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
arXiv Detail & Related papers (2024-07-10T14:08:58Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver [2.350508194508073]
We show that an explicit constant factor for an upper bound on the complexity is far more efficient than might naively be expected from the upper bound.
In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.
arXiv Detail & Related papers (2023-12-12T19:36:41Z) - 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) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.
Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
arXiv Detail & Related papers (2023-02-16T13:57:19Z) - 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) - Optimal scaling quantum linear systems solver via discrete adiabatic
theorem [0.9846257338039974]
We develop a quantum algorithm for solving linear systems that is discreteally optimal.
Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.
arXiv Detail & Related papers (2021-11-16T00:21:37Z) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions.
In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
arXiv Detail & Related papers (2020-02-10T23:23:04Z)
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.