Constant-time hybrid compilation of Shor's algorithm with quantum just-in-time compilation

Shortalyst

Code and benchmark scripts for the paper, "Constant-time hybrid compilation of Shor’s algorithm with quantum just-in-time compilation", by David Ittah (@dime10), Jackson Fraser (@JacksonnF), Josh Izaac (@josh146), and Olivia Di Matteo (@glassnotes).

Usage

General usage

To run the quantum just-in-time-compiled version of Shor's algorithm out-of-the-box, you can pass it a number to factor, N, and a random integer a between 2 and N-2 (inclusive).

import jax.numpy as jnp

from shortalyst.shors_algorithm import shors_algorithm

N = 35
a = 2
n_bits = int(jnp.floor(jnp.log2(N))) + 1
n_trials = 100

p, q, success_prob, _, _ = shors_algorithm(N, a, n_bits, n_trials)

print(f"p = {p}, q = {q}, success_prob = {success_prob:.4f}")

A random a can also be generated by passing a JAX PRNGKey as a keyword argument (see docstring for details).

Installation

Dependencies are listed in the pyproject.toml file and can be installed via

$ pip install -e .

or a tool such as Poetry. pytest is required for the suite of unit tests in tests/.

Replication

Code for generating the set of plots shown in the paper can be found in the compilation-benchmarking.ipynb notebook.

To obtain the gate counts, a custom version of Catalyst is currently required. Please clone and checkout the shortalyst tag from the official Catalyst repository, and follow the build from the source instructions available in the documentation.

Alternatively, the data files used for the paper can be found in data/.

Acknowledgments

If you use our code in your own work, please cite our preprint:

@misc{ittah2025constanttimehybridcompilationshors,
      title={Constant-time hybrid compilation of Shor's algorithm with quantum just-in-time compilation}, 
      author={David Ittah and Jackson Fraser and Josh Izaac and Olivia {Di Matteo}},
      year={2025},
      eprint={2504.12449},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2504.12449}, 
}

This work is a collaboration between the UBC Quantum Software and Algorithms Research Lab, and members of the PennyLane and Catalyst teams at Xanadu.

It is based in part on the PennyLane demo, Quantum just-in-time compiling Shor’s algorithm with PennyLane and Catalyst.

The QSAR Lab acknowledges funding from an NSERC Alliance Quantum grant, the Canada Research Chairs program, and the Electrical and Computer Engineering Department at UBC.