Quantum Algorithms for Evaluating Min-Max Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Richard Cleve , Dmitry Gavinsky , D. L. Yonge-Mallo

ABSTRACT

We present a bounded-error quantum algorithm for evaluating Min-Max trees with queries, where N is the size of the tree and where the allowable queries are comparisons of the form [xj < xk]. This is close to tight, since there is a known quantum lower bound of .

PAGES

11-15

Book

TITLE

Theory of Quantum Computation, Communication, and Cryptography

ISBN

978-3-540-89303-5
978-3-540-89304-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-89304-2_2

DOI

http://dx.doi.org/10.1007/978-3-540-89304-2_2

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Perimeter Institute", 
          "id": "https://www.grid.ac/institutes/grid.420198.6", 
          "name": [
            "David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo, Canada", 
            "Perimeter Institute for Theoretical Physics, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cleve", 
        "givenName": "Richard", 
        "id": "sg:person.01107130536.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01107130536.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gavinsky", 
        "givenName": "Dmitry", 
        "id": "sg:person.07441567631.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07441567631.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yonge-Mallo", 
        "givenName": "D. L.", 
        "id": "sg:person.01117203011.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01117203011.20"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.jcss.2004.02.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004407936"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026820361"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/237814.237866", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053319325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539796300933", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880101"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1986.44", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086230642"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "We present a bounded-error quantum algorithm for evaluating Min-Max trees with queries, where N is the size of the tree and where the allowable queries are comparisons of the form [xj < xk]. This is close to tight, since there is a known quantum lower bound of .", 
    "editor": [
      {
        "familyName": "Kawano", 
        "givenName": "Yasuhito", 
        "type": "Person"
      }, 
      {
        "familyName": "Mosca", 
        "givenName": "Michele", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-89304-2_2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-89303-5", 
        "978-3-540-89304-2"
      ], 
      "name": "Theory of Quantum Computation, Communication, and Cryptography", 
      "type": "Book"
    }, 
    "name": "Quantum Algorithms for Evaluating Min-Max Trees", 
    "pagination": "11-15", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-89304-2_2"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ba687d2e3f448780490054c04ae2e9f2e5eb30a9d7c5cc493019b1e224204dc8"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039132676"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-89304-2_2", 
      "https://app.dimensions.ai/details/publication/pub.1039132676"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T06:09", 
    "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/0000000350_0000000350/records_77561_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-89304-2_2"
  }
]
 

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-89304-2_2'

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-89304-2_2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-89304-2_2'

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-89304-2_2'


 

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

95 TRIPLES      22 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-89304-2_2 schema:author Nf6bab2ee89014010b2044b9260df1b0d
2 schema:citation https://doi.org/10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
3 https://doi.org/10.1016/j.jcss.2004.02.002
4 https://doi.org/10.1109/sfcs.1986.44
5 https://doi.org/10.1137/s0097539796300933
6 https://doi.org/10.1145/237814.237866
7 schema:datePublished 2008
8 schema:datePublishedReg 2008-01-01
9 schema:description We present a bounded-error quantum algorithm for evaluating Min-Max trees with queries, where N is the size of the tree and where the allowable queries are comparisons of the form [xj < xk]. This is close to tight, since there is a known quantum lower bound of .
10 schema:editor Nd3e0014a7dd44bf7916251bb69f085a9
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree true
14 schema:isPartOf Ne0fe5f638ca74fb4a1f69ffc3caf314f
15 schema:name Quantum Algorithms for Evaluating Min-Max Trees
16 schema:pagination 11-15
17 schema:productId N60ffab0c90a643908b67d285953904b7
18 N852e862984d344b79c72e43238d9e73e
19 N88b6d2dfbc8c44448c9e5a67c4160c4e
20 schema:publisher Nc3ca0ae391634ce8a98daf28cd9c0cf2
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039132676
22 https://doi.org/10.1007/978-3-540-89304-2_2
23 schema:sdDatePublished 2019-04-16T06:09
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher N46b9d71e0ee24d828ab5510680e029ac
26 schema:url https://link.springer.com/10.1007%2F978-3-540-89304-2_2
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N136346776bf94b48b00a73e21f7b2916 schema:familyName Kawano
31 schema:givenName Yasuhito
32 rdf:type schema:Person
33 N3f53ec08a7664bb4a715f2157af1279a rdf:first sg:person.07441567631.32
34 rdf:rest Nd8f061529a9b4dd69ab863461f957644
35 N46b9d71e0ee24d828ab5510680e029ac schema:name Springer Nature - SN SciGraph project
36 rdf:type schema:Organization
37 N4c72e74635604780abe754a50de54c94 schema:familyName Mosca
38 schema:givenName Michele
39 rdf:type schema:Person
40 N60ffab0c90a643908b67d285953904b7 schema:name dimensions_id
41 schema:value pub.1039132676
42 rdf:type schema:PropertyValue
43 N852e862984d344b79c72e43238d9e73e schema:name readcube_id
44 schema:value ba687d2e3f448780490054c04ae2e9f2e5eb30a9d7c5cc493019b1e224204dc8
45 rdf:type schema:PropertyValue
46 N88b6d2dfbc8c44448c9e5a67c4160c4e schema:name doi
47 schema:value 10.1007/978-3-540-89304-2_2
48 rdf:type schema:PropertyValue
49 Nc3ca0ae391634ce8a98daf28cd9c0cf2 schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 Nd3e0014a7dd44bf7916251bb69f085a9 rdf:first N136346776bf94b48b00a73e21f7b2916
53 rdf:rest Neb00ef5392114381bf692e20c6f00a89
54 Nd8f061529a9b4dd69ab863461f957644 rdf:first sg:person.01117203011.20
55 rdf:rest rdf:nil
56 Ne0fe5f638ca74fb4a1f69ffc3caf314f schema:isbn 978-3-540-89303-5
57 978-3-540-89304-2
58 schema:name Theory of Quantum Computation, Communication, and Cryptography
59 rdf:type schema:Book
60 Neb00ef5392114381bf692e20c6f00a89 rdf:first N4c72e74635604780abe754a50de54c94
61 rdf:rest rdf:nil
62 Nf6bab2ee89014010b2044b9260df1b0d rdf:first sg:person.01107130536.64
63 rdf:rest N3f53ec08a7664bb4a715f2157af1279a
64 sg:person.01107130536.64 schema:affiliation https://www.grid.ac/institutes/grid.420198.6
65 schema:familyName Cleve
66 schema:givenName Richard
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01107130536.64
68 rdf:type schema:Person
69 sg:person.01117203011.20 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
70 schema:familyName Yonge-Mallo
71 schema:givenName D. L.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01117203011.20
73 rdf:type schema:Person
74 sg:person.07441567631.32 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
75 schema:familyName Gavinsky
76 schema:givenName Dmitry
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07441567631.32
78 rdf:type schema:Person
79 https://doi.org/10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p schema:sameAs https://app.dimensions.ai/details/publication/pub.1026820361
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/j.jcss.2004.02.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004407936
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1109/sfcs.1986.44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086230642
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1137/s0097539796300933 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880101
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/237814.237866 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053319325
88 rdf:type schema:CreativeWork
89 https://www.grid.ac/institutes/grid.420198.6 schema:alternateName Perimeter Institute
90 schema:name David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo, Canada
91 Perimeter Institute for Theoretical Physics, Canada
92 rdf:type schema:Organization
93 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
94 schema:name David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo, Canada
95 rdf:type schema:Organization
 




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


...