Quantum Algorithm for Hilbert's Tenth Problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2003-07

AUTHORS

Tien D Kieu

ABSTRACT

We explore in the framework of Quantum Computation the notion of Computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm for Hilbert's tenth problem, which is equivalent to the Turing halting problem and is known to be mathematically noncomputable, is proposed where quantum continuous variables and quantum adiabatic evolution are employed. If this algorithm could be physically implemented, as much as it is valid in principle—that is, if certain Hamiltonian and its ground state can be physically constructed according to the proposal—quantum computability would surpass classical computability as delimited by the Church—Turing thesis. It is thus argued that computability, and with it the limits of Mathematics, ought to be determined not solely by Mathematics itself but also by Physical Principles. More... »

PAGES

1461-1478

References to SciGraph publications

  • 1980-05. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines in JOURNAL OF STATISTICAL PHYSICS
  • 2002-02. Non-Turing Computations Via Malament–Hogarth Space-Times in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1982-06. Simulating physics with computers in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 1982-10. A single quantum cannot be cloned in NATURE
  • 2002-04. Coins, Quantum Measurements, and Turing's Barrier in QUANTUM INFORMATION PROCESSING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1025780028846

    DOI

    http://dx.doi.org/10.1023/a:1025780028846

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1035231626


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Swinburne University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.1027.4", 
              "name": [
                "Centre for Atom Optics and Ultrafast Spectroscopy, Swinburne University of Technology, 3122, Hawthorn, Australia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kieu", 
            "givenName": "Tien D", 
            "id": "sg:person.010545077206.50", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545077206.50"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1103/physrevlett.79.325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002540107"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.79.325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002540107"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/299802a0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005824196", 
              "https://doi.org/10.1038/299802a0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01011339", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008923572", 
              "https://doi.org/10.1007/bf01011339"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1117/12.486889", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013001173"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1014019225365", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018112119", 
              "https://doi.org/10.1023/a:1014019225365"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.80.4084", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019121306"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.80.4084", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019121306"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1019623616675", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026683677", 
              "https://doi.org/10.1023/a:1019623616675"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.82.1784", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033134351"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.82.1784", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033134351"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.58.5355", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034364415"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.58.5355", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034364415"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02650179", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038336282", 
              "https://doi.org/10.1007/bf02650179"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.79.2915", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040092639"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.79.2915", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040092639"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreva.65.012322", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041261854"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreva.65.012322", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041261854"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00107510302712", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049556375"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539795293172", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880065"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539796300921", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880100"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003-07", 
        "datePublishedReg": "2003-07-01", 
        "description": "We explore in the framework of Quantum Computation the notion of Computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm for Hilbert's tenth problem, which is equivalent to the Turing halting problem and is known to be mathematically noncomputable, is proposed where quantum continuous variables and quantum adiabatic evolution are employed. If this algorithm could be physically implemented, as much as it is valid in principle\u2014that is, if certain Hamiltonian and its ground state can be physically constructed according to the proposal\u2014quantum computability would surpass classical computability as delimited by the Church\u2014Turing thesis. It is thus argued that computability, and with it the limits of Mathematics, ought to be determined not solely by Mathematics itself but also by Physical Principles.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1025780028846", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053677", 
            "issn": [
              "0020-7748", 
              "1572-9575"
            ], 
            "name": "International Journal of Theoretical Physics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "7", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "42"
          }
        ], 
        "name": "Quantum Algorithm for Hilbert's Tenth Problem", 
        "pagination": "1461-1478", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a7d3ca22bbda3f31e562ee8159e0d4fdc5ba50e6d2b283418dcdf8631120159c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1025780028846"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035231626"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1025780028846", 
          "https://app.dimensions.ai/details/publication/pub.1035231626"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T21:35", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8687_00000506.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FA%3A1025780028846"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1025780028846'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1025780028846'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1025780028846'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1025780028846'


     

    This table displays all metadata directly associated to this object as RDF triples.

    111 TRIPLES      21 PREDICATES      42 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1025780028846 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N730a8fce4163441fbc351bfa44960ff4
    4 schema:citation sg:pub.10.1007/bf01011339
    5 sg:pub.10.1007/bf02650179
    6 sg:pub.10.1023/a:1014019225365
    7 sg:pub.10.1023/a:1019623616675
    8 sg:pub.10.1038/299802a0
    9 https://doi.org/10.1080/00107510302712
    10 https://doi.org/10.1103/physreva.65.012322
    11 https://doi.org/10.1103/physreve.58.5355
    12 https://doi.org/10.1103/physrevlett.79.2915
    13 https://doi.org/10.1103/physrevlett.79.325
    14 https://doi.org/10.1103/physrevlett.80.4084
    15 https://doi.org/10.1103/physrevlett.82.1784
    16 https://doi.org/10.1117/12.486889
    17 https://doi.org/10.1137/s0097539795293172
    18 https://doi.org/10.1137/s0097539796300921
    19 schema:datePublished 2003-07
    20 schema:datePublishedReg 2003-07-01
    21 schema:description We explore in the framework of Quantum Computation the notion of Computability, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm for Hilbert's tenth problem, which is equivalent to the Turing halting problem and is known to be mathematically noncomputable, is proposed where quantum continuous variables and quantum adiabatic evolution are employed. If this algorithm could be physically implemented, as much as it is valid in principle—that is, if certain Hamiltonian and its ground state can be physically constructed according to the proposal—quantum computability would surpass classical computability as delimited by the Church—Turing thesis. It is thus argued that computability, and with it the limits of Mathematics, ought to be determined not solely by Mathematics itself but also by Physical Principles.
    22 schema:genre research_article
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N7a2f729b22e8415588b7343579d8f50d
    26 Nef4cd75c14b74ffcb4df0ae282655196
    27 sg:journal.1053677
    28 schema:name Quantum Algorithm for Hilbert's Tenth Problem
    29 schema:pagination 1461-1478
    30 schema:productId N33a53ad54c394870ba8bc005f0a9dcf1
    31 N8b9d3dbc5f15414898b0a073b76f40ef
    32 Nadc22115ced54e589608975937c963f0
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035231626
    34 https://doi.org/10.1023/a:1025780028846
    35 schema:sdDatePublished 2019-04-10T21:35
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nf2e5f2e21ae54943ad34a54406e3156b
    38 schema:url http://link.springer.com/10.1023%2FA%3A1025780028846
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset articles
    41 rdf:type schema:ScholarlyArticle
    42 N33a53ad54c394870ba8bc005f0a9dcf1 schema:name readcube_id
    43 schema:value a7d3ca22bbda3f31e562ee8159e0d4fdc5ba50e6d2b283418dcdf8631120159c
    44 rdf:type schema:PropertyValue
    45 N730a8fce4163441fbc351bfa44960ff4 rdf:first sg:person.010545077206.50
    46 rdf:rest rdf:nil
    47 N7a2f729b22e8415588b7343579d8f50d schema:issueNumber 7
    48 rdf:type schema:PublicationIssue
    49 N8b9d3dbc5f15414898b0a073b76f40ef schema:name doi
    50 schema:value 10.1023/a:1025780028846
    51 rdf:type schema:PropertyValue
    52 Nadc22115ced54e589608975937c963f0 schema:name dimensions_id
    53 schema:value pub.1035231626
    54 rdf:type schema:PropertyValue
    55 Nef4cd75c14b74ffcb4df0ae282655196 schema:volumeNumber 42
    56 rdf:type schema:PublicationVolume
    57 Nf2e5f2e21ae54943ad34a54406e3156b schema:name Springer Nature - SN SciGraph project
    58 rdf:type schema:Organization
    59 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Mathematical Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Pure Mathematics
    64 rdf:type schema:DefinedTerm
    65 sg:journal.1053677 schema:issn 0020-7748
    66 1572-9575
    67 schema:name International Journal of Theoretical Physics
    68 rdf:type schema:Periodical
    69 sg:person.010545077206.50 schema:affiliation https://www.grid.ac/institutes/grid.1027.4
    70 schema:familyName Kieu
    71 schema:givenName Tien D
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545077206.50
    73 rdf:type schema:Person
    74 sg:pub.10.1007/bf01011339 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008923572
    75 https://doi.org/10.1007/bf01011339
    76 rdf:type schema:CreativeWork
    77 sg:pub.10.1007/bf02650179 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038336282
    78 https://doi.org/10.1007/bf02650179
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1023/a:1014019225365 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018112119
    81 https://doi.org/10.1023/a:1014019225365
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1023/a:1019623616675 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026683677
    84 https://doi.org/10.1023/a:1019623616675
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1038/299802a0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005824196
    87 https://doi.org/10.1038/299802a0
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1080/00107510302712 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049556375
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1103/physreva.65.012322 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041261854
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1103/physreve.58.5355 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034364415
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1103/physrevlett.79.2915 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040092639
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1103/physrevlett.79.325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002540107
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1103/physrevlett.80.4084 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019121306
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1103/physrevlett.82.1784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033134351
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1117/12.486889 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013001173
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1137/s0097539795293172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880065
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1137/s0097539796300921 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880100
    108 rdf:type schema:CreativeWork
    109 https://www.grid.ac/institutes/grid.1027.4 schema:alternateName Swinburne University of Technology
    110 schema:name Centre for Atom Optics and Ultrafast Spectroscopy, Swinburne University of Technology, 3122, Hawthorn, Australia
    111 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...