9 votes

Classical complexity for Simon's problem

To determine the classical complexity of a problem you need two things, of course: an upper bound (generally an algorithm) and a lower bound. There is an easy randomized algorithm that works with ...
John Watrous's user avatar
  • 5,887
8 votes
Accepted

How could one implement a circuit using Grover's algorithm to solve a linear system of equations?

You certainly could use Grover's search. You would create 2 registers. This first, of 3 qubits, would effectively store the $\{s_0,s_1,s_2\}$. This is the standard register for Grovers on which you ...
DaftWullie's user avatar
8 votes
Accepted

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

$$ \newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\...
DaftWullie's user avatar
7 votes
Accepted

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

Note: $I_k$ is unit matrix and $O_k$ is the zero matrix of order $k$ in the following text. First step of the algorithm is $H \otimes H \otimes I_2 \otimes I_2$ as you mentioned. A controlled gate $...
Martin Vesely's user avatar
6 votes
Accepted

What is the hidden subgroup in Simon's problem?

To see that Simon's program is an instance of an (abelian) hidden subgroup problem, we have to identify the group $G$, the subgroup $H$, the set $X$ and the function $f : G \rightarrow X$. Note first ...
MartinQuantum's user avatar
6 votes
Accepted

What is the intuition behind uniform Hadamard superposition?

The first Hadamard gates applied to a fiducial all-zero's ket on $n$ qubits serve to prepare your input register into the uniform superposition over all $2^n$ basis states. The last Hadamard gates ...
Mark Spinelli's user avatar
5 votes
Accepted

Simon's algorithm: Number of equations

Imagine for a moment that $y_1,\ldots,y_{n-1}$ are linearly independent vectors in $\mathbb{R}^n$. There would then be a one-dimension subspace of vectors $s$ satisfying the $n-1$ equations you listed....
John Watrous's user avatar
  • 5,887
5 votes
Accepted

How to come up with Simon's Algorithm circuit for this 3 qubit system? (given truth table & s)

I'm not saying this is a good way of doing it, but if you're completely stumped, there is always a fallback: use a multi-controlled-not. For example, if you use controlled-controlled-controlled-not, ...
DaftWullie's user avatar
4 votes
Accepted

Simon's Algorithm Probability of Independence

At first glance, the formula looks lightly wrong: the last term in the should only be $(1-2^{n-2}/N(s))$, giving $$ P_{ind}=\prod_{k=1}^{n-1}\left(1-\frac{2^{k-1}}{N(s)}\right) $$ overall. Thus every ...
DaftWullie's user avatar
4 votes
Accepted

Clarification needed regarding quantum "black-box" circuits

$$\newcommand{\Bra}[1]{\left<#1\right|}\newcommand{\Ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$ ...
kludg's user avatar
  • 3,204
4 votes

Clarification needed regarding quantum "black-box" circuits

Nice question. Your second example is correct. I will show this by using Equation 2 from here: $(A + B)\otimes C = A\otimes C + B\otimes C$. For your example: $\left(\frac{|0\rangle+|1\rangle}{\...
user1271772 No more free time's user avatar
4 votes
Accepted

Coding an oracle for Simon's algorithm

You could do something like: assume the most significant bit of $s$ is 1. write a function that says "if the most significant bit of $x$ is 0, return $x$. if the most significant bit of $x$ is 1, ...
DaftWullie's user avatar
4 votes
Accepted

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

Assuming $x$ is $n$ bits, here's a simple procedure: take $n$ ancilla qubits, all prepared in $|0\rangle$. Do a transversal controlled-not (i.e. bit by bit controlled-not) from the register with $|x\...
DaftWullie's user avatar
4 votes
Accepted

Is the measurement of the second register in Simon's algorithm superfluous?

Yes, the measurements on the ancillary qubits are unnecessary. You can just discard those qubits instead of measuring them.
Craig Gidney's user avatar
4 votes
Accepted

How is the factorization of the XOR operator done?

$(-1)^1 = (-1)^3$, so the operation in your question is in the sense of modulo 2, hence $r\cdot y+s\cdot y=(r\oplus s)\cdot y$. Examples to show things I've said just now. $r = (1,0,1),s=(0,0,1),y=(1,...
narip's user avatar
  • 2,984
3 votes

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

As mentioned above there is nothing called "Oracle free" algorithm. Let's put this in simple words: Consider we are making a problem solving algorithm to solve the roots of a quadratic ...
Geomon Joshy's user avatar
3 votes
Accepted

Why is the function operator used in Simon's algorithm unitary?

The easiest way to prove this is to apply the operator twice $$ |x\rangle|a\rangle\mapsto |x\rangle|a\oplus f(x)\rangle\mapsto |x\rangle|a\oplus f(x)\oplus f(x)\rangle=|x\rangle|a\rangle. $$ So, two ...
DaftWullie's user avatar
3 votes
Accepted

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?

With the Hidden Subgroup Problem, abelian or otherwise, we have a function $f$ from elements of $g\in G$ to an arbitrary set $X$, that is constant on cosets of $H\le G$ and is distinct on different ...
Mark Spinelli's user avatar
3 votes
Accepted

N-Qubit Hadamard vs Quantum Fourier Transform

As you pointed out correctly, both $H^{\otimes n}$ and QFT applied on input state $|0\rangle^{\otimes n}$ return state $$ |\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n}|i\rangle. $$ There is no ...
Martin Vesely's user avatar
3 votes
Accepted

Simon's algorithm -- circuit for given s

Remember that we're not told what function $f$ is being implemented by this circuit, it is simply claimed that $f(x)=f(y)$ if and only if $y=x$ or $x\oplus 11=\bar{x}$. So, we need to identify what ...
DaftWullie's user avatar
3 votes

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

This is basically the definition of the type of function that you apply Simon's algorithm to. You are required to have a function $f(x)$ such that $$ f(x)=f(y) $$ if and only if $x\oplus y=0$ or $s$. ...
DaftWullie's user avatar
3 votes
Accepted

Implementing a Gaussian elimination solver for Simon's algorithm's outcome of linear equations

Note that the $00$ measurement is actually unusable: any string $s$ is orthogonal to $00$, so this doesn't give you a bit of informration on $s$. Furthermore, as noted in this answer, for a secret of $...
Tristan Nemoz's user avatar
  • 6,162
2 votes

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

In order to represent a '$\mathbf 0$' state as a vector in a Hilbert space, the '$\mathbf 0$' vector must in fact be non-zero. Thus, the label '$\mathbf 0$' is just a label for some designated vector (...
JSQuareD's user avatar
  • 121
2 votes

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

The first state in your question is not a valid quantum state as it is not normalized. The result comes directly from the axioms of quantum mechanics. You just have to apply the Born rule. For a ...
biryani's user avatar
  • 966
2 votes

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

Measurements are only allowed at the end of the quantum circuit for current machines like those of IBM. Also for Simon's algorithm we don't care about the output of the second register. Thus only ...
KAJ226's user avatar
  • 13.8k
2 votes
Accepted

Simon's Algorithm: Calculating the effects on the second Hadamard gate and the resulting amplitudes

Your mistake happens at the step "we write the sum as one", the normalization term ought to be $\dfrac{1}{\sqrt{2}\sqrt{2^n}}=\dfrac{1}{\sqrt{2^{n+1}}}$, not $\dfrac{1}{\sqrt{2^{n-1}}}$. ...
Tristan Nemoz's user avatar
  • 6,162
2 votes
Accepted

Is the blackbox already a reversible operator, or are we the ones that convert it into one?

From the algorithm's point of view (for any oracle-based algorithm) it needs the oracle to be a black box that implements the function reversibly, so that it can just be plugged in the rest of the ...
Mariia Mykhailova's user avatar
2 votes

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

Remember that $f$ must satisfy Simon's promise: $$\forall (x,y),f(x)=f(y)\implies \begin{cases}y\\s\oplus y\end{cases}$$ Thus there are two cases: Either $s=0$, in which case $f$ is injective Or $s\...
Tristan Nemoz's user avatar
  • 6,162
2 votes

Simon's algorithm circuit with hidden oracle

Yes, that's the point of the algorithm to figure out using the measurements one got! An important information though is the size of the registers you're dealing with, or whether you only measured the ...
Tristan Nemoz's user avatar
  • 6,162
2 votes

Why do black box separations imply oracle separations?

Oracle separations and black-box separations are effectively synonymous. Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible