# 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.

48 questions
Filter by
Sorted by
Tagged with
188 views

### Wong's "Introduction to Classical and Quantum Computing" Exercise 7.20

I am currently working my way through "Introduction to Classical and Quantum Computing" by Thomas Wong. I am trying to solve the following problem on Simon's Algorithm: Exercise 7.20. You ...
• 81
53 views

### How many oracles can satisfy a solution of Simons problem?

I know that the f/oracles in Simons algorithm is 2-1, and that $f(x)=f(y)\iff y=x\oplus s$. My question is if we can have gave different oracles/functions, that has the same codomain/output for a ...
264 views

### Prove that there is no polynomial size quantum algorithm for a Simon's problem with no promise on the input

We look at the following variant of Simon's problem. There is an algorithm $A$ that solves a problem with the following settings: The input is an oracle $f:\{0,1\}^n \to [M]$. The output of the ...
• 239
42 views

### Grover meets Anyone - feasibility

Recently, a variety of algorithms have been proposed to combine Grover algorithm with other quantum algorithms. As an example, given a function $f: \{0, 1\}^n\mapsto \{0,1\}$, the Grover meet Simon ...
• 548
349 views

### What is the intuition behind uniform Hadamard superposition?

I noticed that in many quantum algorithms, you apply a layer of uniform Hadamard transformation before and after the operations in between. For example, Deutsch-Josza, Simon's, and Grover's search. ...
• 267
40 views

• 11
1 vote
68 views

• 21
452 views

### Simon's algorithm for a function $f: \{0,1\}^m \mapsto \{0,1\}^m$, $n > m$

Usually Simon's algorithm is defined for function $f: \{0,1\}^n \mapsto \{0,1\}^n$. Can Simon's algorithm still be applied to function of the form $f: \{0,1\}^n \mapsto \{0,1\}^m$, where $n > m$? ...
831 views

### Solving modified version of Simon's Algorithm with multiple secret strings

I am stuck on the following question. Let $S$ be the $span${s1, s2, ... , sk} such that $S$ is a $k$-dimensional subspace of {0, 1}n. Let 𝑓:{0,1}𝑛→{0,1}𝑛 be a function so that $f(x) = f(y)$ if ...
1 vote
175 views

217 views

### In the hidden subgroup problem for finite Abelian groups, where does the state $\frac{1}{\sqrt{|G|}}\sum_{g\in G} |g,0\rangle$ come from?

I am new to the concept of HSP. Previously, I saw how to solve hidden subgroup problem over $\mathbb{Z}_2^n$, which was Simon's algorithm. Over there the first step was to apply $H^{\otimes n}$, which ...
• 227
110 views

### How can I solve Simon's problem for the projection function $f(x_0,x_1)=x_0$?

I am having issues solving Simon's problem for a projection function. The function $f: \{0,1\}^2 \mapsto \{0,1\}$ defined as $f(x_0,x_1) = x_0$ returns the least significant bit of its argument. How ...
• 21
1k views

### In Simon's algorithm, is there a general method to define an oracle given a certain periodicity?

I have to implement Simon's algorithm in Cirq. I have problems determining the oracle $f(x)$ defined such that $f(x)=f(x\oplus a)$ from a certain value of $a$. Given a random $a$, is there a general ...
• 153
424 views

### A Simon's algorithm with secret string b = 01, IBM Quantum experience gives a different result from what I calculate

I try to design the circuit for $b = 11$ and succeeded in running. Therefore, I start to think of the circuit for different secret string $b = 01$. The circuit I made is down below: Here is the ...
• 61
368 views

### N-Qubit Hadamard vs Quantum Fourier Transform

Both Simon's algorithm and the algorithm for period finding begin by placing qubits in the equal superposition state, but Simon's algorithm uses the n-qubit Hadamard $H^{\otimes n}$ while the period ...
411 views

### Simon's algorithm -- circuit for given s

I'm currently learning Simon's algorithm, from IBM Quantum Experiene. For the given string $s=11$, they display the implemented function $Q_f$ like this: Can someone explain to me, why the CNOT gates ...
• 107
2k views

### How to interpret a 4 qubit quantum circuit as a matrix?

This is part of Simon Algorithm (Initial state + some Oracle function) There is a post that explains how to interpret circuits (How to interpret a quantum circuit as a matrix?), but I'm not sure how ...
1 vote
110 views

### Simon's algorithm example [duplicate]

I am trying to wrap my head around Simon's algorithm and I am trying to solve a question. This is the solution that I have come up with. Please correct me if I am wrong.
68 views

### Simon's Algorithm - How to simulate second Hadamard operation on first register?

I am implementing a simulation of Simon's Algorithm, and am at the part of applying the second n-qbit Hadamard transformation, $H^{\otimes n}$, to the first of the two n-qbit registers, leaving the ...
• 123
311 views

### What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
• 1,393
1k views

### Coding an oracle for Simon's algorithm

I am trying to implement Simon's algorithm which calls for a 2-to-1 mapping function that satisfies $f(x) = f(x⊕s)$. I am looking for a simple way to code the oracle (using $H$, $Cx$, and $R$ gates), ...
755 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. ...
• 26.2k
198 views

• 1,393
442 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 ...
547 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 ...
• 185