Prove that a given integer N is prime, or in most cases prove it composite and produce a witness, rather than merely declaring it probably prime as a randomized primality test does.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Prove that a given integer N is prime, or in most cases prove it composite and produce a witness, rather than merely declaring it probably prime as a randomized primality test does. By Lucas's theorem, if some element of the multiplicative group modulo N has order exactly N − 1, then N is prime. The algorithm picks a random a; if the greatest common divisor of a and N is not one, the divisor itself proves N composite. Otherwise it computes a^((N−1)/2) mod N classically as a cheap Fermat screen: if the result is neither +1 nor −1 then N is composite with a as witness, if it is +1 the algorithm restarts, and only if it is −1 — which guarantees that the order divides N − 1 — does it invoke quantum order finding to compute the order exactly. If that order is N − 1, then N is prime and a is a quantum certificate of its primality. The classical screen exists precisely to avoid paying for the quantum subroutine when it would not yet be informative.
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
This record is named by the layer graph at:
Takes A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted. Returns The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
By Lucas's theorem, if some element of the multiplicative group modulo N has order exactly N − 1, then N is prime. The algorithm picks a random a; if the greatest common divisor of a and N is not one, the divisor itself proves N composite. Otherwise it computes a^((N−1)/2) mod N classically as a cheap Fermat screen: if the result is neither +1 nor −1 then N is composite with a as witness, if it is +1 the algorithm restarts, and only if it is −1 — which guarantees that the order divides N − 1 — does it invoke quantum order finding to compute the order exactly. If that order is N − 1, then N is prime and a is a quantum certificate of its primality. The classical screen exists precisely to avoid paying for the quantum subroutine when it would not yet be informative. This record's speedup class, "Polynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "Its complexity is essentially quadratic in the asymptotic limit, which is more efficient than classical tests that prove primality with certainty, which are usually restricted to integers of a particular form, or require a number of operations of the order of the sixth power of the number of bits (AKS test).". Reported cost: O((log n)² n³) operations for an n-bit number N, reducible to O(log log n (log n)³ n²) in the asymptotic limit if fast multiplication is used. The paper states that this reduces the asymptotic complexity of the earlier Chau-Lo quantum primality test from O((log n)(log log n) n³) to O((log log n)(log n)³ n²)..
ALGORITHM: Primality proving by quantum order finding
PROBLEM: Prove that a given integer N is prime, or in most cases prove it composite and produce a witness, rather than merely declaring it probably prime as a randomized primality test does.
IDEA: By Lucas's theorem, if some element of the multiplicative group modulo N has order exactly N − 1, then N is prime. The algorithm picks a random a; if the greatest common divisor of a and N is not one, the divisor itself proves N composite. Otherwise it computes a^((N−1)/2) mod N classically as a cheap Fermat screen: if the result is neither +1 nor −1 then N is composite with a as witness, if it is +1 the algorithm restarts, and only if it is −1 — which guarantees that the order divides N − 1 — does it invoke quantum order finding to compute the order exactly. If that order is N − 1, then N is prime and a is a quantum certificate of its primality. The classical screen exists precisely to avoid paying for the quantum subroutine when it would not yet be informative.
REPORTED COST: O((log n)² n³) operations for an n-bit number N, reducible to O(log log n (log n)³ n²) in the asymptotic limit if fast multiplication is used. The paper states that this reduces the asymptotic complexity of the earlier Chau-Lo quantum primality test from O((log n)(log log n) n³) to O((log log n)(log n)³ n²).
BASIS: abstract of arXiv:1711.02616: "The algorithm requires O((log n)^2 n^3) operations for a number N with n bits, which can be reduced to O(log log n(log n)^3 n^2) operations in the asymptotic limit if we use fast multiplication."; body: "The total expected complexity of our algorithm is O((log n)^2 n^3) for the log n repetitions needed to find an element of order N − 1 with high probability."; and, for the comparison with the earlier test: "Our algorithm reduces the asymptotic complexity of the Chau-Lo quantum primality test from O((log n)(log log n)n^3) to O((log log n)(log n)^3n^2)."
PRIMARY SOURCE: Alvaro Donis-Vela, Juan Carlos Garcia-Escartin (2017), A quantum primality test with order finding — https://arxiv.org/abs/1711.02616
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Compare Computational number theory with the strongest classical method for the same instance, input budget, and output metric.
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
Primary source, and the source of this record's cost claim. Consult it for the classical Fermat screen that decides when the quantum subroutine is worth invoking, for the black-box treatment of order finding that every stated figure depends on, and for the passage where the authors accept losing the classical certificate of primality in exchange for a quantum one.
arxiv.org/abs/1711.02616 ↗