Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    A proof that P is strictly contained in BQP would not alo... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Skepticism
    HistoryEditSee Inverse

    A proof that P is strictly contained in BQP would not alone determine the bearing of quantum computation on the limits of feasible computation or on the Cobham-Edmonds thesis

    Modality & PossibilitySkepticism
    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    2 reasons against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.No polynomial-time quantum algorithms have been found for NP-complete problems on widely accepted quantum computation models
      ?

      Think about whether this reason is strong or weak

    • 2.There is considerable controversy about whether physical realizations of quantum models can be made sufficiently robust to reliably solve instances beyond classical hardware
      ?

      Think about whether this reason is strong or weak

    • 3.Empirical investigation beyond the theoretical proof would still be required
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.If P ⊊ BQP were proven, it would establish that physical quantum systems transcend Church-Turing thesis constraints on feasible computation.
      ?

      Think about whether this reason is strong or weak

    • 2.The Cobham-Edmonds thesis equates feasibility with polynomial-time computability, so any strict extension of P directly revises its scope.
      ?

      Think about whether this reason is strong or weak

    • 3.A formal containment proof carries normative weight for the thesis independent of engineering robustness concerns.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Deutsch and Penrose both argue quantum computation's theoretical model is itself a physical thesis about what nature permits, not merely mathematical.
      ?

      Think about whether this reason is strong or weak

    • 2.If P ⊊ BQP is provable, the proof presupposes a physically realizable model, collapsing the gap between theoretical and empirical investigation the claim assumes.
      ?

      Think about whether this reason is strong or weak

    Sign in or register to share your perspective on this statement.

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Topics

    SkepticismModality & Possibility

    Connections

    1 topic

    Truth & Knowledge3 linked

    Related

    A formal containment proof carries normative weight for the thesis independent o...Deutsch and Penrose both argue quantum computation's theoretical model is itself...Empirical investigation beyond the theoretical proof would still be requiredIf P ⊊ BQP is provable, the proof presupposes a physically realizable model, col...
    +4 moreShow less
    If P ⊊ BQP were proven, it would establish that physical quantum systems transce...No polynomial-time quantum algorithms have been found for NP-complete problems o...The Cobham-Edmonds thesis equates feasibility with polynomial-time computability...There is considerable controversy about whether physical realizations of quantum...

    Similar

    Even a proof that P is properly contained in BQP would not settle the ...92%Even a proof that P is a strict subset of BQP would not by itself sett...88%Even if P ⊊ BQP were proven, further empirical investigation would be ...82%There is considerable controversy about whether physical realizations ...76%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    It is thus also reasonable to ask how we might modify the definition of \(\mathfrak{N}\) so as to obtain a characterization of probabilistic algorithms which we might usefully employ. [33] This class can be most readily defined relative to a model of computation known as the probabilistic Turing machine \(\mathfrak{C}\). Such a device \(C\) has access to a random number generator which produces a new bit at each step in its computation but is otherwise like a conventional Turing machine. The act
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit