Is there an example of Shor's algorithm for the discrete log problem with concrete numbers anywhere?

Question

I understand the problem well enough and I'm trying to understand the algorithm, Shor's version. It's not easy to read the abstract descriptions available everywhere --- Shor's paper, Nielsen's book and many others. I will build a numerical example --- various numerical examples --- if none are available out there, but if you know any that will be a nice start.

If you don't know any, feel free to give me directions on how to build it. For instance, I have already understood that a key step to the algorithm is setting up two registers |a>|b> and then applying a circuit that takes |$a$>|$b$> to |$y\oplus g^a x^{-b}$>, where $g$ is a generator and $x$ is the number whose logarithm we want to find. (The computation is be reduced mod $p$.) (Of course, $y$ is to be initialized to zero.)

The next step is to compute the QFT, something I've never done and looks a bit difficult, so I will consider the previous step a mile stone for now. I think that at the previous step I will have a superposition of all possible values of the pair $(a,b)$ and so the QFT would only serve to amplify the states that are interesting.

As you can see, more than examples, I'm looking for careful steps and explanations. I'll appreciate any help on this.

Answer 1

Classiq's library has an example of the full algorithm including the circuit creation and post processing.

Here you can find a basic example of a vanilla case, where the order is a power of 2:

from classiq import *
from classiq.qmod.symbolic import log, ceiling

MODULU_NUM = 5
G_GENERATOR = 3
X_LOGARITHM = 2
ORDER = 4

@qfunc
def discrete_log_oracle(
    g_generator: CInt,
    x_element: CInt,
    N_modulus: CInt,
    order: CInt,
    x1: QArray[QBit],
    x2: QArray[QBit],
    func_res: Output[QArray[QBit]],
) -> None:

    allocate(ceiling(log(N_modulus, 2)), func_res)

    inplace_prepare_int(1, func_res)
    modular_exp(N_modulus, x_element, func_res, x1)
    modular_exp(N_modulus, g_generator, func_res, x2)

@qfunc
def discrete_log(
    g: CInt,
    x: CInt,
    N: CInt,
    order: CInt,
    x1: Output[QArray[QBit]],
    x2: Output[QArray[QBit]],
    func_res: Output[QArray[QBit]],
) -> None:
    reg_len = ceiling(log(order, 2))
    allocate(reg_len, x1)
    allocate(reg_len, x2)

    hadamard_transform(x1)
    hadamard_transform(x2)

    discrete_log_oracle(g, x, N, order, x1, x2, func_res)

    invert(lambda: qft(x1))
    invert(lambda: qft(x2))

@qfunc
def main(
    x1: Output[QNum],
    x2: Output[QNum],
    func_res: Output[QNum],
) -> None:
    discrete_log(G_GENERATOR, X_LOGARITHM, MODULU_NUM, ORDER, x1, x2, func_res)

qmod = create_model(main, constraints=Constraints(max_width=13))
qprog = synthesize(qmod)
show(qprog)

Disclaimer - I am a Classiq employee