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;
$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.
logic
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
$endgroup$
add a comment
|
$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.
logic
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
$endgroup$
add a comment
|
$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.
logic
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
$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
logic
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
asked 8 hours ago
Leo KovacicLeo Kovacic
213 bronze badges
213 bronze badges
add a comment
|
add a comment
|
2 Answers
2
active
oldest
votes
$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").
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
$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
add a comment
|
$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.
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
$endgroup$
add a comment
|
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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").
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
$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
add a comment
|
$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").
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
$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
add a comment
|
$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").
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
$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").
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
edited 7 hours ago
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
answered 7 hours ago
Noah SchweberNoah Schweber
142k10 gold badges173 silver badges327 bronze badges
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
add a comment
|
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
add a comment
|
$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.
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
$endgroup$
add a comment
|
$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.
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
$endgroup$
add a comment
|
$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.
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
$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.
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
edited 7 hours ago
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
answered 7 hours ago
spaceisdarkgreenspaceisdarkgreen
37.6k2 gold badges22 silver badges59 bronze badges
37.6k2 gold badges22 silver badges59 bronze badges
add a comment
|
add a comment
|
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
