4
$\begingroup$

I often see Simon's algorithm with two $n$-ary measurement gates for the two computations (Hadamard in upper part, $f$ in lower part). For example, this image

Quantum circuit for Simon's algorithm

taken from wikipedia. In the same article, the explanation states that the state immediatly before the measurement is $$ \sum_{y \in \{0,1\}^n} \left( \lvert y \rangle \otimes \left( \frac{1}{2^n} \sum_{x \in \{0,1\}^n} ((-1)^{x\cdot y} \lvert f(x) \rangle ) \right) \right) $$ and the article proceeds to evaluate $\left( \frac{1}{2^n} \sum_{x \in \{0,1\}^n} ((-1)^{x\cdot y} \lvert f(x) \rangle ) \right)$ to determine the probability of measuring one particular value for $y$.

I am wondering, the evaluation seems to imply that the second measurement, i.e., on the bottom wire, is actually superfluous. In fact, what I am wondering is that I suspect it would be rather dumb to do it that way, because then we have to take care of the probability to measure one particular value of $f(x)$, i.e., a combined state $\lvert y \rangle \otimes \lvert f(x) \rangle$, where we have $2^n$ ($s$ is zero) or $2^{n-1}$ ($s$ is non-zero) different values for $f(x)$. And doing so, i.e., reading out $f(x)$ would give us a rather high chance to measure two values for $y$ in a row (which we want to avoid, as at the end we want to have $n-1$ independent values $y$) as many different values of $f(x)$ share the same $y$ value in the first register.

Am I correct? And if so, why the second measurement gate then? Is there any reason?

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, the measurements on the ancillary qubits are unnecessary. You can just discard those qubits instead of measuring them.

$\endgroup$
7
  • $\begingroup$ Ok. Thank you. And is it right that measuring them would actually yield a much more inefficient implementation? $\endgroup$
    – StefanH
    Jan 1 at 20:28
  • $\begingroup$ @StefanH No, measurement isn't expensive and the oracle evaluations are very expensive so it has little impact on efficiency. You could get a small speedup in the oracle evaluation by substituting the last Toffoli targeting each ancilla with an X basis measurement + classically controlled CZ (which will ruin the ancilla but you were discarding it anyways so it's fine). But that will be negligible compared to the cost of the rest of the circuit. $\endgroup$ Jan 1 at 20:30
  • $\begingroup$ Sorry, still a beginner here. But what I was asking more specifically, if I measure each wire I get a state $\lvert y \rangle \otimes \lvert f(x) \rangle$ at the end with probabilty $1/2^{n-1} 1/2^{n-1}$ ($s$ non-zero). However, I am only interested in the $y$'s and with measuring $f(x)$ I might get two times the same $y$ with probability $2^{n-1}$ if I measure the whole state. But if I only measure $y$, I get a single $y$ with probability $1/2^{n-1}$. Is this not an improvement "probablity-wise"? Is it clear what I am asking... $\endgroup$
    – StefanH
    Jan 1 at 20:37
  • $\begingroup$ @StefanH Performing a demolition measurement of a qubit and ignoring the measurement result is always equivalent to just discarding the qubit and not measuring it. The circuits have identical statistics. So no, it can't be an improvement. You have to actually use the measurement information for it to affect the success probability of the algorithm. Otherwise you'd violate the no communication theorem. $\endgroup$ Jan 1 at 21:04
  • $\begingroup$ So then, what is the problem with the reasoning that I have to make more calls to the procedure if I measure $f(x)$? $\endgroup$
    – StefanH
    Jan 1 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.