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:1701.06942 · Baltic Journal of Modern Computing

Optimal One-shot Quantum Algorithm for EQUALITY and AND

Andris Ambainis, Jānis Iraids

Published Dec 19, 2016• 2 citations
arXivHTMLPDF

Abstract

We study the computation complexity of Boolean functions in the quantum black box model.In this model our task is to compute a function f : {0, 1} → {0, 1} on an input x ∈ {0, 1} n that can be accessed by querying the black box.Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries.We show that the lowest possible error probability for ANDn and EQUALITY n+1 is 1 2 -n n 2 +1 .

DOI
10.22364/bjmc.2016.4.4.09

Related papers

An improved quantum query algorithm for computing AND Boolean function

Alina Vasilieva, Taisia Mischenko-Slatenkova

We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•0 citations

High precision quantum query algorithm for computing AND-based boolean functions

Alina Vasilieva, Taisia Mischenko-Slatenkova

Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi is a Boolean function. Finally, we demonstrate another kind of an algorithm for AND of two variables, that has a correct answer probability p=9/10, but cannot be extended to compute AND(f1,f2).

ACM International Conference on Computing Frontiers (CF)•May 17, 2010•0 citations

Quantum Query Algorithm Constructions for Computing AND, OR and MAJORITY Boolean Functions

Alina Vasilieva

Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.

arXiv:0710.5592•Oct 30, 2007•1 citation

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve +2 more

We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.

arXiv:quant-ph/9802049•Journal of the ACM•Jul 1, 2001•922 citations

Quantum Query Algorithm Constructions for Computing AND, OR and MAJORITY Boolean Functions

Alina Vasiljeva

Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.

•Jan 1, 2008•1 citation

Properties and application of nondeterministic quantum query algorithms

Alina Dubrovska

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

arXiv:quant-ph/0606248•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations
We study the computation complexity of Boolean functions in the quantum black box model.In this model our task is to compute a function f : {0, 1} → {0, 1} on an input x ∈ {0, 1} n that can be accessed by querying the black box.Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries.We show that the lowest possible error probability for ANDn and EQUALITY n+1 is 1 2 -n n 2 +1 .
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi is a Boolean function. Finally, we demonstrate another kind of an algorithm for AND of two variables, that has a correct answer probability p=9/10, but cannot be extended to compute AND(f1,f2).
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.
Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.