Query complexity of generalized Simon's problem

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric c...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2021-12, Vol.281, p.104790, Article 104790
Main Authors: Ye, Zekun, Huang, Yunqi, Li, Lvzhou, Wang, Yuyi
Format: Article
Language:English
Subjects:
Group theory
Quantum computing
Query complexity
Simon's problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP(p,n,k), is a natural extension of Simon's problem: Given a function f:Zpn→X where X is a finite set and the promise that for any x,y∈Zpn,f(x)=f(y) iff x−y∈S for a subgroup S≤Zpn of rank k
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104790