Could quantum computing help resolve some computability problems like p vs np or the halting problem?Let $Q$...
Does every Ubuntu question answer apply to it's derivatives? (Xubuntu, Lubuntu, Kubuntu)
Would Great Old Ones care about the Blood War?
Can 35 mm film which went through a washing machine still be developed?
Dotted footnote rule
Can I pay off my mortgage with a new one?
Is "Ram married his daughter" ambiguous?
Is Zhent just the term for any member of the Zhentarim?
How do we know for sure a transliteration is lossless?
In 1700s, why was 'books that never read' grammatical?
Injection from two strings to one string
Would we have more than 8 minutes of light, if the sun "went out"?
How does case-insensitive collation work?
As a girl, how can I voice male characters effectively?
Should I be able to see patterns in a HS256 encoded JWT?
Object Oriented Design: Where to place behavior that pertains to more than one type of object?
Are there any tricks to pushing a grand piano?
Should I reveal productivity tricks to peers?
How fast are we moving relative to the CMB?
Minimum perfect squares needed to sum up to a target
Redirect output on-the-fly - looks not possible in Linux, why?
What’s the BrE for “shotgun wedding”?
Is right click on tables bad UX
Can/should you swim in zero G?
I've been fired, was allowed to announce it as if I quit and given extra notice, how to handle the questions?
Could quantum computing help resolve some computability problems like p vs np or the halting problem?
Let $Q$ be an undecidable subset of $mathbb{N}$ 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;
}
.everyonelovesstackoverflow{position: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
