Are there any uses for Shor's algorithm other than breaking public key cryptography

Are there any uses for Shor's algorithm other than breaking public key cryptography Ask Question Asked 2 years, 7 months ago Modified today Viewed 3k times 12 This question may be slightly opinion based, so I apologise if this is the incorrect place to ask. My question is, is there any use for Shor's integer factorisation algorithm other than for breaking public key cryptography. If there isn't, then am I right in thinking that the algorithm becomes obsolete once all data is encrypted using post quantum cryptography? shors-algorithmapplications Share Improve this question Follow edited Sep 18, 2023 at 8:37 CommunityBot 1 asked Sep 14, 2023 at 23:19 Adrien Amour 4013 3 silver badges 8 8 bronze badges 2 Duplicate of a question posted on Math Overflow: mathoverflow.net/q/413924 –  tparker Commented Sep 17, 2023 at 22:53 Add a comment 2 Answers Sorted by: Highest score (default) Date modified (newest first) Date created (oldest first) 15 A bit of an esoteric answer: there is a particular proposal for post-quantum cryptography called "CSI-FiSh", based on isogenies. Without getting too deep into the number theory, the parameters of CSI-FiSh define a particular group structure. If we know the group structure, we can make efficient digital signature schemes; if we do not know the group structure, the digital signature schemes are much less efficient. However, the best classical algorithms to find the group structure are subexponential in the input size of the CSI-FiSh parameters, and the best quantum attacks are also subexponential. So far we only know the group structure for 512-bit primes, which many people (including me) feel are not large enough to be quantum safe. But we cannot find the group structure for bigger parameters with classical computers. Yet, Shor's algorithm could find the group structure in polynomial time! In the end, this means we can't make this scheme efficient and secure until we have a quantum computer that can apply Shor's algorithm to it. Some have called it "post-post-quantum cryptography" for this reason. I'm not sure that this scheme would actually be used, but it's a potential constructive application for Shor's algorithm. Share Improve this answer Follow edited Sep 15, 2023 at 21:10 answered Sep 15, 2023 at 17:44 Sam Jaques 2,3548 8 silver badges 15 15 bronze badges 2 That’s pretty neat! How meta. –  Mark Spinelli Commented Sep 15, 2023 at 18:24 Where could we find out more about CSI-FiSh, @SamJacques? –  Mark Spinelli Commented Sep 15, 2023 at 18:45 Sorry, added a link! –  Sam Jaques Commented Sep 15, 2023 at 21:10 Add a comment 13 community wiki It's an interesting question to pose which problems reduce to factoring (or discrete log), and whether any of those problems could be of practical value. In general I think the consensus is that most such problems are of some number-theoretical bent in the first place. There's a 1987 paper from Heather Woll that proves and lists some reductions known at that time: Whether any other reductions are known, since, say, Shor '94, that are of industrial relevance, I am not sure. I've often thought about reducing factoring to finding Golomb rulers but I don't know enough number theory to make headway. Factoring (and discrete log and related questions) are such unique problems in computer science - Aaronson often quips that if we can factor numbers easily then we can collapse the entire world economy but we wouldn't collapse the polynomial hierarchy. Graph Isomorphism is another problem of much practical importance, but alas this is not known to be in BQP (and our classical algorithms are pretty good anyways). I do disagree, though, that "the algorithm becomes obsolete once all data is encrypted using post quantum cryptography". The website that I'm writing this on, right now, says https - all of those private keys are ripe for the taking even after conversion to post-quantum cryptography. Share Improve this answer Follow edited 4 hours ago community wiki 2 revs Mark Spinelli Very interesting! Thank you for your answer. –  FDGod Commented Sep 15, 2023 at 8:27 Add a comment Start asking to get answers Find the answer to your question by asking. Ask question Explore related questions shors-algorithmapplications See similar questions with these tags. The Overflow Blog The messy truth of your AI strategies Gen Z needs a knowledge base (and so do you) Related 33 Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor? 5 Are there any other published quantum factoring algorithms that are simpler or more efficient than Shor’s? 3 Implementing QFT for Shor's Algorithm 3 Implementing QFT for Shor's Algorithm? 12 Does the quantum Fourier transform have many applications beyond period finding? 4 Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm? 9 Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's? 7 How many logical qubits are needed for RSA breaking? Hot Network Questions Why did "boxer" become the default air-cooled engine? NSolve where function being searched is the result of a DE How to give a big power up to players against the final boss? Hume: "The most lively thought is still inferior to the dullest sensation." Really? Archaic usage of "whomst" ACAP Takeoff Field Length: What V1 Assumption Is Used? How do I successfully get to this character in Dark Bramble? Would a future closed-loop steady-state economy (with no net resource depletion) mine outer space, and if so, for what? Hostile reaction to relationship within the lab hex viewer output What role does vibrato have in the orchestra? What is this PCB connector nut? Does Jesus's warning during His "Triumphal Entry" force interpretation of "this Generation" (Matt. 24) as referring to the First Century Jews? Source for Rabbi Shmuel Rozovsky's piece on Keruvim? Mysterious Clan Gathering: Trouble Brain implant fails leaving man in a bad condition Does pasting lemma hold for uniformly continuous functions? Confusion in the definition of being root of polynomials What is wrong with this "counterexample" to the Extreme Value Theorem? I picked up a bike frame. No branding, no paint, no parts. Any idea what bike this is?? Serial number LI08G00346. Pics attached What makes the dialogue logic way of distinguishing "logical form" from "content" philosophically distinctive? Mysterious binomial identity Password checker Are the new Talgo trains on the Copenhagen-Hamburg route any faster than the old ones in terms of actual travel time? Question feed By continuing to use this website, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. By exiting this window, default cookies will be accepted. To reject cookies, select an option from below. Customize settings Cookie Consent Preference Center When you visit any of our websites, it may store or retrieve information on your browser, mostly in the form of cookies. This information might be about you, your preferences, or your device and is mostly used to make the site work as you expect it to. The information does not usually directly identify you, but it can give you a more personalized experience. Because we respect your right to privacy, you can choose not to allow some types of cookies. Click on the different category headings to find out more and manage your preferences. Please note, blocking some types of cookies may impact your experience of the site and the services we are able to offer. Cookie Policy Accept all cookies Manage Consent Preferences Strictly Necessary Cookies Always Active These cookies are necessary for the website to function and cannot be switched off in our systems. They are usually only set in response to actions made by you which amount to a request for services, such as setting your privacy preferences, logging in or filling in forms. You can set your browser to block or alert you about these cookies, but some parts of the site will not then work. These cookies do not store any personally identifiable information. Targeting Cookies Targeting Cookies These cookies are used to make advertising messages more relevant to you and may be set through our site by us or by our advertising partners. They may be used to build a profile of your interests and show you relevant advertising on our site or on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. Performance Cookies Performance Cookies These cookies allow us to count visits and traffic sources so we can measure and improve the performance of our site. They help us to know which pages are the most and least popular and see how visitors move around the site. All information these cookies collect is aggregated and therefore anonymous. If you do not allow these cookies we will not know when you have visited our site, and will not be able to monitor its performance. Functional Cookies Functional Cookies These cookies enable the website to provide enhanced functionality and personalisation. They may be set by us or by third party providers whose services we have added to our pages. If you do not allow these cookies then some or all of these services may not function properly. Cookie List Clear checkbox label label Apply Cancel Consent Leg.Interest checkbox label label checkbox label label checkbox label label Necessary cookies only Confirm My Choices