On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Masaki Nakanishi

ABSTRACT

One of important questions on quantum computing is whether there is a computational gap between the models that are allowed to use quantum effects and the models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with quantum pushdown stack). It has been shown that some quantum computation models are more powerful than classical counterparts and some are not since quantum computation models are required to obey some restrictions such as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stack is assumed to be implemented as a classical device, and show that they are strictly more powerful than classical counterparts in the one-sided error setting. That is, we show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with one-sided error. More... »

PAGES

179-187

References to SciGraph publications

  • 2000. Quantum Pushdown Automata in SOFSEM 2000: THEORY AND PRACTICE OF INFORMATICS
  • 1968-09. A helpful result for proving inherent ambiguity in MATHEMATICAL SYSTEMS THEORY
  • Book

    TITLE

    Computing and Combinatorics

    ISBN

    978-3-540-22856-1
    978-3-540-27798-9

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_21

    DOI

    http://dx.doi.org/10.1007/978-3-540-27798-9_21

    DIMENSIONS

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


    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/0206", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Quantum Physics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/02", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Physical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Nara Institute of Science and Technology", 
              "id": "https://www.grid.ac/institutes/grid.260493.a", 
              "name": [
                "Graduate School of Information Science, Nara Institute of Science and Technology, 8916\u20135, Takayama, Ikoma, 630\u20130101, Nara, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nakanishi", 
            "givenName": "Masaki", 
            "id": "sg:person.011732067351.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011732067351.04"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01694004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011041182", 
              "https://doi.org/10.1007/bf01694004"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44411-4_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019218823", 
              "https://doi.org/10.1007/3-540-44411-4_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(98)00191-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046566791"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00138-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053392383"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "One of important questions on quantum computing is whether there is a computational gap between the models that are allowed to use quantum effects and the models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with quantum pushdown stack). It has been shown that some quantum computation models are more powerful than classical counterparts and some are not since quantum computation models are required to obey some restrictions such as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stack is assumed to be implemented as a classical device, and show that they are strictly more powerful than classical counterparts in the one-sided error setting. That is, we show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with one-sided error.", 
        "editor": [
          {
            "familyName": "Chwa", 
            "givenName": "Kyung-Yong", 
            "type": "Person"
          }, 
          {
            "familyName": "Munro", 
            "givenName": "J. Ian J.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-27798-9_21", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-22856-1", 
            "978-3-540-27798-9"
          ], 
          "name": "Computing and Combinatorics", 
          "type": "Book"
        }, 
        "name": "On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations", 
        "pagination": "179-187", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045918953"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-27798-9_21"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "dabbb2221b888d33561821e900b7aae0119aeeca37597d214d48790e7d7a4447"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-27798-9_21", 
          "https://app.dimensions.ai/details/publication/pub.1045918953"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:18", 
        "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/0000000362_0000000362/records_87104_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-27798-9_21"
      }
    ]
     

    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.1007/978-3-540-27798-9_21'

    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.1007/978-3-540-27798-9_21'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_21'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_21'


     

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

    84 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-27798-9_21 schema:about anzsrc-for:02
    2 anzsrc-for:0206
    3 schema:author Nd0a7e694b3704a7cbd90f48a6a0b42ae
    4 schema:citation sg:pub.10.1007/3-540-44411-4_22
    5 sg:pub.10.1007/bf01694004
    6 https://doi.org/10.1016/s0304-3975(02)00138-x
    7 https://doi.org/10.1016/s0304-3975(98)00191-1
    8 schema:datePublished 2004
    9 schema:datePublishedReg 2004-01-01
    10 schema:description One of important questions on quantum computing is whether there is a computational gap between the models that are allowed to use quantum effects and the models that are not. Several types of quantum computation models have been proposed, including quantum finite automata and quantum pushdown automata (with quantum pushdown stack). It has been shown that some quantum computation models are more powerful than classical counterparts and some are not since quantum computation models are required to obey some restrictions such as reversible state transitions. In this paper, we investigate the power of quantum pushdown automata whose stack is assumed to be implemented as a classical device, and show that they are strictly more powerful than classical counterparts in the one-sided error setting. That is, we show that there is a non-context-free language which quantum pushdown automata with classical stack operations can recognize with one-sided error.
    11 schema:editor Neaf245e9626a48698a57101e8d250b5d
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N4a36e83deaa448a6ab22fb7f9f50f878
    16 schema:name On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations
    17 schema:pagination 179-187
    18 schema:productId N085228f6df174b8eb0499d33c5aeaf41
    19 N5150f744e714467598ef9d5242cc32a0
    20 Nf1621feb0eaa4a81b5485d2821a0a8e8
    21 schema:publisher N7ed2217dbbbc403a8e70c790011f7062
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045918953
    23 https://doi.org/10.1007/978-3-540-27798-9_21
    24 schema:sdDatePublished 2019-04-16T08:18
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher N539b277ad38a4b28b9ecdb52b0d51326
    27 schema:url https://link.springer.com/10.1007%2F978-3-540-27798-9_21
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N085228f6df174b8eb0499d33c5aeaf41 schema:name doi
    32 schema:value 10.1007/978-3-540-27798-9_21
    33 rdf:type schema:PropertyValue
    34 N4a36e83deaa448a6ab22fb7f9f50f878 schema:isbn 978-3-540-22856-1
    35 978-3-540-27798-9
    36 schema:name Computing and Combinatorics
    37 rdf:type schema:Book
    38 N5150f744e714467598ef9d5242cc32a0 schema:name readcube_id
    39 schema:value dabbb2221b888d33561821e900b7aae0119aeeca37597d214d48790e7d7a4447
    40 rdf:type schema:PropertyValue
    41 N539b277ad38a4b28b9ecdb52b0d51326 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N7ed2217dbbbc403a8e70c790011f7062 schema:location Berlin, Heidelberg
    44 schema:name Springer Berlin Heidelberg
    45 rdf:type schema:Organisation
    46 N851dbb8aa47b43529e1c01d63ee2b24d schema:familyName Munro
    47 schema:givenName J. Ian J.
    48 rdf:type schema:Person
    49 Ncc9187e642554596ac92d4c2d348978c schema:familyName Chwa
    50 schema:givenName Kyung-Yong
    51 rdf:type schema:Person
    52 Nd0a7e694b3704a7cbd90f48a6a0b42ae rdf:first sg:person.011732067351.04
    53 rdf:rest rdf:nil
    54 Neaf245e9626a48698a57101e8d250b5d rdf:first Ncc9187e642554596ac92d4c2d348978c
    55 rdf:rest Neee85a6247c049f5ab559b82158c232b
    56 Neee85a6247c049f5ab559b82158c232b rdf:first N851dbb8aa47b43529e1c01d63ee2b24d
    57 rdf:rest rdf:nil
    58 Nf1621feb0eaa4a81b5485d2821a0a8e8 schema:name dimensions_id
    59 schema:value pub.1045918953
    60 rdf:type schema:PropertyValue
    61 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Physical Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Quantum Physics
    66 rdf:type schema:DefinedTerm
    67 sg:person.011732067351.04 schema:affiliation https://www.grid.ac/institutes/grid.260493.a
    68 schema:familyName Nakanishi
    69 schema:givenName Masaki
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011732067351.04
    71 rdf:type schema:Person
    72 sg:pub.10.1007/3-540-44411-4_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019218823
    73 https://doi.org/10.1007/3-540-44411-4_22
    74 rdf:type schema:CreativeWork
    75 sg:pub.10.1007/bf01694004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011041182
    76 https://doi.org/10.1007/bf01694004
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1016/s0304-3975(02)00138-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1053392383
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1016/s0304-3975(98)00191-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046566791
    81 rdf:type schema:CreativeWork
    82 https://www.grid.ac/institutes/grid.260493.a schema:alternateName Nara Institute of Science and Technology
    83 schema:name Graduate School of Information Science, Nara Institute of Science and Technology, 8916–5, Takayama, Ikoma, 630–0101, Nara, Japan
    84 rdf:type schema:Organization
     




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


    ...