PySparQ.pysparq.algorithms.shor

Shor’s Quantum Factorization Algorithm Implementation

Exceptions

ShorExecutionFailed

Exception raised when Shor's algorithm fails to find factors.

Classes

ExpMod	Modular exponentiation operation.
ModMul	Controlled modular multiplication operation.
SemiClassicalShor	Semi-classical implementation of Shor's algorithm.
Shor	Full quantum Shor's algorithm.

Functions

check_period(→ None)	Check if period is valid for factoring.
compute_period(→ int)	Compute the period from measurement result.
create_shor_demo(→ str)	Generate a demo script for Shor's algorithm.
factor(→ tuple[int, int])	Factor N using Shor's algorithm.
factor_full_quantum(→ tuple[int, int])	Factor N using full quantum Shor's algorithm.
find_best_fraction(→ tuple[int, int])	Find the best fraction c/r approximating y/Q using Farey sequence.
general_expmod(→ int)	Compute a^x mod N efficiently using square-and-multiply.
shor_postprocess(→ tuple[int, int])	Classical post-processing for Shor's algorithm.

Module Contents

exception PySparQ.pysparq.algorithms.shor.ShorExecutionFailed

Bases: Exception

Exception raised when Shor’s algorithm fails to find factors.

Initialize self. See help(type(self)) for accurate signature.

class PySparQ.pysparq.algorithms.shor.ExpMod(input_reg: str, output_reg: str, a: int, N: int, period: int)

Modular exponentiation operation.

dag(state: pysparq.SparseState) → None

N: int

a: int

axmodn: list[int]

input_reg: str

output_reg: str

period: int

class PySparQ.pysparq.algorithms.shor.ModMul(reg: str, a: int, x: int, N: int)

Controlled modular multiplication operation.

clear_conditions() → None

conditioned_by_all_ones(cond: str) → ModMul

conditioned_by_nonzeros(cond: str | int) → ModMul

dag(state: pysparq.SparseState) → None

N: int

a: int

opnum: int

reg: str

x: int

class PySparQ.pysparq.algorithms.shor.SemiClassicalShor(a: int, N: int)

Semi-classical implementation of Shor’s algorithm.

run() → tuple[int, int]

N: int

a: int

meas_result: int

n: int

p: int

period: int

q: int

size: int

class PySparQ.pysparq.algorithms.shor.Shor(work_reg: str, ancilla_reg: str, a: int, N: int, period: int)

Full quantum Shor’s algorithm.

ancilla_reg: str

expmod: ExpMod

work_reg: str

PySparQ.pysparq.algorithms.shor.check_period(period: int, a: int, N: int) → None

Check if period is valid for factoring.

PySparQ.pysparq.algorithms.shor.compute_period(meas_result: int, size: int, N: int) → int

Compute the period from measurement result.

PySparQ.pysparq.algorithms.shor.create_shor_demo() → str

Generate a demo script for Shor’s algorithm.

PySparQ.pysparq.algorithms.shor.factor(N: int, a: int | None = ...) → tuple[int, int]

Factor N using Shor’s algorithm.

PySparQ.pysparq.algorithms.shor.factor_full_quantum(N: int, a: int | None = ...) → tuple[int, int]

Factor N using full quantum Shor’s algorithm.

PySparQ.pysparq.algorithms.shor.find_best_fraction(y: int, Q: int, N: int) → tuple[int, int]

Find the best fraction c/r approximating y/Q using Farey sequence.

PySparQ.pysparq.algorithms.shor.general_expmod(a: int, x: int, N: int) → int

Compute a^x mod N efficiently using square-and-multiply.

PySparQ.pysparq.algorithms.shor.shor_postprocess(meas: int, size: int, a: int, N: int) → tuple[int, int]

Classical post-processing for Shor’s algorithm.