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:0911.2317 · Electronic Proceedings in Theoretical Computer Science

Algorithms for Quantum Branching Programs Based on Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

Published Nov 15, 2009• 29 citations
arXivHTMLPDF

Abstract

In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.

DOI
10.4204/eptcs.9.1

Related papers

On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

We develop quantum fingerprinting technique for constructing quantum branching pro-grams (QBPs), which are considered as circuits with an ability to use classical bits as control variables. We demonstrate our approach constructing optimal quantum ordered binary decision diagram (QOBDD) for MODm Boolean function. The construction of our technique also allows to extend the recent result of Ambainis and Nahimovs it is based on. In addition we show how our technique works for encoding quantum information for the equality problem in the simultaneous message passing model. 1

Electronic colloquium on computational complexity•Jan 1, 2008•9 citations

On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Farid Mansurovich Ablayev, Airat Khasianov, Alexander Vasiliev

We consider the Hidden Subgroup, and Equality-related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms in circuit notation. Our algorithms require at most logarithmic number of qubits. 1

Electronic colloquium on computational complexity•Jan 1, 2008•11 citations

On quantum realisation of Boolean functions by the fingerprinting technique

Farid Mansurovich Ablayev, A. V. Vasilyev

In this paper, we develop the fingerprinting technique of calculation of Boolean functions in quantum calculation models. The use of the fingerprinting technique is demonstrated on the example of calculation of the function MOD m in the class of quantum OBDD (oblivious read-once branching programs). Next, the potentialities of the fingerprinting technique are demonstrated in the example of realisation of the ‘equality’ function in the quantum model of communication with a referee (the SMP communication model) and in examples of recognition of languages in quantum automata. All given realisations of Boolean functions in various quantum calculation models (OBDD, SMP communication model, and a finite automaton) are asymptotically optimal. The authors thank Juhani Karhumäki for the invitation to the University of Turku and fruitful discussions of this research.

Discrete Mathematics and Applications•Jan 1, 2009•17 citations

On Computational Power of Quantum Read-Once Branching Programs

Farid Mansurovich Ablayev, Alexander Vasiliev

In this paper we review our current results concerning the computational power of quantum read-once branching programs. First of all, based on the circuit presentation of quantum branching programs and our variant of quantum fingerprinting technique, we show that any Boolean function with linear polynomial presentation can be computed by a quantum read-once branching program using a relatively small (usually logarithmic in the size of input) number of qubits. Then we show that the described class of Boolean functions is closed under the polynomial projections.

arXiv:1103.2809•Electronic Proceedings in Theoretical Computer Science•Mar 8, 2011•5 citations

COMPLEXITY BOUNDS ON SOME FUNDAMENTAL COMPUTATIONAL PROBLEMS FOR QUANTUM BRANCHING PROGRAMS

Airat Khasianov

We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.

•Jan 1, 2005•3 citations

Quantum Ordered Binary Decision Diagrams with Repeated Tests

Matthias Homeister, Stephan Waack

Quantum branching programs (quantum binary decision diagrams, respectively) are a convenient tool for examining quantum computations using only a logarithmic amount of space. Recently several types of restricted quantum branching programs have been considered, e. g. read--once quantum branching programs. This paper considers quantum ordered binary decision diagrams (QOBDDs) and answers the question: How does the computational power of QOBDDs increase, if we allow repeated tests. Additionally it is described how to synthesize QOBDDs according to Boolean operations.

arXiv:quant-ph/0507258•Jul 27, 2005•3 citations
In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
We develop quantum fingerprinting technique for constructing quantum branching pro-grams (QBPs), which are considered as circuits with an ability to use classical bits as control variables. We demonstrate our approach constructing optimal quantum ordered binary decision diagram (QOBDD) for MODm Boolean function. The construction of our technique also allows to extend the recent result of Ambainis and Nahimovs it is based on. In addition we show how our technique works for encoding quantum information for the equality problem in the simultaneous message passing model. 1
In this paper, we develop the fingerprinting technique of calculation of Boolean functions in quantum calculation models. The use of the fingerprinting technique is demonstrated on the example of calculation of the function MOD m in the class of quantum OBDD (oblivious read-once branching programs). Next, the potentialities of the fingerprinting technique are demonstrated in the example of realisation of the ‘equality’ function in the quantum model of communication with a referee (the SMP communication model) and in examples of recognition of languages in quantum automata. All given realisations of Boolean functions in various quantum calculation models (OBDD, SMP communication model, and a finite automaton) are asymptotically optimal. The authors thank Juhani Karhumäki for the invitation to the University of Turku and fruitful discussions of this research.
In this paper we review our current results concerning the computational power of quantum read-once branching programs. First of all, based on the circuit presentation of quantum branching programs and our variant of quantum fingerprinting technique, we show that any Boolean function with linear polynomial presentation can be computed by a quantum read-once branching program using a relatively small (usually logarithmic in the size of input) number of qubits. Then we show that the described class of Boolean functions is closed under the polynomial projections.
We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.
Quantum branching programs (quantum binary decision diagrams, respectively) are a convenient tool for examining quantum computations using only a logarithmic amount of space. Recently several types of restricted quantum branching programs have been considered, e. g. read--once quantum branching programs. This paper considers quantum ordered binary decision diagrams (QOBDDs) and answers the question: How does the computational power of QOBDDs increase, if we allow repeated tests. Additionally it is described how to synthesize QOBDDs according to Boolean operations.