Quantum Finite Multitape Automata View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Andris Ambainis , Richard Bonner , Rūsiņš Freivalds , Marats Golovkins , Marek Karpinski

ABSTRACT

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4],and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] prove that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages. More... »

PAGES

340-348

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-47849-3_21

DOI

http://dx.doi.org/10.1007/3-540-47849-3_21

DIMENSIONS

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


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/02", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Physical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California, 94720-2320, Berkeley, CA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, 94720-2320, Berkeley, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ambainis", 
        "givenName": "Andris", 
        "id": "sg:person.013055041521.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013055041521.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Physics, M\u00e4lardalens University, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.411579.f", 
          "name": [
            "Department of Mathematics and Physics, M\u00e4lardalens University, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonner", 
        "givenName": "Richard", 
        "id": "sg:person.015573353607.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015573353607.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics and Computer Science, University of Latvia, Rai\u0146a bulv. 29, Riga, Latvia", 
          "id": "http://www.grid.ac/institutes/grid.9845.0", 
          "name": [
            "Institute of Mathematics and Computer Science, University of Latvia, Rai\u0146a bulv. 29, Riga, Latvia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "id": "sg:person.014644001541.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644001541.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics and Computer Science, University of Latvia, Rai\u0146a bulv. 29, Riga, Latvia", 
          "id": "http://www.grid.ac/institutes/grid.9845.0", 
          "name": [
            "Institute of Mathematics and Computer Science, University of Latvia, Rai\u0146a bulv. 29, Riga, Latvia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Golovkins", 
        "givenName": "Marats", 
        "id": "sg:person.011254660331.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011254660331.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Bonn, 53117, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Department of Computer Science, University of Bonn, 53117, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4],and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] prove that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.", 
    "editor": [
      {
        "familyName": "Pavelka", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Tel", 
        "givenName": "Gerard", 
        "type": "Person"
      }, 
      {
        "familyName": "Barto\u0161ek", 
        "givenName": "Miroslav", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-47849-3_21", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66694-3", 
        "978-3-540-47849-2"
      ], 
      "name": "SOFSEM\u201999: Theory and Practice of Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "quantum finite automata", 
      "quantum computer", 
      "first results", 
      "probabilistic computers", 
      "probabilistic finite automata", 
      "Ambainis", 
      "Watrous", 
      "computer", 
      "results", 
      "generalization", 
      "paper", 
      "C. Moore", 
      "Moore", 
      "problem", 
      "automata", 
      "Crutchfield", 
      "notion", 
      "concise", 
      "finite automata", 
      "deterministic finite automata", 
      "probabilistic automata", 
      "complicated language", 
      "language", 
      "regular languages", 
      "Freivalds", 
      "multitape automata", 
      "Kondacs"
    ], 
    "name": "Quantum Finite Multitape Automata", 
    "pagination": "340-348", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015618128"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-47849-3_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-47849-3_21", 
      "https://app.dimensions.ai/details/publication/pub.1015618128"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_472.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-47849-3_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/3-540-47849-3_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/3-540-47849-3_21'

Turtle is a human-readable linked data format.

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

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

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


 

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

133 TRIPLES      22 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-47849-3_21 schema:about anzsrc-for:02
2 anzsrc-for:0206
3 schema:author N21e4c7328a6c41cd9a42516e0077eee0
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4],and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] prove that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.
7 schema:editor Na25c246c52974a70af785ffdf021c9ed
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N69cdd071727341d7aaf70c7572c5fa0f
11 schema:keywords Ambainis
12 C. Moore
13 Crutchfield
14 Freivalds
15 Kondacs
16 Moore
17 Watrous
18 automata
19 complicated language
20 computer
21 concise
22 deterministic finite automata
23 finite automata
24 first results
25 generalization
26 language
27 multitape automata
28 notion
29 paper
30 probabilistic automata
31 probabilistic computers
32 probabilistic finite automata
33 problem
34 quantum computer
35 quantum finite automata
36 regular languages
37 results
38 schema:name Quantum Finite Multitape Automata
39 schema:pagination 340-348
40 schema:productId N97c8e1485d3d4f1bb70944828cdabef5
41 Na0584e9a619945c6968d260219c2bf51
42 schema:publisher N33ac53657e0d4a9c9fb90a022f8e5f37
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015618128
44 https://doi.org/10.1007/3-540-47849-3_21
45 schema:sdDatePublished 2022-12-01T06:54
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher Ne7f14463965c457a85f8b3fe231bb58d
48 schema:url https://doi.org/10.1007/3-540-47849-3_21
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N1d8b60153af5498f8a92fdc1582ff90a schema:familyName Bartošek
53 schema:givenName Miroslav
54 rdf:type schema:Person
55 N21e4c7328a6c41cd9a42516e0077eee0 rdf:first sg:person.013055041521.26
56 rdf:rest N60300a22749a4977bb73cd78e93c5100
57 N32bc3359355845508fca1ad50666f244 rdf:first sg:person.014644001541.17
58 rdf:rest N4d3f492142454ce0a28223326cb9bdb4
59 N33ac53657e0d4a9c9fb90a022f8e5f37 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N4d3f492142454ce0a28223326cb9bdb4 rdf:first sg:person.011254660331.28
62 rdf:rest N5162585280c74ba8b4a9adf4b17a68d4
63 N5162585280c74ba8b4a9adf4b17a68d4 rdf:first sg:person.011636042271.02
64 rdf:rest rdf:nil
65 N5386967955264af8892fb25d8c3f6e09 schema:familyName Tel
66 schema:givenName Gerard
67 rdf:type schema:Person
68 N5ebbdf240666481ca6dfefe574da9a46 rdf:first N1d8b60153af5498f8a92fdc1582ff90a
69 rdf:rest rdf:nil
70 N60300a22749a4977bb73cd78e93c5100 rdf:first sg:person.015573353607.26
71 rdf:rest N32bc3359355845508fca1ad50666f244
72 N69cdd071727341d7aaf70c7572c5fa0f schema:isbn 978-3-540-47849-2
73 978-3-540-66694-3
74 schema:name SOFSEM’99: Theory and Practice of Informatics
75 rdf:type schema:Book
76 N7d8e83db2750468583694b13a4a3bea0 rdf:first N5386967955264af8892fb25d8c3f6e09
77 rdf:rest N5ebbdf240666481ca6dfefe574da9a46
78 N97c8e1485d3d4f1bb70944828cdabef5 schema:name dimensions_id
79 schema:value pub.1015618128
80 rdf:type schema:PropertyValue
81 Na0584e9a619945c6968d260219c2bf51 schema:name doi
82 schema:value 10.1007/3-540-47849-3_21
83 rdf:type schema:PropertyValue
84 Na25c246c52974a70af785ffdf021c9ed rdf:first Nc977efeff4b344e1baaa027bcefeacb7
85 rdf:rest N7d8e83db2750468583694b13a4a3bea0
86 Nc977efeff4b344e1baaa027bcefeacb7 schema:familyName Pavelka
87 schema:givenName Jan
88 rdf:type schema:Person
89 Ne7f14463965c457a85f8b3fe231bb58d schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
92 schema:name Physical Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
95 schema:name Quantum Physics
96 rdf:type schema:DefinedTerm
97 sg:person.011254660331.28 schema:affiliation grid-institutes:grid.9845.0
98 schema:familyName Golovkins
99 schema:givenName Marats
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011254660331.28
101 rdf:type schema:Person
102 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
103 schema:familyName Karpinski
104 schema:givenName Marek
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
106 rdf:type schema:Person
107 sg:person.013055041521.26 schema:affiliation grid-institutes:grid.47840.3f
108 schema:familyName Ambainis
109 schema:givenName Andris
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013055041521.26
111 rdf:type schema:Person
112 sg:person.014644001541.17 schema:affiliation grid-institutes:grid.9845.0
113 schema:familyName Freivalds
114 schema:givenName Rūsiņš
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644001541.17
116 rdf:type schema:Person
117 sg:person.015573353607.26 schema:affiliation grid-institutes:grid.411579.f
118 schema:familyName Bonner
119 schema:givenName Richard
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015573353607.26
121 rdf:type schema:Person
122 grid-institutes:grid.10388.32 schema:alternateName Department of Computer Science, University of Bonn, 53117, Bonn, Germany
123 schema:name Department of Computer Science, University of Bonn, 53117, Bonn, Germany
124 rdf:type schema:Organization
125 grid-institutes:grid.411579.f schema:alternateName Department of Mathematics and Physics, Mälardalens University, Sweden
126 schema:name Department of Mathematics and Physics, Mälardalens University, Sweden
127 rdf:type schema:Organization
128 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California, 94720-2320, Berkeley, CA
129 schema:name Computer Science Division, University of California, 94720-2320, Berkeley, CA
130 rdf:type schema:Organization
131 grid-institutes:grid.9845.0 schema:alternateName Institute of Mathematics and Computer Science, University of Latvia, Raiņa bulv. 29, Riga, Latvia
132 schema:name Institute of Mathematics and Computer Science, University of Latvia, Raiņa bulv. 29, Riga, Latvia
133 rdf:type schema:Organization
 




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


...