Editing Shor's algorithm (section)

== Period finding and discrete logarithms ==
Shor's algorithms for the [[Discrete logarithm|discrete log]] and the order finding problems are instances of an algorithm solving the period finding problem.{{Citation needed|date=August 2023}} All three are instances of the [[hidden subgroup problem]].<!-- It would be good to add the period finding algorithm here -->

=== Shor's algorithm for discrete logarithms ===
Given a [[Group (mathematics)|group]] <math>G</math> with order <math> p </math> and [[Generator (mathematics)|generator]] <math> g \in G </math>, suppose we know that <math> x = g^{r} \in G </math>, for some <math> r \in \mathbb{Z}_p </math>, and we wish to compute <math> r </math>, which is the [[discrete logarithm]]: <math> r = {\log_{g}}(x) </math>. Consider the [[abelian group]] <math> \mathbb{Z}_{p} \times \mathbb{Z}_{p} </math>, where each factor corresponds to modular addition of values. Now, consider the function

:<math>
f \colon \mathbb{Z}_{p} \times \mathbb{Z}_{p} \to G \;;\; f(a,b) = g^{a} x^{- b} .
</math>

This gives us an abelian [[hidden subgroup problem]], where <math> f </math> corresponds to a [[group homomorphism]]. The [[Kernel (algebra)|kernel]] corresponds to the multiples of <math> (r,1) </math>. So, if we can find the kernel, we can find <math> r </math>. A quantum algorithm for solving this problem exists. This algorithm is, like the factor-finding algorithm, due to Peter Shor and both are implemented by creating a superposition through using Hadamard gates, followed by implementing <math> f </math> as a quantum transform, followed finally by a quantum Fourier transform.<ref name=":0" /> Due to this, the quantum algorithm for computing the discrete logarithm is also occasionally referred to as "Shor's Algorithm."

The order-finding problem can also be viewed as a hidden subgroup problem.<ref name=":0">{{cite book |last1=Nielsen |first1=Michael A. |url=http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf |archive-url=https://web.archive.org/web/20190711070716/http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf |archive-date=2019-07-11 |url-status=live |title=Quantum Computation and Quantum Information |last2=Chuang |first2=Isaac L. |date=9 December 2010 |publisher=Cambridge University Press |isbn=978-1-107-00217-3 |edition=7th |access-date=24 April 2022}}</ref> To see this, consider the group of integers under addition, and for a given <math> a\in\mathbb{Z}</math> such that: <math> a^{r}=1</math>, the function
:<math>
f \colon \mathbb{Z}\to \mathbb{Z} \;;\; f(x) = a^{x},\; f(x+r) = f(x) .
</math>
For any finite abelian group <math>G</math>, a quantum algorithm exists for solving the hidden subgroup for <math>G</math> in polynomial time.<ref name=":0" />