Quantum period finding algorithm for Shor's algorithm.
This algorithm is a specialized application of quantum phase estimation (QPE) to find the period of the modular exponentiation function f(x) = a^x mod N.
Instead of reimplementing QPE, this module leverages the existing quantum-phase-estimation algorithm and adapts it for period finding by:
Quantum period finding algorithm for Shor's algorithm. This algorithm is a specialized application of quantum phase estimation (QPE) to find the period of the modular exponentiation function f(x) = a^x mod N. Instead of reimplementing QPE, this module leverages the existing quantum-phase-estimation algorithm and adapts it for period finding by: 1. Setting up the appropriate unitary operator (modular exponentiation) 2. Using QPE to estimate the phase 3. Converting phase estimates to period estimates using continued fractions
(phase-to-period phase precision-qubits N a)Convert a phase estimate from QPE to a period estimate for modular exponentiation.
In quantum period finding, we're estimating the phase φ where the eigenvalue of the modular exponentiation unitary is e^(iφ). The period r relates to the phase through: φ = 2πs/r for some integer s.
We use continued fractions to find the best rational approximation s/r where r is likely to be the period.
Parameters:
Returns: Map with period estimate or nil if no valid period found
Convert a phase estimate from QPE to a period estimate for modular exponentiation. In quantum period finding, we're estimating the phase φ where the eigenvalue of the modular exponentiation unitary is e^(iφ). The period r relates to the phase through: φ = 2πs/r for some integer s. We use continued fractions to find the best rational approximation s/r where r is likely to be the period. Parameters: - phase: Estimated phase from QPE - precision-qubits: Number of precision qubits used in QPE - N: Modulus for period finding - a: Base for modular exponentiation a^x mod N Returns: Map with period estimate or nil if no valid period found
(quantum-period-finding backend a N precision-qubits)(quantum-period-finding backend a N precision-qubits n-measurements)(quantum-period-finding backend a N precision-qubits n-measurements options)Find the period of f(x) = a^x mod N using quantum phase estimation.
This function is a specialized application of quantum phase estimation for period finding in Shor's algorithm. It uses a generalized QPE that works with modular exponentiation as the unitary operator.
The approach:
Parameters:
Returns: Map containing:
Find the period of f(x) = a^x mod N using quantum phase estimation. This function is a specialized application of quantum phase estimation for period finding in Shor's algorithm. It uses a generalized QPE that works with modular exponentiation as the unitary operator. The approach: 1. Use generalized QPE with modular exponentiation as the controlled unitary 2. Convert phase measurement results to period estimates using continued fractions 3. Return the most likely period with statistical confidence Parameters: - backend: Quantum backend implementing the QuantumBackend protocol - a: Base for the function f(x) = a^x mod N - N: Modulus - precision-qubits: Number of qubits for phase precision (affects accuracy) - n-measurements: (optional) Number of measurements for statistical analysis (default: 1) - options: (optional) Map containing additional backend options Returns: Map containing: - :estimated-period - Most likely period estimate - :period-candidates - All valid period candidates with probabilities - :qpe-results - Raw results from quantum phase estimation - :success - Whether a valid period was found - :confidence - Statistical confidence in the result
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 |