0
$\begingroup$

Let's look at quantum subroutine of Shor's algorithm:

enter image description here

  1. Hadamard gates create superposition of all (exponential number) values for input qubits.
  2. Then we perform a classical function on them, which is here: $f(a) = y^a \textrm{ mod } N$, where $N$ is the number we would like to factorize, $y<N$ is some chosen (usually random) number.
  3. Then we perform measurement of value of this function $f(a)=m$ (random). This measurement restricts the original ensemble to only input values $a$, such that $f(a)=m$.
  4. Mathematics says that this restricted ensemble has to be periodic, this period can be concluded from value of (quantum) Fourier transform, and allows to conclude the factors.

So generally we branch calculations, get the final outcome from the first branch (input qubits), but treatment of other branches seems also crucial to make the algorithm work - including "uncomputing" of auxiliary qubits.

Imagine Bob has access to implementation of Shor's algorithm, but it is leaky - like in the yellow box above, value and auxiliary qubits finally get to Eve.

A natural question is if Eve can cripple Bob's computation? For example allowing him or not to break RSA cipher. If she could, she could also delay this choice.

As uncomputing or not requires input qubits, it seems tough to cripple calculations through auxiliary qubits alone (?)

However, there is Walborn's "Double-slit quantum erasure" experiment (nice explanation), where rotating polarizer for one of entangled photons, we erase or not which-slit information for the second photon - deciding between classical and interfering statistics for this double-slit.

So maybe Eve could erase information from value qubits, e.g. by putting Hadamard gates before measuring these qubits? This way their measurement would no longer restrict to fixed value of classical function, crippling calculations?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Here from an eagles eye perspective:

No matter what Eve does will lead to a measurable difference in Bobs states, otherwise superluminal communication would be possible. Does Bob need to use (perform measurement on them, or let them directly interact with his qubits) the qubits which are at Eves? If yes then of course she can cripple Bob algorirhm by just throwing them away, or.measuring them.and not telling Bob the result. If no, then Bob can.just continue and he will get the same results no matter what she does.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Bob uses only outcome of measuring input bits for factorization. Please take a look at Walborn's delayed choice - literally rotating polarizer on one arm, changes statistics on the second arm. However, sending information back in time is impossible due to requirement of coincident counter ... so erasing information in one arm of Shor shouldn't fundamentally forbid changing behavior on another arm (?), but there should be some deeper reason forbidding sending information this way (?) $\endgroup$
    – Jarek Duda
    Commented May 9, 2018 at 7:45
  • $\begingroup$ @JarekDuda I had a look, and I dont know what the difficulty.is. One always has to.keep in mind that the.eraser experiments require coincidence measurements between the states. Then.interesting.results are possible. In case eve has one of the.states and doesnt wanr to tell her outcome no.special filtering on bobs side is.possible (because.he.doesnt.have eves.info), so all the local states/measuremnts are the.same.to him even if eve.does.whatever.locally on her system. (Sry.for.the periods, next time I buy a better mobile) $\endgroup$
    – lalala
    Commented May 9, 2018 at 11:59
2
$\begingroup$

Imagine [...] auxiliary qubits [leak] to Eve. [Can she] cripple Bob's computation?

No. This is guaranteed by the no-communication theorem. If Eve's measurements could affect whether Bob succeeded or not at finding factors, this would allow for a faster-than-light communication mechanism.

However, there is Walborn's "Double-slit quantum erasure" experiment (nice explanation), where rotating polarizer for one of entangled photons, we erase or not which-slit information for the second photon - deciding between classical and interfering statistics for this double-slit.

If you actually do an eraser experiments, with Eve deciding whether or not to rotate a polarizer in an attempt to control the pattern that Bob sees, you will find that it doesn't work. At least not the way you think. Bob will always see no interference pattern.

The interference pattern only comes out later, in the analysis, when you use Eve's measurement results to group Bob's measurements. Bob has to be told what Eve's measurement results were in order to recover the interference patterns (or lack thereof) that are in the correlations between their two data sets.

In the factoring scenario, this would be a bit like Eve telling Bob which runs he's allowed to use and which he has to throw away. She may be able to use the ancillae to predict which runs are bad at a rate better than chance.

For example, if Eve performs a QFT on the ancillae then measures them and gets the result 0000...00, then she can confidently say that Bob's attempt to factor the number failed / will fail. But she's not controlling anything, she's using measurement results to infer related information.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Imagine Eve has two options: 1) just measure value qubits, 2) Use Hadamard gates on all value qubits, then measure them. In the second case we have no longer restriction on input qubits - all {0,...,2^n-1} of them are possible with the same amplitude - DFT should return period 1 - do you agree? $\endgroup$
    – Jarek Duda
    Commented May 10, 2018 at 7:10
  • $\begingroup$ @JarekDuda No, I don't agree. Bob's expected measurements are the same in both the first and second case. You're assuming erasure can be applied unilaterally by Eve, but erasure always requires applying fixup operations back into the original system (or during the analysis) and in your scenario Eve is not doing this (since it requires Bob's cooperation). $\endgroup$
    – Craig Gidney
    Commented May 10, 2018 at 9:52
  • $\begingroup$ In Walborn's delayed choice, Bob measures statistics for double slits ("interference minimum allows to break cipher"), Eve rotates or not polarizer - not asking for Bob's cooperation. It requires coincidence-counter, here causality cones of Bob and Eve will finally meet: entire world acts as this coincidence counter. Writing in quantum formalism Shor situation, using Hadamar gates on value qubits and measuring them, seems to make that classical function meaningless here (?) $\endgroup$
    – Jarek Duda
    Commented May 10, 2018 at 10:06
  • $\begingroup$ @JarekDuda Go do a simulation of the delayed choice experiment and see what happens from Bob's perspective. Eve's choices only make a difference if you condition on her measurement results, and that just doesn't make sense in a "sneaky adversary" context. $\endgroup$
    – Craig Gidney
    Commented May 10, 2018 at 15:57
  • 1
    $\begingroup$ @JarekDuda Basically, you have corrected identified a contradiction between what you believe about delayed erasure and Shor's algorithm. But the problem isn't with Shor as you seem to be assuming; it's that you have fundamentally misunderstood what happens during delayed erasure. You should ask a question focused on that misconception. $\endgroup$
    – Craig Gidney
    Commented May 10, 2018 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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