Could quantum computing help resolve some computability problems like p vs np or the halting problem?Let $Q$ be an undecidable subset of $mathbbN$ created by diagonalization. What's the problem with this “algorithm” for computing $Q$?Why is the numbering of computable functions significant?Universal introduction - how exactly does it work?$p to q$ vs. $p$ only if $q$Do we really need material implication, material equivalence and the exclusive or?Textbook (or similar) for finite multivalued logicWhy a decidable logic is considered trivial?

Object Oriented Design: Where to place behavior that pertains to more than one type of object?

Is Zhent just the term for any member of the Zhentarim?

No interest ever. Just a fee for my end,

How do I know how many sub-shells deep I am?

An example of a "regular poset" which does not belong to a convex polytope

Fair Use of Photos as a Derivative Work

Redirect output on-the-fly - looks not possible in Linux, why?

how would i use rm to delete all files without certain wildcard?

SHA3-255, one bit less

The answer is the same (tricky puzzle!)

I've been fired, was allowed to announce it as if I quit and given extra notice, how to handle the questions?

Was Smaug sealed inside the Lonely Mountain?

How are characteristic classes morphisms of infinite loop spaces? (if they are)

Found a minor bug, affecting 1% of users. What should QA do?

Choice of solvent during thin layer chromatography

Does SQL Server's serializable isolation level lock entire table

Should I be able to see patterns in a HS256 encoded JWT?

What's the difference between motherboard and chassis?

Can/should you swim in zero G?

How to explain that the sums of numerators over sums of denominators isn't the same as the mean of ratios?

Why is my vegetable stock bitter, but the chicken stock not?

Would houseruling two or more instances of resistance to the same element as immunity be overly unbalanced?

Power Adapter for Traveling to Scotland (I live in the US)

Is there any problem with students seeing faculty naked in university gym?



Could quantum computing help resolve some computability problems like p vs np or the halting problem?


Let $Q$ be an undecidable subset of $mathbbN$ created by diagonalization. What's the problem with this “algorithm” for computing $Q$?Why is the numbering of computable functions significant?Universal introduction - how exactly does it work?$p to q$ vs. $p$ only if $q$Do we really need material implication, material equivalence and the exclusive or?Textbook (or similar) for finite multivalued logicWhy a decidable logic is considered trivial?






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;








2












$begingroup$


How much could " quantum " logic push the limits of computability in the sense of standard logic. Don't know if this is even a sensible question and it's as vague as it gets, that's why I'm posting it here not on owerflow although might be something still in research.










share|cite|improve this question









$endgroup$




















    2












    $begingroup$


    How much could " quantum " logic push the limits of computability in the sense of standard logic. Don't know if this is even a sensible question and it's as vague as it gets, that's why I'm posting it here not on owerflow although might be something still in research.










    share|cite|improve this question









    $endgroup$
















      2












      2








      2





      $begingroup$


      How much could " quantum " logic push the limits of computability in the sense of standard logic. Don't know if this is even a sensible question and it's as vague as it gets, that's why I'm posting it here not on owerflow although might be something still in research.










      share|cite|improve this question









      $endgroup$




      How much could " quantum " logic push the limits of computability in the sense of standard logic. Don't know if this is even a sensible question and it's as vague as it gets, that's why I'm posting it here not on owerflow although might be something still in research.







      logic






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 8 hours ago









      Leo KovacicLeo Kovacic

      213 bronze badges




      213 bronze badges























          2 Answers
          2






          active

          oldest

          votes


















          2














          $begingroup$

          Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).



          This article by Aaronson is a good starting point for this sort of thing. To quote from the article:




          [Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster
          than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.





          As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").






          share|cite|improve this answer











          $endgroup$










          • 1




            $begingroup$
            To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
            $endgroup$
            – Derek Elkins
            6 hours ago



















          2














          $begingroup$

          Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.



          However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.






          share|cite|improve this answer











          $endgroup$
















            Your Answer








            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "69"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader:
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            ,
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );














            draft saved

            draft discarded
















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3373541%2fcould-quantum-computing-help-resolve-some-computability-problems-like-p-vs-np-or%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            2














            $begingroup$

            Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).



            This article by Aaronson is a good starting point for this sort of thing. To quote from the article:




            [Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster
            than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.





            As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").






            share|cite|improve this answer











            $endgroup$










            • 1




              $begingroup$
              To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
              $endgroup$
              – Derek Elkins
              6 hours ago
















            2














            $begingroup$

            Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).



            This article by Aaronson is a good starting point for this sort of thing. To quote from the article:




            [Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster
            than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.





            As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").






            share|cite|improve this answer











            $endgroup$










            • 1




              $begingroup$
              To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
              $endgroup$
              – Derek Elkins
              6 hours ago














            2














            2










            2







            $begingroup$

            Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).



            This article by Aaronson is a good starting point for this sort of thing. To quote from the article:




            [Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster
            than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.





            As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").






            share|cite|improve this answer











            $endgroup$



            Everything computable in the quantum sense is also computable in the standard sense, so you don't get any new power that way. On the complexity side, things are more interesting, but not (yet) as drastic as one might expect: it is still open, for example, whether a quantum computer can solve NP-complete (in the usual sense) problems in polynomial time. "Quantum speedup," such as we have so far, is due to structural properties of the problem in question (e.g. factoring) which general problems in NP do not have (as far as we know).



            This article by Aaronson is a good starting point for this sort of thing. To quote from the article:




            [Quantum computers] would solve certain specific problems, such as factoring integers, dramatically faster
            than we know how to solve them with today’s computers, but analysis suggests that for most problems quantum computers would surpass conventional ones only slightly. [...] A quantum algorithm capable of solving NP-complete problems efficiently would, like Shor’s algorithm, have to exploit the problems’ structure.





            As an aside, though, we need to be careful when we talk about "quantum computers." If we're just talking about computation which somehow uses quantum mechanics, this is a wildly-underdetermined notion: certainly very weird laws of physics could in principle allow us to build computers which lean on quantum phenomena somehow for huge computational power (including beyond classical computability). That seems wildly implausible though. There is an axiomatic notion of quantum computation, however, which so far matches what we know about quantum physics, and with respect to which we can in fact prove impossibility results (e.g. "everything quantum computable is classically computable").







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited 7 hours ago

























            answered 7 hours ago









            Noah SchweberNoah Schweber

            142k10 gold badges173 silver badges327 bronze badges




            142k10 gold badges173 silver badges327 bronze badges










            • 1




              $begingroup$
              To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
              $endgroup$
              – Derek Elkins
              6 hours ago













            • 1




              $begingroup$
              To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
              $endgroup$
              – Derek Elkins
              6 hours ago








            1




            1




            $begingroup$
            To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
            $endgroup$
            – Derek Elkins
            6 hours ago





            $begingroup$
            To be clear, as spaceisdarkgreen states, even if quantum computers could solve NP-complete problems (precisely, if BQP contained NP), this would not resolve P = NP. That said, there would probably be a massive surge of interest in quantum computers at that point.
            $endgroup$
            – Derek Elkins
            6 hours ago














            2














            $begingroup$

            Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.



            However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.






            share|cite|improve this answer











            $endgroup$



















              2














              $begingroup$

              Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.



              However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.






              share|cite|improve this answer











              $endgroup$

















                2














                2










                2







                $begingroup$

                Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.



                However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.






                share|cite|improve this answer











                $endgroup$



                Quantum computers don't give you any new computable functions, so they certainly can't solve the halting problem in the sense of there being a quantum algorithm that can decide if an arbitrary classical algorithm halts. P vs NP is a sharp mathematical problem about classical computation so QC can't really have any bearing on that problem per se.



                However, quantum computers do give new algorithms, and there are several well-known problems where the fastest known quantum algorithm is faster than the fastest known classical algorithm. (By "fast" here, I mean in terms of asymptotic time complexity). So a question related to P=NP that would make sense would be if any NP-hard problems can be solved in polynomial time by a quantum computer. The answer is that we don't know. The most famous polynomial time quantum algorithm, Shor's algorithm, solves the prime factorization problem in polynomial time whereas there is no known classical algorithm that does this. However, prime factorization is not known to be NP-complete, and expert consensus is that it is probably not.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited 7 hours ago

























                answered 7 hours ago









                spaceisdarkgreenspaceisdarkgreen

                37.6k2 gold badges22 silver badges59 bronze badges




                37.6k2 gold badges22 silver badges59 bronze badges































                    draft saved

                    draft discarded















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid


                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.

                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3373541%2fcould-quantum-computing-help-resolve-some-computability-problems-like-p-vs-np-or%23new-answer', 'question_page');

                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

                    Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

                    Ласкавець круглолистий Зміст Опис | Поширення | Галерея | Примітки | Посилання | Навігаційне меню58171138361-22960890446Bupleurum rotundifoliumEuro+Med PlantbasePlants of the World Online — Kew ScienceGermplasm Resources Information Network (GRIN)Ласкавецькн. VI : Літери Ком — Левиправивши або дописавши її