Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [simons-algorithm]

For questions regarding the famous Simon's algorithm which solves Simon's problem exponentially faster than any deterministic or probabilistic classical algorithm, requiring exponentially less computational power than the best classical probabilistic algorithm.

5
votes
1answer
70 views

What is the hidden subgroup in Simon's problem?

Given access to an oracle for a function $f:\{0,1\}^n\to\{0,1\}^n$ such that $f(x)=f(y)$ iff $x\oplus y\in\{0,s\}$, Simon's algorithm allows to recover $s$ in $\mathcal O(n)$ queries to the oracle. ...
4
votes
2answers
56 views

Simon's Algorithm - Probability that the measurement results in a string Y

I found something in a lecture on Simon's algorithm that I do not quite understand how to interpret. There the following is said: $$\sum_{y\in\{0,1\}^n}|y\rangle\left(\sum_{x\in\{0,1\}^n} (-1)^{x\...
3
votes
1answer
305 views

In Simon's algorithm, why is $f$ one-to-one if (and only if) $s=0^n$?

I'm dealing with Simon's algorithm a bit and "stumbled" upon something called for the algorithm. It is said that if the period is $s = 0^n$, then it is an injective function, that is, a 1 to 1 ...
3
votes
3answers
208 views

Classical complexity for Simon's problem

Simon's problem is that you are given a function $f : \{0,1\}^n \to \{0,1\}^n$ such that $f(x)=f(y)$ if and only if $x \bigoplus y$ is either $0^n$ or some unknown $s$. The problem is to find $s$. If $...
7
votes
1answer
95 views

Simon's algorithm: Number of equations

During the classical pre-processing stage of Simon's algorithm, we repeat the quantum operations $n-1$ times to get $$ \begin{alignat}{7} y_{1} \cdot s & \phantom{\vdots} =~ && 0 \\ y_{2} ...
4
votes
1answer
76 views

Simon's Algorithm Probability of Independence

In this pdf for the Simon's algorithm we need $n-1$ independent $\mathbf y$ such that: $$ \mathbf y \cdot \mathbf s=0$$ to find $\mathbf s$. On page 6 of the pdf the author writes that the probability ...
7
votes
2answers
245 views

Clarification needed regarding quantum “black-box” circuits

$\newcommand{\Ket}[1]{\left|#1\right>}$ I understand that in general quantum black box algorithms (such as the ones which play a part in Simon's & Deutsch's algorithm) implement a quantum ...
8
votes
2answers
140 views

Use of the term “dimension” in this description of Simon's algorithm?

In Kaye, Laflamme and Mosca (2007) pg106 they write the following (in the context of Simon's algorithm): ...where $S=\{\mathbf{0},\mathbf{s}\}$ is a $2$-dimensional vector space spanned by $\mathbf{...
6
votes
1answer
541 views

How exactly does Simon's algorithm solve the Simon's problem?

Problem Statement: We are given a $2-1$ function $f:\{0,1\}^{n}\to\{0,1\}^{n}$ such that: there is a secret string $s\in\{0,1\}^{n}$ such that: $f(x)=f(x\oplus s)$. Challenge: find $s$. Simon's ...