Polynomial Time Quantum Algorithm for Search Problem and Its Application View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2014

AUTHORS

Satoshi Iriyama , Masanori Ohya

ABSTRACT

The well known quantum algorithm for search problem is Grover’s one. However, its computational complexity is not a polynomial in the input. In this study, we propose a polynomial time quantum algorithm for it based on quantum binary search and an amplification process. This process can be written as a quantum Turing machine form, a so called generalized quantum Turing machine (GQTM). We introduce the definition of GQTM and its language classes. More... »

PAGES

172-183

Book

TITLE

Quantum Interaction

ISBN

978-3-642-54942-7
978-3-642-54943-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-54943-4_15

DOI

http://dx.doi.org/10.1007/978-3-642-54943-4_15

DIMENSIONS

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


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": "Tokyo University of Science", 
          "id": "https://www.grid.ac/institutes/grid.143643.7", 
          "name": [
            "Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Iriyama", 
        "givenName": "Satoshi", 
        "id": "sg:person.015760605365.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760605365.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tokyo University of Science", 
          "id": "https://www.grid.ac/institutes/grid.143643.7", 
          "name": [
            "Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ohya", 
        "givenName": "Masanori", 
        "id": "sg:person.013365420775.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013365420775.41"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0019-9958(84)80060-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014507492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(84)80060-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014507492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0034-4877(03)90002-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024115457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1088/1464-4266/5/6/015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059141466"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s1230161208000262", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063015498"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s1230161215500195", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063015685"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789812774491_0017", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096066220"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "The well known quantum algorithm for search problem is Grover\u2019s one. However, its computational complexity is not a polynomial in the input. In this study, we propose a polynomial time quantum algorithm for it based on quantum binary search and an amplification process. This process can be written as a quantum Turing machine form, a so called generalized quantum Turing machine (GQTM). We introduce the definition of GQTM and its language classes.", 
    "editor": [
      {
        "familyName": "Atmanspacher", 
        "givenName": "Harald", 
        "type": "Person"
      }, 
      {
        "familyName": "Haven", 
        "givenName": "Emmanuel", 
        "type": "Person"
      }, 
      {
        "familyName": "Kitto", 
        "givenName": "Kirsty", 
        "type": "Person"
      }, 
      {
        "familyName": "Raine", 
        "givenName": "Derek", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-54943-4_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-54942-7", 
        "978-3-642-54943-4"
      ], 
      "name": "Quantum Interaction", 
      "type": "Book"
    }, 
    "name": "Polynomial Time Quantum Algorithm for Search Problem and Its Application", 
    "pagination": "172-183", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-54943-4_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "be26220371f001a521c224d1f337d977361e4c4c3ab30bb54db0889ad6ed2348"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039917211"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-54943-4_15", 
      "https://app.dimensions.ai/details/publication/pub.1039917211"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T22:57", 
    "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_8695_00000268.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-54943-4_15"
  }
]
 

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-642-54943-4_15'

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-642-54943-4_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-54943-4_15'

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-642-54943-4_15'


 

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

105 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-54943-4_15 schema:about anzsrc-for:02
2 anzsrc-for:0206
3 schema:author N4d8cd5ef10d7421c93f1de7fd559660a
4 schema:citation https://doi.org/10.1016/s0019-9958(84)80060-1
5 https://doi.org/10.1016/s0034-4877(03)90002-4
6 https://doi.org/10.1088/1464-4266/5/6/015
7 https://doi.org/10.1142/9789812774491_0017
8 https://doi.org/10.1142/s1230161208000262
9 https://doi.org/10.1142/s1230161215500195
10 schema:datePublished 2014
11 schema:datePublishedReg 2014-01-01
12 schema:description The well known quantum algorithm for search problem is Grover’s one. However, its computational complexity is not a polynomial in the input. In this study, we propose a polynomial time quantum algorithm for it based on quantum binary search and an amplification process. This process can be written as a quantum Turing machine form, a so called generalized quantum Turing machine (GQTM). We introduce the definition of GQTM and its language classes.
13 schema:editor Nf01e01b2b9a74e7c987eb1db1789e013
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf Ncb96c6147837479a98de45b987b4fbd5
18 schema:name Polynomial Time Quantum Algorithm for Search Problem and Its Application
19 schema:pagination 172-183
20 schema:productId N8d696949915f4ba09c65244e70712819
21 Nb81797dbbc334ffebcf91178983bd2f3
22 Nf30084db7aa0401285f526b826df651c
23 schema:publisher N238d23be146949d6b068a8595c166f3e
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039917211
25 https://doi.org/10.1007/978-3-642-54943-4_15
26 schema:sdDatePublished 2019-04-15T22:57
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Ne3b448f5279146f79de696bc20143fd6
29 schema:url http://link.springer.com/10.1007/978-3-642-54943-4_15
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N14a59bfcd238408a81557504abd222d4 rdf:first Ncdaf28b50943481c93c8c6df0db0b045
34 rdf:rest rdf:nil
35 N17b8081529c141f28947a9a5c51a1fd9 schema:familyName Kitto
36 schema:givenName Kirsty
37 rdf:type schema:Person
38 N238d23be146949d6b068a8595c166f3e schema:location Berlin, Heidelberg
39 schema:name Springer Berlin Heidelberg
40 rdf:type schema:Organisation
41 N3c2d4ad83c964efdbb713e676058db64 schema:familyName Atmanspacher
42 schema:givenName Harald
43 rdf:type schema:Person
44 N4d8cd5ef10d7421c93f1de7fd559660a rdf:first sg:person.015760605365.01
45 rdf:rest Nddbd575dc0904b0897b793c3abda254f
46 N6cbd04c123c04c2d82d6a88882aa80d6 rdf:first N17b8081529c141f28947a9a5c51a1fd9
47 rdf:rest N14a59bfcd238408a81557504abd222d4
48 N6e46050512824ad8b1d320dd6cd75d17 schema:familyName Haven
49 schema:givenName Emmanuel
50 rdf:type schema:Person
51 N8d696949915f4ba09c65244e70712819 schema:name dimensions_id
52 schema:value pub.1039917211
53 rdf:type schema:PropertyValue
54 Nb81797dbbc334ffebcf91178983bd2f3 schema:name readcube_id
55 schema:value be26220371f001a521c224d1f337d977361e4c4c3ab30bb54db0889ad6ed2348
56 rdf:type schema:PropertyValue
57 Nc76a75fc791840d6be90f3c59e8ce1b2 rdf:first N6e46050512824ad8b1d320dd6cd75d17
58 rdf:rest N6cbd04c123c04c2d82d6a88882aa80d6
59 Ncb96c6147837479a98de45b987b4fbd5 schema:isbn 978-3-642-54942-7
60 978-3-642-54943-4
61 schema:name Quantum Interaction
62 rdf:type schema:Book
63 Ncdaf28b50943481c93c8c6df0db0b045 schema:familyName Raine
64 schema:givenName Derek
65 rdf:type schema:Person
66 Nddbd575dc0904b0897b793c3abda254f rdf:first sg:person.013365420775.41
67 rdf:rest rdf:nil
68 Ne3b448f5279146f79de696bc20143fd6 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nf01e01b2b9a74e7c987eb1db1789e013 rdf:first N3c2d4ad83c964efdbb713e676058db64
71 rdf:rest Nc76a75fc791840d6be90f3c59e8ce1b2
72 Nf30084db7aa0401285f526b826df651c schema:name doi
73 schema:value 10.1007/978-3-642-54943-4_15
74 rdf:type schema:PropertyValue
75 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
76 schema:name Physical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
79 schema:name Quantum Physics
80 rdf:type schema:DefinedTerm
81 sg:person.013365420775.41 schema:affiliation https://www.grid.ac/institutes/grid.143643.7
82 schema:familyName Ohya
83 schema:givenName Masanori
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013365420775.41
85 rdf:type schema:Person
86 sg:person.015760605365.01 schema:affiliation https://www.grid.ac/institutes/grid.143643.7
87 schema:familyName Iriyama
88 schema:givenName Satoshi
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760605365.01
90 rdf:type schema:Person
91 https://doi.org/10.1016/s0019-9958(84)80060-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014507492
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/s0034-4877(03)90002-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024115457
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1088/1464-4266/5/6/015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059141466
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1142/9789812774491_0017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096066220
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1142/s1230161208000262 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063015498
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1142/s1230161215500195 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063015685
102 rdf:type schema:CreativeWork
103 https://www.grid.ac/institutes/grid.143643.7 schema:alternateName Tokyo University of Science
104 schema:name Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan
105 rdf:type schema:Organization
 




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


...