I'm currently investigating Shor's algorithm and especially Smolin's variant, that he described in his article: https://arxiv.org/abs/1301.7007

My applied changes according to Smolin's variant are here: https://github.com/Sage-Cat/quantum_shors_algorithm

The paper I read you can find in repository docs/Smolin_pretending_large_numbers.pdf.

To be concise, he suggests to make this changes:

  1. Find a, such as a^2 = 1 mod N, using Extended Euclidean Algorithm
  2. Set period r = 2
  3. And somehow use 2 qubits to simulate finding a and r or smth. (I don't understand the actual use of 2 qubits). From his paper I got only that he uses 2 qubits to get specific CNOT entanglement like this:
    operation ValidateAUsingQuantumSubroutine(a : Int, N : Int, r : Int) : Result {
        use qubits = Qubit[2];
        // Prepare qubits
        CNOT(qubits[0], qubits[1]);

        // Measurement could be used to validate assumptions or effects
        let measurement = M(qubits[0]);

        return measurement;

But how it helps to validate a, I don't understand.


1 Answer 1


The thing to understand is that the quadratic residue $a$, that Smolin is getting you to compute, is exactly the same $a$ that Shor's algorithm is finding by using period-finding against a random base $g$. When you set $g=a$, you get a vacuous execution of Shor's algorithm where it computes that this $g$'s period is 2, and returns $g^{2/2} = \text{...drumroll...} = a$ as the quadratic residue to use for factoring.

So the first cheat is knowing the value you're trying to find. The second cheat is using the fact that you know the period of $f(x) = g^x$ is 2, and therefore Shor's algorithm will still work if you substitute this complicated $f$ with some trivial period-2 function like bit-flipping. So you do that. And also you reduce your phase estimation register size from $2n$ to 1, since that's sufficient for period 2. Thus the whole quantum part degenerates into a CNOT gate conjugated by Hadamard gates on its control.

These cheats are cheating. But that was the intent of the paper. It's a reaction to papers that claim to factor numbers with quantum computers by using subtler cheats.

  • $\begingroup$ So Smolin is simply saying that there is no real use for such "oversimplified" algorithms, except for educational purposes? And that such "simplifications" speedup nothing? $\endgroup$
    – SageCat
    Feb 15 at 12:49
  • 1
    $\begingroup$ @SageCat Yes, that they speedup nothing of importance. $\endgroup$ Feb 15 at 17:46

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.