org.soulspace.qclojure.domain.math — org.soulspace/qclojure 0.2.0

Mathematical operations and utilities for quantum algorithms.

complete-factorization clj

(complete-factorization factors)

Complete factorization of a vector of partial factors, e.g. [3 9].

continued-fraction clj

(continued-fraction num den)

(continued-fraction num den max-depth)

(continued-fraction num den max-depth epsilon)

Convert a fraction to continued fraction representation.

This implementation handles numerical precision issues and early termination conditions that are important for Shor's algorithm. It can detect periodic patterns in the continued fraction expansion, which is crucial for finding the correct period.

Parameters:

• num: Numerator of the fraction
• den: Denominator of the fraction
• max-depth: (Optional) Maximum depth of continued fraction expansion
• epsilon: (Optional) Precision threshold for detecting near-zero remainders

Returns: Vector of continued fraction terms

convergents clj

(convergents cf)

Calculate convergents from continued fraction representation.

This enhanced implementation handles edge cases better and includes additional validation to ensure proper convergence, which is important for accurately extracting periods in Shor's algorithm.

Parameters:

• cf: Vector of continued fraction terms

Returns: Vector of convergents as [numerator denominator] pairs

find-period clj

(find-period measured-value precision N a)

Find the period from a phase estimate using improved continued fraction expansion.

This function implements a more robust version of period extraction from a phase measurement, which is critical for Shor's algorithm.

Parameters:

• measured-value: The value from quantum measurement
• precision: Number of bits used in phase estimation
• N: Modulus for period finding
• a: Base for modular exponentiation

Returns: Most likely period or nil if no valid period found

gcd clj

(gcd a b)

Calculate greatest common divisor using Euclidean algorithm.

mod-exp clj

(mod-exp base exp m)

Calculate (base^exp) mod m efficiently using binary exponentiation.

perfect-power-factor clj

(perfect-power-factor N)

Check if N is a perfect power and return its base factor.

A perfect power is a number that can be expressed as a^k for some integers a and k where k > 1. This function finds the smallest base a such that N = a^k for some k > 1.

This is used in Shor's algorithm for classical preprocessing - if N is a perfect power, we can factor it classically without needing quantum period finding.

Examples:

• perfect-power-factor(8) = 2 (since 8 = 2^3)
• perfect-power-factor(9) = 3 (since 9 = 3^2)
• perfect-power-factor(15) = 1 (since 15 is not a perfect power)

Parameters:

• N: The number to check for perfect power

Returns: Base factor a if N = a^k for some k > 1, otherwise returns 1

prime? clj

(prime? n)

Simple primality test for small numbers.

round-precision clj

(round-precision x precision)

Round a number to specified decimal places.

Parameters:

• x: Number to round
• precision: Number of decimal places

Returns: Number rounded to specified precision