COMPLEXITY BOUNDS ON SOME FUNDAMENTAL COMPUTATIONAL PROBLEMS FOR QUANTUM BRANCHING PROGRAMS

Airat Khasianov

Published Jan 1, 2005• 3 citations

Abstract

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.

DOI: 10.13140/rg.2.2.19342.66889

Related papers

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 complexityJan 1, 200811 citations

Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem.

Airat Khasianov

We consider the Hidden Subgroup in the context of quantum Ordered Binary Decision Diagrams. We show several lower bounds for this function. In this paper we also consider a slightly more general definition of the hidden subgroup problem (in contrast to that in [KH10]). It turns out that in this case the problem is intractable for the quantum OBDD. We prove exponential lower bounds for this function.

Electronic colloquium on computational complexityJan 1, 20100 citations

ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM

Stephen Fenner, Yong Zhang

We study the computational complexity of the HIDDEN SUBGROUP problem, a well-studied problem in quantum computing. First we show that several proposed generalizations or variants of this problem, including HIDDEN COSET, HIDDEN SHIFT, and ORBIT COSET, are all equivalent or reducible to HIDDEN SUBGROUP. Then we study the relationship between the decision version and search version of HIDDEN SUBGROUP over various group classes. We show that the two versions are polynomial-time equivalent over permutation groups, and over dihedral groups given the order of the group is smooth. Finally, we give nonadaptive program checkers for HIDDEN SUBGROUP and its decision version.

International Journal of Foundations of Computer ScienceDec 1, 20132 citations

Quantum factoring, discrete logarithms, and the hidden subgroup problem

Richard Jozsa

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.

arXiv:quant-ph/0012084Computing in Science & EngineeringJan 1, 2001121 citations

Algorithms for Quantum Branching Programs Based on Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

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.

arXiv:0911.2317Electronic Proceedings in Theoretical Computer ScienceNov 15, 200929 citations

The Hidden Subgroup Problem for Universal Algebras

Matthew Moore, Taylor Walenczyk

The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.

arXiv:2001.11298ACM/IEEE Symposium on Logic in Computer Science (LICS)May 26, 20200 citations