Modular Arithmetic Libraries

[dfinder]

What should we add?

As part of a quantum computing project for trying to implement Shor's algorithm against a 3 digit number, I ended up implementing https://arxiv.org/pdf/2112.10537 in Qiskit by converting the example code/pennylane code into qiskit. Would this be good to add?

[alexanderivrii]

Thanks @dfinder for the suggestion and for your willingness to contribute the code!

I have taken a brief look at the linked paper and it seems that the described synthesis methods form an extension/improvement of what we have in Qiskit already, see https://docs.quantum.ibm.com/api/qiskit/circuit_library for the arithmetic circuit classes that are already supported, and see https://docs.quantum.ibm.com/api/qiskit/transpiler_synthesis_plugins for the available synthesis algorithms for these classes. (Note that while I say "circuit classes", the recommended way is to represent these objects as Gates and not as QuantumCircuits, e.g. one should use ModularAdderGate and not DraperQFTAdder).

Could you please make a list of the existing/new arithmetic gate classes + the corresponding synthesis algorithms that you would be willing to add?

Especially where the new gates are concerned, we have an ongoing discussion in #13571 of which gates should be a part of Qiskit's circuit library. There are many useful gates that we may not want to include in Qiskit itself, yet have them available somewhere in the Qiskit ecosystem. For instance, a possible choice is to implement new gate classes + synthesis methods as a new package within https://github.com/qiskit-community.

One more question, do you have any data on the 2-qubit gate counts / 2-qubit depths for the gates that already exist in Qiskit (i.e. FullAdderGate, ModularAdderGate, MultiplierGate, etc. ) and for which the paper's synthesis methods apply?

[dfinder]

Considering that modular exponentiation is at the heart of some of the most compelling use cases thus far for quantum computing[Cracking RSA and Diffie–Hellman], I found it somewhat fascinating that modular exponentiation wasn't already baked into the system.

I would be willing to add functions that work as follows:
N|> => N+K mod M|>
N|> => N*K mod M|>
N|> => C^N mod M|>, for constant C.

So we have:
With x = ceil(lg(m))
Add K fourier:O(x) with x qubits.
Modular adder in place: 1 work qubit, x normal qubits. 5 add k fouriers, and 4 QFTs, and some flips on the work bit.(2x^2+5x+2)
Multiplication out mod k is 2 QFTs, and a modular adder for each qubit.(3x^3+6x^2+2x), this requires 2x+1 qubits.
Modular Multi in place adds another x qubits.
Modular multi in place uses 2*multiply out+x swaps: 6x^3+12x^2+5x

And then exponentiation is n (modular multiplies, reset the adder).

So modular exponentiation with modulo N uses 6x^4+12x^3+5x^2+1 gates and 3x+1 qubits.

But you wanted the 2-qubit gate decomposition. I am afraid I'll have to use math and get back to you shortly.

Wait, are you asking also for the decomposition numbers for the pre-existing implemented quantum adders/multipliers?

this sounds like a fun research project, I'll get back to you shortly.

[alexanderivrii]

Thank you for clarifying. So the first function N|> => N+K mod M|> is exactly the same as ModularAdderGate, defined as $|a\rangle_n |b\rangle_n \rightarrow |a\rangle_n |(a+b) \mod 2^n\rangle_n $, at least when $M= 2^n$, where $n$ is the number of bits required to represent $a$, $b$ and $a+b\mod 2^n$. In your suggestion, is $M$ always a power of 2? If this is indeed the case, then we already have the relevant gate within Qiskit, and adding a new synthesis method here and make it available via a plugin interface here would be much appreciated.

My question about the data was to just run all the different synthesis methods to compare the number of 2-qubit gates and the 2-qubit depth for the new synthesis method for the ModularAdderGate that you are offering to implement against the synthesis methods that we have already, for example here is the code that I have used to evaluate the existing synthesis methods:

from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import ModularAdderGate
from qiskit.transpiler.passes.synthesis import HLSConfig
from qiskit.transpiler.passes import HighLevelSynthesis

def depth_2q(circ):
    return circ.depth(lambda op: len(op.qubits) == 2 and op.name != "barrier")

def size_2q(circ):
    return circ.size(lambda op: len(op.qubits) == 2 and op.name != "barrier")

configs = [
    ("qft     ", HLSConfig(ModularAdder=["qft_d00"])),
    ("ripple04", HLSConfig(ModularAdder=["ripple_c04"])),
    ("ripple95", HLSConfig(ModularAdder=["ripple_v95"]))
]

for nq in range(1, 10):
    for na in range(5):  # number of available ancilla qubits
        for config in configs:
            adder = ModularAdderGate(nq)
            qc = QuantumCircuit(adder.num_qubits + na)
            qc.append(adder, range(adder.num_qubits))
            qct = HighLevelSynthesis(basis_gates=['cx', 'u'], hls_config=config[1])(qc)
            print(f"nq = {nq}, na = {na}, method = {config[0]}: count = {size_2q(qct)}, depth = {depth_2q(qct)}")

I believe the new synthesis method should offer an advantage but it would be nice to see some concrete numbers (of course, these could be easily worked out from the formulas that you have listed above).

Regarding the two other functions, N|> => N*K mod M|> and N|> => C^N mod M|>, I believe we don't have these in Qiskit (ok, we do have a MultiplierGate, but it's not an in-place multiplier like the one I think you have, and we don't have the exponentiation gate). Personally, I would like to see them in Qiskit as well, but I suggest to wait till the #13571 is resolved.