On Computational Power of Quantum Branching Programs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001-08-02

AUTHORS

Farid Ablayev , Aida Gainutdinova , Marek Karpinski

ABSTRACT

In this paper we introduce a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2n), contrary to the analogous situation for quantum finite automata. Further we display certain symmetric Boolean function which is computable by a read-once QBP with O(logn) width, which requires a width Ω(n) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions in each levels.We present a general lower bound for the width of read-once QBPs, showing that the upper bound for the considered symmetric function is almost tight. More... »

PAGES

59-70

Book

TITLE

Fundamentals of Computation Theory

ISBN

978-3-540-42487-1
978-3-540-44669-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44669-9_8

DOI

http://dx.doi.org/10.1007/3-540-44669-9_8

DIMENSIONS

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


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": "Dept. of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Theoretical Cybernetics of Kazan State University, 420008, Kazan, Russia", 
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ablayev", 
        "givenName": "Farid", 
        "id": "sg:person.07505156746.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07505156746.84"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Theoretical Cybernetics of Kazan State University, 420008, Kazan, Russia", 
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gainutdinova", 
        "givenName": "Aida", 
        "id": "sg:person.011037106067.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037106067.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, 53117, Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Theoretical Cybernetics of Kazan State University, 420008, Kazan, Russia", 
            "Dept. of Computer Science, University of Bonn, 53117, Bonn"
          ], 
          "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": "2001-08-02", 
    "datePublishedReg": "2001-08-02", 
    "description": "In this paper we introduce a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2n), contrary to the analogous situation for quantum finite automata. Further we display certain symmetric Boolean function which is computable by a read-once QBP with O(logn) width, which requires a width \u03a9(n) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions in each levels.We present a general lower bound for the width of read-once QBPs, showing that the upper bound for the considered symmetric function is almost tight.", 
    "editor": [
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44669-9_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42487-1", 
        "978-3-540-44669-9"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "quantum branching programs", 
      "computational power", 
      "quantum finite automata", 
      "branching programs", 
      "quantum nature", 
      "natural restrictions", 
      "symmetric functions", 
      "Boolean functions", 
      "symmetric Boolean functions", 
      "finite automata", 
      "analogous situation", 
      "model", 
      "width", 
      "function", 
      "automata", 
      "power", 
      "permanent transition", 
      "transition", 
      "restriction", 
      "situation", 
      "nature", 
      "program", 
      "reads", 
      "obliviousness", 
      "levels", 
      "such programs", 
      "paper", 
      "BP"
    ], 
    "name": "On Computational Power of Quantum Branching Programs", 
    "pagination": "59-70", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028028013"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44669-9_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44669-9_8", 
      "https://app.dimensions.ai/details/publication/pub.1028028013"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "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_384.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44669-9_8"
  }
]
 

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-44669-9_8'

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-44669-9_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44669-9_8'

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-44669-9_8'


 

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

102 TRIPLES      22 PREDICATES      52 URIs      45 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44669-9_8 schema:about anzsrc-for:02
2 anzsrc-for:0206
3 schema:author Nd023b00f43c948cfb7ca89aec4c084aa
4 schema:datePublished 2001-08-02
5 schema:datePublishedReg 2001-08-02
6 schema:description In this paper we introduce a model of a Quantum Branching Program (QBP) and study its computational power. We define several natural restrictions of a general QBP model, such as a read-once and a read-k-times QBP, noting that obliviousness is inherent in a quantum nature of such programs.In particular we show that any Boolean function can be computed deterministically (exactly) by a read-once QBP in width O(2n), contrary to the analogous situation for quantum finite automata. Further we display certain symmetric Boolean function which is computable by a read-once QBP with O(logn) width, which requires a width Ω(n) on any deterministic read-once BP and (classical) randomized read-once BP with permanent transitions in each levels.We present a general lower bound for the width of read-once QBPs, showing that the upper bound for the considered symmetric function is almost tight.
7 schema:editor Nca6d345561f74ce3ae0f2635182bf9c6
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N6bb476a6cbed44168caa841e3468fc26
11 schema:keywords BP
12 Boolean functions
13 analogous situation
14 automata
15 branching programs
16 computational power
17 finite automata
18 function
19 levels
20 model
21 natural restrictions
22 nature
23 obliviousness
24 paper
25 permanent transition
26 power
27 program
28 quantum branching programs
29 quantum finite automata
30 quantum nature
31 reads
32 restriction
33 situation
34 such programs
35 symmetric Boolean functions
36 symmetric functions
37 transition
38 width
39 schema:name On Computational Power of Quantum Branching Programs
40 schema:pagination 59-70
41 schema:productId N0f68f01e84a847b897a413bf5f468cc4
42 N68d6574b8a854adaa6e152120ce05649
43 schema:publisher N4ac31c5b2a2a4520ad56c778f29cb818
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028028013
45 https://doi.org/10.1007/3-540-44669-9_8
46 schema:sdDatePublished 2022-12-01T06:52
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher Nfa6cd0600a754a2190da92979c035a1d
49 schema:url https://doi.org/10.1007/3-540-44669-9_8
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N0f68f01e84a847b897a413bf5f468cc4 schema:name dimensions_id
54 schema:value pub.1028028013
55 rdf:type schema:PropertyValue
56 N2545770624bf4c05a3664b67c28d6c74 schema:familyName Freivalds
57 schema:givenName Rūsiņš
58 rdf:type schema:Person
59 N4ac31c5b2a2a4520ad56c778f29cb818 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N68d6574b8a854adaa6e152120ce05649 schema:name doi
62 schema:value 10.1007/3-540-44669-9_8
63 rdf:type schema:PropertyValue
64 N6bb476a6cbed44168caa841e3468fc26 schema:isbn 978-3-540-42487-1
65 978-3-540-44669-9
66 schema:name Fundamentals of Computation Theory
67 rdf:type schema:Book
68 N95ed4d41864a47a384a730bff5887c57 rdf:first sg:person.011636042271.02
69 rdf:rest rdf:nil
70 N9f21c0ca33ac49fd82058edcea9f3361 rdf:first sg:person.011037106067.07
71 rdf:rest N95ed4d41864a47a384a730bff5887c57
72 Nca6d345561f74ce3ae0f2635182bf9c6 rdf:first N2545770624bf4c05a3664b67c28d6c74
73 rdf:rest rdf:nil
74 Nd023b00f43c948cfb7ca89aec4c084aa rdf:first sg:person.07505156746.84
75 rdf:rest N9f21c0ca33ac49fd82058edcea9f3361
76 Nfa6cd0600a754a2190da92979c035a1d schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
79 schema:name Physical Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
82 schema:name Quantum Physics
83 rdf:type schema:DefinedTerm
84 sg:person.011037106067.07 schema:affiliation grid-institutes:grid.10388.32
85 schema:familyName Gainutdinova
86 schema:givenName Aida
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011037106067.07
88 rdf:type schema:Person
89 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
90 schema:familyName Karpinski
91 schema:givenName Marek
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
93 rdf:type schema:Person
94 sg:person.07505156746.84 schema:affiliation grid-institutes:grid.10388.32
95 schema:familyName Ablayev
96 schema:givenName Farid
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07505156746.84
98 rdf:type schema:Person
99 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, 53117, Bonn
100 schema:name Dept. of Computer Science, University of Bonn, 53117, Bonn
101 Dept. of Theoretical Cybernetics of Kazan State University, 420008, Kazan, Russia
102 rdf:type schema:Organization
 




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


...