MilestoneTheory & algorithmsConfirmed

Hallgren gives an efficient quantum algorithm for Pell's equation

2002

Sean Hallgren gives a polynomial-time quantum algorithm for Pell's equation, using a compact representation of solutions that can be too long to write out. The best known classical method takes subexponential time; a classical lower bound is not proved.

Why it matters

Extending quantum period finding to irrational periods broadens its reach beyond integer factoring and discrete logarithms.

Sean Hallgren

See it on the timeline

Related

• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)
• Kitaev extends Shor's results with a method for measuring eigenvalues (Nov 20, 1995)