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 N097a2390e8e6487b95646e5b5c3a9e45
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 N9ab912f0a39341668b6fbb68c9d969df
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf Naf7f8ea68c2c46fc8045ca0018b0ef89
18 schema:name Polynomial Time Quantum Algorithm for Search Problem and Its Application
19 schema:pagination 172-183
20 schema:productId N50a184dec40e47d689a638c1060a4f8c
21 Nac87a72a2ec544cb9946170b11bb70d3
22 Nef75fff727894b408ad83b2c8b407595
23 schema:publisher Ne43c86c9a4ec4cfc941fcbb4409e36f4
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 N30d47ca3afdb497ab038b80051663bce
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 N097a2390e8e6487b95646e5b5c3a9e45 rdf:first sg:person.015760605365.01
34 rdf:rest N3d3debabe35b461bb23f819ef83dd69c
35 N159fb9a5c8254ffa895d6f494621dfd5 schema:familyName Atmanspacher
36 schema:givenName Harald
37 rdf:type schema:Person
38 N30d47ca3afdb497ab038b80051663bce schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N3d3debabe35b461bb23f819ef83dd69c rdf:first sg:person.013365420775.41
41 rdf:rest rdf:nil
42 N50a184dec40e47d689a638c1060a4f8c schema:name dimensions_id
43 schema:value pub.1039917211
44 rdf:type schema:PropertyValue
45 N6527972145cf430c921d3ea70f383f97 rdf:first Nd55a44dd73a147ada35ae73caf9757a3
46 rdf:rest Ndbaad9039ddb48c39bf7f8d293c3606b
47 N947ade1d9a9841e8959da3536625a3b0 rdf:first Na59d6e19d09d4d47bf1a9641753acbf2
48 rdf:rest N6527972145cf430c921d3ea70f383f97
49 N9ab912f0a39341668b6fbb68c9d969df rdf:first N159fb9a5c8254ffa895d6f494621dfd5
50 rdf:rest N947ade1d9a9841e8959da3536625a3b0
51 Na59d6e19d09d4d47bf1a9641753acbf2 schema:familyName Haven
52 schema:givenName Emmanuel
53 rdf:type schema:Person
54 Nac87a72a2ec544cb9946170b11bb70d3 schema:name readcube_id
55 schema:value be26220371f001a521c224d1f337d977361e4c4c3ab30bb54db0889ad6ed2348
56 rdf:type schema:PropertyValue
57 Naf7f8ea68c2c46fc8045ca0018b0ef89 schema:isbn 978-3-642-54942-7
58 978-3-642-54943-4
59 schema:name Quantum Interaction
60 rdf:type schema:Book
61 Nd32f60e63c094deba1110aef30fd0b20 schema:familyName Raine
62 schema:givenName Derek
63 rdf:type schema:Person
64 Nd55a44dd73a147ada35ae73caf9757a3 schema:familyName Kitto
65 schema:givenName Kirsty
66 rdf:type schema:Person
67 Ndbaad9039ddb48c39bf7f8d293c3606b rdf:first Nd32f60e63c094deba1110aef30fd0b20
68 rdf:rest rdf:nil
69 Ne43c86c9a4ec4cfc941fcbb4409e36f4 schema:location Berlin, Heidelberg
70 schema:name Springer Berlin Heidelberg
71 rdf:type schema:Organisation
72 Nef75fff727894b408ad83b2c8b407595 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)


...