Editing Shor's algorithm (section)

=== Physical implementation ===
Given the high error rates of contemporary quantum computers and too few qubits to use [[quantum error correction]], laboratory demonstrations obtain correct results only in a fraction of attempts.

In 2001, Shor's algorithm was demonstrated by a group at [[IBM]], who factored <math> 15 </math> into <math> 3 \times 5 </math>, using an [[Nuclear magnetic resonance quantum computer|NMR implementation]] of a quantum computer with seven qubits.<ref name = "VSBYSC01">{{cite journal |last1=Vandersypen |first1=Lieven M. K. |last2=Steffen |first2=Matthias |last3=Breyta |first3=Gregory |last4=Yannoni |first4=Costantino S. |last5=Sherwood |first5=Mark H. |last6=Chuang |first6=Isaac L. |title=Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance |journal=Nature |date=December 2001 |volume=414 |issue=6866 |pages=883–887 |doi=10.1038/414883a |pmid=11780055 |arxiv=quant-ph/0112176 |bibcode=2001Natur.414..883V }}</ref> After IBM's implementation, two independent groups implemented Shor's algorithm using [[Photonics|photonic]] qubits, emphasizing that multi-qubit [[quantum entanglement|entanglement]] was observed when running the Shor's algorithm circuits.<ref name = "LBYP07">{{cite journal |last1=Lu |first1=Chao-Yang |last2=Browne |first2=Daniel E. |last3=Yang |first3=Tao |last4=Pan |first4=Jian-Wei |title=Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits |journal=Physical Review Letters |date=19 December 2007 |volume=99 |issue=25 |page=250504 |doi=10.1103/PhysRevLett.99.250504 |pmid=18233508 |arxiv=0705.1684 |bibcode=2007PhRvL..99y0504L }}</ref><ref name = "LWLBJGW07">{{cite journal |last1=Lanyon |first1=B. P. |last2=Weinhold |first2=T. J. |last3=Langford |first3=N. K. |last4=Barbieri |first4=M. |last5=James |first5=D. F. V. |last6=Gilchrist |first6=A. |last7=White |first7=A. G. |title=Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement |journal=Physical Review Letters |date=19 December 2007 |volume=99 |issue=25 |page=250505 |doi=10.1103/PhysRevLett.99.250505 |pmid=18233509 |arxiv=0705.1398 |bibcode=2007PhRvL..99y0505L }}</ref> In 2012, the factorization of <math> 15 </math> was performed with solid-state qubits.<ref>{{Cite journal|last1 = Lucero|first1 = Erik|last2 = Barends|first2 = Rami|last3 = Chen|first3 = Yu|last4 = Kelly|first4 = Julian|last5 = Mariantoni|first5 = Matteo|last6 = Megrant|first6 = Anthony|last7 = O'Malley|first7 = Peter|last8 = Sank|first8 = Daniel|last9 = Vainsencher|first9 = Amit|last10 = Wenner|first10 = James|last11 = White|first11 = Ted|last12 = Yin|first12 = Yi|last13 = Cleland|first13 = Andrew N.|last14 = Martinis|first14 = John M.|title = Computing prime factors with a Josephson phase qubit quantum processor|journal = Nature Physics|volume = 8|issue = 10|pages = 719|year = 2012|doi = 10.1038/nphys2385|bibcode = 2012NatPh...8..719L|arxiv = 1202.5707|s2cid = 44055700}}</ref> Later, in 2012, the factorization of <math> 21 </math> was achieved.<ref>{{cite journal|last1 = Martín-López|first1 = Enrique|last2 = Martín-López|first2 = Enrique|last3 = Laing|first3 = Anthony|last4 = Lawson|first4 = Thomas|last5 = Alvarez|first5 = Roberto|last6 = Zhou|first6 = Xiao-Qi|last7 = O'Brien|first7 = Jeremy L.|title = Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal = Nature Photonics|volume =6|issue = 11|pages = 773–776|date = 12 October 2012|doi = 10.1038/nphoton.2012.259|arxiv = 1111.4147|bibcode = 2012NaPho...6..773M|s2cid = 46546101}}</ref> In 2016, the factorization of <math> 15 </math> was performed again using trapped-ion qubits with a recycling technique.<ref>{{cite journal|last1 = Monz|first1 = Thomas |last2 = Nigg|first2 = Daniel|last3 = Martinez|first3 = Esteban A.|last4 = Brandl|first4 = Matthias F.|last5 = Schindler|first5 = Philipp|last6 = Rines|first6 = Richard|last7 = Wang|first7 = Shannon X.|last8 = Chuang|first8 = Isaac L.|last9 = Blatt|first9 = Rainer|title = Realization of a scalable Shor algorithm|journal = Science|volume =351|issue = 6277|pages = 1068–1070|date = 4 March 2016|doi = 10.1126/science.aad9480|pmid = 26941315 |arxiv = 1507.08852|bibcode = 2016Sci...351.1068M|s2cid = 17426142}}</ref> In 2019, an attempt was made to factor the number <math> 35 </math> using Shor's algorithm on an IBM [[IBM Q System One|Q System One]], but the algorithm failed because of accumulating errors.<ref>{{cite journal |last1=Amico |first1=Mirko |last2=Saleem |first2=Zain H. |last3=Kumph |first3=Muir |title=Experimental study of Shor's factoring algorithm using the IBM Q Experience |journal=Physical Review A |date=8 July 2019 |volume=100 |issue=1 |page=012305 |doi=10.1103/PhysRevA.100.012305 |arxiv=1903.00768 |bibcode=2019PhRvA.100a2305A |s2cid=92987546 }}</ref> However, all these demonstrations have compiled the algorithm by making use of prior knowledge of the answer, and some have even oversimplified the algorithm in a way that makes it equivalent to coin flipping.<ref>{{cite journal |last1=Smolin |first1=John A. |last2=Smith |first2=Graeme |last3=Vargo |first3=Alexander |title=Oversimplifying quantum factoring |journal=Nature |date=July 2013 |volume=499 |issue=7457 |pages=163–165 |doi=10.1038/nature12290 |pmid=23846653 |arxiv=1301.7007 |bibcode=2013Natur.499..163S }}</ref> Furthermore, attempts using quantum computers with other algorithms have been made.<ref>{{cite journal |last1=Karamlou |first1=Amir H. |last2=Simon |first2=William A. |last3=Katabarwa |first3=Amara |last4=Scholten |first4=Travis L. |last5=Peropadre |first5=Borja |last6=Cao |first6=Yudong |title=Analyzing the performance of variational quantum factoring on a superconducting quantum processor |journal=npj Quantum Information |date=28 October 2021 |volume=7 |issue=1 |page=156 |doi=10.1038/s41534-021-00478-z |arxiv=2012.07825 |bibcode=2021npjQI...7..156K }}</ref> However, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.<ref>{{Cite web |date=2019-12-28 |title=Quantum computing motte-and-baileys |url=https://scottaaronson.blog/?p=4447 |access-date=2021-11-15 |website=Shtetl-Optimized |language=en-US}}</ref>

Theoretical analyses of Shor's algorithm assume a quantum computer free of noise and errors. However, near-term practical implementations will have to deal with such undesired phenomena (when more qubits are available, [[quantum error correction]] can help). In 2023, [[Jin-Yi Cai]] showed that in the presence of noise, Shor's algorithm fails [[asymptotically almost surely]] for large semiprimes that are products of two primes in {{OEIS el|A073024}}.<ref name="noise">{{cite journal |arxiv=2306.10072 |last1=Cai |first1=Jin-Yi |date=2024 |title=Shor's algorithm does not factor large integers in the presence of noise |journal=Science China Information Sciences |volume=67 |issue=7 |doi=10.1007/s11432-023-3961-3 }}</ref> These primes <math>p</math> have the property that <math>p-1</math> has a prime factor larger than <math>p^{2/3}</math>, and have a positive density in the set of all primes. Hence error correction will be needed to be able to factor all numbers with Shor's algorithm.