Shor's algorithm for integer factorization using quantum period finding.
This implementation includes optimizations for hardware compatibility, multiple measurements for statistical robustness, and enhanced period extraction.
The algorithm combines classical preprocessing, quantum period finding, and classical post-processing to efficiently factor composite integers.
For complete prime factorization, use the complete-factorization function
which recursively applies Shor's algorithm until all factors are prime.
Shor's algorithm for integer factorization using quantum period finding. This implementation includes optimizations for hardware compatibility, multiple measurements for statistical robustness, and enhanced period extraction. The algorithm combines classical preprocessing, quantum period finding, and classical post-processing to efficiently factor composite integers. For complete prime factorization, use the `complete-factorization` function which recursively applies Shor's algorithm until all factors are prime.
(complete-factorization backend N)(complete-factorization backend N options)Perform complete prime factorization using Shor's algorithm recursively.
Unlike the basic shor-algorithm which finds only one factorization, this function continues factoring until all factors are prime.
Parameters:
Returns: Map containing:
Example: (complete-factorization backend 27) ;=> {:prime-factors [3 3 3], :success true, ...} (complete-factorization backend 15) ;=> {:prime-factors [3 5], :success true, ...}
Perform complete prime factorization using Shor's algorithm recursively.
Unlike the basic shor-algorithm which finds only one factorization,
this function continues factoring until all factors are prime.
Parameters:
- backend: Quantum backend for executing quantum circuits
- N: Integer to factor completely
- options: (Optional) Options map passed to shor-algorithm
Returns:
Map containing:
- :prime-factors - Vector of all prime factors (sorted)
- :success - Boolean indicating if complete factorization succeeded
- :N - The input number
- :factorization-tree - Tree showing the factorization process
- :total-attempts - Total number of Shor algorithm calls made
- :statistics - Combined statistics from all factorization steps
Example:
(complete-factorization backend 27) ;=> {:prime-factors [3 3 3], :success true, ...}
(complete-factorization backend 15) ;=> {:prime-factors [3 5], :success true, ...}(generate-unique-coprime-values N)Generate all values a where 2 <= a < N and gcd(a,N) = 1, in random order. This ensures no duplicate values are attempted during factorization.
Parameters:
Returns: Vector of unique coprime integers a
Generate all values a where 2 <= a < N and gcd(a,N) = 1, in random order. This ensures no duplicate values are attempted during factorization. Parameters: - N: Integer to factor Returns: Vector of unique coprime integers a
(shor-algorithm backend N)(shor-algorithm backend N options)Shor's algorithm for integer factorization.
Shor's algorithm is a quantum algorithm that can factor large integers exponentially faster than the best known classical algorithms. It combines classical preprocessing, quantum period finding, and classical post-processing.
This improved implementation supports:
Algorithm steps:
Parameters:
Returns: Map containing:
Example: (shor-algorithm 15) ;=> {:factors [3 5], :success true, :N 15, ...} (shor-algorithm 21 {:hardware-compatible true}) ;=> {:factors [3 7], :success true, ...}
Shor's algorithm for integer factorization.
Shor's algorithm is a quantum algorithm that can factor large integers
exponentially faster than the best known classical algorithms. It combines
classical preprocessing, quantum period finding, and classical post-processing.
This improved implementation supports:
1. Hardware-compatible mode for real quantum hardware execution
2. Multiple measurements for statistical robustness
3. Enhanced period extraction for better success rate
Algorithm steps:
1. Classical preprocessing: Check for trivial cases
2. Choose random a < N, check gcd(a,N)
3. Quantum period finding: Find period r of f(x) = a^x mod N
4. Classical post-processing: Extract factors from the period
Parameters:
- backend: Quantum backend implementing the QuantumBackend protocol to execute the circuit
- N: Integer to factor (should be composite)
- options: (Optional) Map containing:
- :n-qubits - Number of qubits for quantum period finding (default: 2*⌈log₂(N)⌉)
- :hardware-compatible - Boolean indicating if hardware-optimized circuit should be used
- :n-measurements - Number of measurements for statistical analysis (default: 10)
- :max-attempts - Maximum number of random 'a' values to try (default: 10)
Returns:
Map containing:
- :factors - Vector of non-trivial factors found (empty if factorization failed)
- :success - Boolean indicating if factorization succeeded
- :N - The input number
- :attempts - Vector of maps describing each attempt with different 'a' values
- :circuit - The quantum circuit from the successful attempt (if any)
- :statistics - Performance statistics and confidence metrics
Example:
(shor-algorithm 15) ;=> {:factors [3 5], :success true, :N 15, ...}
(shor-algorithm 21 {:hardware-compatible true}) ;=> {:factors [3 7], :success true, ...}cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |