2
$\begingroup$

As a practice exercise, I am trying to factor $N=14$ using Shor's algorithm. My initial guess is $a = 5$, and I need a quantum circuit $U$ for:

$U\vert y \rangle = \vert 5 \cdot y ~{\rm mod}~ 14 \rangle$ for $y=1, 2, \cdots, 13$, i.e. for $y=0001, 0010, ... , 1101$. The modular arithmetic yields the table:

01 0001 0011
02 0010 0110
03 0011 1001
04 0100 1100
05 0101 0001
06 0110 0100
07 0111 0111
08 1000 1010
09 1001 1101
10 1010 0010
11 1011 0101
12 1100 1000
13 1101 1011

The qiskit examples give a circuit for $N=15$, and I was able to find a similar circuit for factoring $N=6$ by trial and error. $U\vert y \rangle = \vert 5 \cdot y ~{\rm mod}~ 6 \rangle$ is reproduced by:

enter image description here

Clearly, trial and error isn't going to work for $N=14$. Is there a systematic method that will provide the circuit I am looking for?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ please delete the duplicate from crypto.stackexchange, I doubt anyone will answer there. this is the right place. $\endgroup$
    – kodlu
    Nov 13, 2022 at 16:10

2 Answers 2

Reset to default
5
$\begingroup$

Shor's algorithm does not apply to even numbers.

(Nor to prime powers. There is a reason why it was first demonstrated for N=15: It is the smallest number it can be applied to.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ahh. I had not appreciated that. $\endgroup$
    – Robert Singleton
    Nov 14, 2022 at 22:10
  • 2
    $\begingroup$ ... see also my edit. Next should be 21. $\endgroup$
    – Norbert Schuch
    Nov 14, 2022 at 22:10
3
$\begingroup$

The class algorithms.factorizes.Shor contains a "private" method _power_mod_N that does what you want. The result isn't pretty, but it does the job.

Alternatively, if you just want to play with a simulator, you might want to look at quirk. It includes $B^A mod R$ as a built-in gate.

Answering question below:

from qiskit.algorithms.factorizers.shor import Shor
from qiskit import QuantumCircuit

power = Shor()._power_mod_N(n=4, N=14, a=3)
qc = QuantumCircuit(power.num_qubits)
qc.append(power, range(power.num_qubits))
qc.decompose().draw()

The value n is $\log_2(N)$, N is the number you are factoring, and a is the value you're raising to the exponent. For N=14, this generates code with 12 qubits. It's really ugly! Use quirk.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for the suggestion. I'll take a look at _power_mod_N. My primary motivation is to build my own version of $a^x ~{\rm mod}~ N$ for general $a$ and $N$. $\endgroup$
    – Robert Singleton
    Nov 13, 2022 at 22:23
  • $\begingroup$ from algorithms.factorizes.Shor import _power_mod_N didn't work. How should I import this private method? $\endgroup$
    – Robert Singleton
    Nov 13, 2022 at 23:24
  • 1
    $\begingroup$ @RobertSingleton. See above $\endgroup$
    – Frank Yellin
    Nov 14, 2022 at 5:37
  • $\begingroup$ Thanks for your useful example! $\endgroup$
    – Robert Singleton
    Nov 14, 2022 at 12:57
  • 1
    $\begingroup$ Quirk does not (yet)? have a method to extract the gates. Its design goal (according to Gitney's blog) was to provide immediate and continuous user feedback. As such, everything internally is either an operator matrix or a permutation (when the entries in the operator matrix are all 0's and 1's). It doesn't transpile to gates. So, for example, with Shor's algorithm, you get a good idea of how the algorithm works by assuming that $A^x(mod N)$ exists as a gate, and not caring how such a gate would be implemented. Sorry if you actually need to build the circuit and I misled you. $\endgroup$
    – Frank Yellin
    Nov 18, 2022 at 17:48

Your Answer

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

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