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

Lecture notes in computer science

A Quantum Polynomial Time Algorithm in Worst Case for Simon’s Problem

Takashi Mihara, Shao Chin Sung

Published Jan 1, 1998• 4 citations
Publisher
DOI
10.1007/3-540-49381-6_25

Related papers

Deterministic polynomial-time quantum algorithms for Simon?s problem

Takashi Mihara, Shao Chin Sung

Computational Complexity•Dec 1, 2003•14 citations

An exact quantum polynomial-time algorithm for Simon's problem

Gilles Brassard, Peter Høyer

We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.

arXiv:quant-ph/9704027•Israel Symposium on Theory and Computing Systems (ISTCS)•Nov 22, 2002•294 citations

Polynomial Time Quantum Algorithm for Search Problem and Its Application

Satoshi Iriyama, Masanori Ohya

Lecture notes in computer science•Jan 1, 2014•0 citations

Hidden Subhypergroup Problem

Massoud Amini, Mehrdad Kalantar, Mahmood M. Roozbehani

The Hidden Subgroup Problem is used in many quantum algorithms such as Simon's algorithm and Shor's factoring and discrete log algorithms. A polynomial time solution is known in case of abelian groups, and normal subgroups of arbitrary finite groups. The general case is still open. An efficient solution of the problem for symmetric group $S_n$ would give rise to an efficient quantum algorithm for Graph Isomorphism Problem. We formulate a hidden sub-hypergroup problem for finite hypergroups and solve it for finite commutative hypergroups. The given algorithm is efficient if the corresponding QFT could be calculated efficiently.

arXiv:quant-ph/0609220•Sep 28, 2006•5 citations

Some Quantum Algorithms

Vicente Moret‐Bonillo

Springer eBooks•Jan 1, 2017•1 citation

Constant-time solution to Simon's decision problem with the known subgroup range in quantum computer

Chien-Yuan Chen, Chih-Cheng Hsueh

Simon's algorithm can determine whether the function f is bijective or periodic by using the polynomial-function evaluations. Simon's algorithm is more efficient than classical algorithms which require exponential function evaluations. In this paper, we assume that the range of the periodic function is a known subgroup. We further find an integer b orthogonal to the range. According to b, we can construct a quantum algorithm to determine whether f is bijective or periodic in only one function evaluation.

Computational intelligence•Jul 2, 2007•0 citations
We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.
The Hidden Subgroup Problem is used in many quantum algorithms such as Simon's algorithm and Shor's factoring and discrete log algorithms. A polynomial time solution is known in case of abelian groups, and normal subgroups of arbitrary finite groups. The general case is still open. An efficient solution of the problem for symmetric group SnS_nSn​ would give rise to an efficient quantum algorithm for Graph Isomorphism Problem. We formulate a hidden sub-hypergroup problem for finite hypergroups and solve it for finite commutative hypergroups. The given algorithm is efficient if the corresponding QFT could be calculated efficiently.
Simon's algorithm can determine whether the function f is bijective or periodic by using the polynomial-function evaluations. Simon's algorithm is more efficient than classical algorithms which require exponential function evaluations. In this paper, we assume that the range of the periodic function is a known subgroup. We further find an integer b orthogonal to the range. According to b, we can construct a quantum algorithm to determine whether f is bijective or periodic in only one function evaluation.