Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1306.6195

Improved quantum test for linearity of a Boolean function

Kaushik Chakraborty, Subhamoy Maitra

Published Jun 26, 2013• 9 citations
arXivHTMLPDF

Abstract

Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is $ε$-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or $ε$-far $(0 < ε< \frac{1}{2})$ from linear functions requires $O(ε^{-\frac{2}{3}})$ many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to $O(ε^{-\frac{1}{2}})$ by using the Deutsch-Jozsa and the Grover Algorithms.

DOI
10.48550/arxiv.1306.6195

Related papers

Quantum tests for the linearity and permutation invariance of Boolean functions

Mark S. Hillery, Erika Andersson

The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.

arXiv:1106.4831•Physical Review A•Dec 28, 2011•20 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $\varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$, of $n$ variables, is identical with a given function $g$ or is $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose an exact quantum algorithm for making distinction between $|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae

arXiv:2109.06763•Fundamenta Informaticae•Nov 18, 2021•6 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $\varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$, of $n$ variables, is identical with a given function $g$ or is $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose an exact quantum algorithm for making distinction between $|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae

Fundamenta Informaticae•Nov 18, 2021•0 citations

Comparing two quantum oracles using the Deutsch–Jozsa algorithm

Attila Kiss, Krisztián Varga

There are a lot of articles about quantum algorithms, which involve querying a black box function, often called an oracle.This paper proposes a way to combine two oracles and to determine how similar they are using the Deutsch-Jozsa algorithm.In this case being similar means, that the sets of marked states have just a few ones outside of their intersection.The new quantum algorithm is compared to its classical counterparts and a detailed analysis shows when it will outperform them.

Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatorica•Jan 1, 2020•1 citation

Quantum and Randomised Algorithms for Non-linearity Estimation

Debajyoti Bera, Tharrmashastha Sapv

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 Θ (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 λ, with query complexities that depend polynomially on λ. 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.

arXiv:2103.07934•ACM Transactions on Quantum Computing•Jun 30, 2021•4 citations

Quantum conditional query complexity

Imdad S. B. Sardharwalla, Sergii Strelchuk, Richard Jozsa

We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.

arXiv:1609.01600•Quantum Information and Computation•May 1, 2017•6 citations
Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is εεε-far from having that property. The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives. The best known quantum algorithm for testing whether a function is linear or εεε-far (0<ε<12)(0 < ε< \frac{1}{2})(0<ε<21​) from linear functions requires O(ε−23)O(ε^{-\frac{2}{3}})O(ε−32​) many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show that this can be improved to O(ε−12)O(ε^{-\frac{1}{2}})O(ε−21​) by using the Deutsch-Jozsa and the Grover Algorithms.
The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε\varepsilonε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function fff, of nnn variables, is identical with a given function ggg or is ε\varepsilonε-far from ggg, where ε\varepsilonε is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O(1ε)O(\frac{1}{\sqrt{\varepsilon}})O(ε​1​). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ(1ε)\Theta(\frac{1}{\varepsilon})Θ(ε1​). Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f,g)C(f,g)C(f,g) denote the correlation of fff and ggg. We propose an exact quantum algorithm for making distinction between ∣C(f,g)∣=ε|C(f,g)|=\varepsilon∣C(f,g)∣=ε and ∣C(f,g)∣=1|C(f,g)|=1∣C(f,g)∣=1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n)\Theta(2^{n})Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε\varepsilonε-far balanced using O(1ε)O(\frac{1}{\varepsilon})O(ε1​) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2)O(1/\varepsilon^{2})O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε\varepsilonε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function fff, of nnn variables, is identical with a given function ggg or is ε\varepsilonε-far from ggg, where ε\varepsilonε is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O(1ε)O(\frac{1}{\sqrt{\varepsilon}})O(ε​1​). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ(1ε)\Theta(\frac{1}{\varepsilon})Θ(ε1​). Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f,g)C(f,g)C(f,g) denote the correlation of fff and ggg. We propose an exact quantum algorithm for making distinction between ∣C(f,g)∣=ε|C(f,g)|=\varepsilon∣C(f,g)∣=ε and ∣C(f,g)∣=1|C(f,g)|=1∣C(f,g)∣=1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n)\Theta(2^{n})Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε\varepsilonε-far balanced using O(1ε)O(\frac{1}{\varepsilon})O(ε1​) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2)O(1/\varepsilon^{2})O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae
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 Θ (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 λ, with query complexities that depend polynomially on λ. 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.
We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.