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

Quantum Information Processing

Quantum cryptographic property testing of multi-output Boolean functions

Cui Jingyi, Jiansheng Guo

Published May 4, 2019• 4 citations
Publisher
DOI
10.1007/s11128-019-2299-1

Related papers

Quantum Algorithms for Cryptographically Significant Boolean Functions: An IBMQ Experience

Tharrmashastha Sapv, Debajyoti Bera, Arpita Maitra +1 more

SpringerBriefs in computer science•Jan 1, 2021•5 citations

Generating Property-Based Tests for Quantum Algorithms

Antonio García de la Barrera, Manuel Serrano, Ignacio García‐Rodríguez de Guzmán +2 more

Lecture notes in computer science•Jul 24, 2025•0 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

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

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

Quantum cryptography based on an algorithm for determining simultaneously all the mappings of a Boolean function

Koji Nagata, Renata Wong, Do Ngoc Diep +1 more

Quantum Studies Mathematics and Foundations•Feb 10, 2023•2 citations
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.
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