A different Deutsch–Jozsa View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-06

AUTHORS

Debajyoti Bera

ABSTRACT

One of the early achievements of quantum computing was demonstrated by Deutsch and Jozsa (Proc R Soc Lond A Math Phys Sci 439(1907):553, 1992) regarding classification of a particular type of Boolean functions. Their solution demonstrated an exponential speedup compared to classical approaches to the same problem; however, their solution was the only known quantum algorithm for that specific problem so far. This paper demonstrates another quantum algorithm for the same problem, with the same exponential advantage compared to classical algorithms. The novelty of this algorithm is the use of quantum amplitude amplification, a technique that is the key component of another celebrated quantum algorithm developed by Grover (Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM Press, New York, 1996). A lower bound for randomized (classical) algorithms is also presented which establishes a sound gap between the effectiveness of our quantum algorithm and that of any randomized algorithm with similar efficiency. More... »

PAGES

1777-1785

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11128-015-0976-2

DOI

http://dx.doi.org/10.1007/s11128-015-0976-2

DIMENSIONS

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


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": {
          "name": [
            "Indraprastha Institute of Information Technology (IIIT-D), Okhla Industrial Estate Ph-III, 110020, New Delhi, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bera", 
        "givenName": "Debajyoti", 
        "id": "sg:person.011647715651.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011647715651.18"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1103/physrevlett.80.4329", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001325486"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.80.4329", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001325486"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1098/rspa.1992.0167", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014216946"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1098/rspa.1998.0164", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044905446"
        ], 
        "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.1098/rspa.1985.0070", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053404391"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539795293172", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880065"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/istcs.1997.595153", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093921075"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511976667", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098774954"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/conm/305", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1108334884"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015-06", 
    "datePublishedReg": "2015-06-01", 
    "description": "One of the early achievements of quantum computing was demonstrated by Deutsch and Jozsa (Proc R Soc Lond A Math Phys Sci 439(1907):553, 1992) regarding classification of a particular type of Boolean functions. Their solution demonstrated an exponential speedup compared to classical approaches to the same problem; however, their solution was the only known quantum algorithm for that specific problem so far. This paper demonstrates another quantum algorithm for the same problem, with the same exponential advantage compared to classical algorithms. The novelty of this algorithm is the use of quantum amplitude amplification, a technique that is the key component of another celebrated quantum algorithm developed by Grover (Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM Press, New York, 1996). A lower bound for randomized (classical) algorithms is also presented which establishes a sound gap between the effectiveness of our quantum algorithm and that of any randomized algorithm with similar efficiency.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s11128-015-0976-2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052742", 
        "issn": [
          "1570-0755", 
          "1573-1332"
        ], 
        "name": "Quantum Information Processing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "6", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "14"
      }
    ], 
    "name": "A different Deutsch\u2013Jozsa", 
    "pagination": "1777-1785", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0db5416465f606206932d52fed697ef74fa4231db3eeb87933c0ea9b0f1cb1be"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s11128-015-0976-2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1002878479"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s11128-015-0976-2", 
      "https://app.dimensions.ai/details/publication/pub.1002878479"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T01:18", 
    "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_8697_00000579.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs11128-015-0976-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/s11128-015-0976-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/s11128-015-0976-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11128-015-0976-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11128-015-0976-2'


 

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

87 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s11128-015-0976-2 schema:about anzsrc-for:02
2 anzsrc-for:0206
3 schema:author N942818fa947e4879bd8f6e37122c47dc
4 schema:citation https://doi.org/10.1017/cbo9780511976667
5 https://doi.org/10.1090/conm/305
6 https://doi.org/10.1098/rspa.1985.0070
7 https://doi.org/10.1098/rspa.1992.0167
8 https://doi.org/10.1098/rspa.1998.0164
9 https://doi.org/10.1103/physrevlett.80.4329
10 https://doi.org/10.1109/istcs.1997.595153
11 https://doi.org/10.1137/s0097539795293172
12 https://doi.org/10.1145/237814.237866
13 schema:datePublished 2015-06
14 schema:datePublishedReg 2015-06-01
15 schema:description One of the early achievements of quantum computing was demonstrated by Deutsch and Jozsa (Proc R Soc Lond A Math Phys Sci 439(1907):553, 1992) regarding classification of a particular type of Boolean functions. Their solution demonstrated an exponential speedup compared to classical approaches to the same problem; however, their solution was the only known quantum algorithm for that specific problem so far. This paper demonstrates another quantum algorithm for the same problem, with the same exponential advantage compared to classical algorithms. The novelty of this algorithm is the use of quantum amplitude amplification, a technique that is the key component of another celebrated quantum algorithm developed by Grover (Proceedings of the twenty-eighth annual ACM symposium on theory of computing, ACM Press, New York, 1996). A lower bound for randomized (classical) algorithms is also presented which establishes a sound gap between the effectiveness of our quantum algorithm and that of any randomized algorithm with similar efficiency.
16 schema:genre research_article
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N4cca47ce3e6a4134bcdb3b93a4d5b05a
20 N9e615bce218f4ac7a2a0e0a0c3bb4a6d
21 sg:journal.1052742
22 schema:name A different Deutsch–Jozsa
23 schema:pagination 1777-1785
24 schema:productId N4f66181a667044d59bff501e0026018f
25 N993affe28ac5468f8b84d69b7f2c936a
26 Nc1b26dc22629498d876ef895e9f519ee
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002878479
28 https://doi.org/10.1007/s11128-015-0976-2
29 schema:sdDatePublished 2019-04-11T01:18
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N286d85150e2e40a8960dabb5c239ca64
32 schema:url http://link.springer.com/10.1007%2Fs11128-015-0976-2
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N26855b58ada040e1a981537bed646d58 schema:name Indraprastha Institute of Information Technology (IIIT-D), Okhla Industrial Estate Ph-III, 110020, New Delhi, India
37 rdf:type schema:Organization
38 N286d85150e2e40a8960dabb5c239ca64 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N4cca47ce3e6a4134bcdb3b93a4d5b05a schema:issueNumber 6
41 rdf:type schema:PublicationIssue
42 N4f66181a667044d59bff501e0026018f schema:name doi
43 schema:value 10.1007/s11128-015-0976-2
44 rdf:type schema:PropertyValue
45 N942818fa947e4879bd8f6e37122c47dc rdf:first sg:person.011647715651.18
46 rdf:rest rdf:nil
47 N993affe28ac5468f8b84d69b7f2c936a schema:name readcube_id
48 schema:value 0db5416465f606206932d52fed697ef74fa4231db3eeb87933c0ea9b0f1cb1be
49 rdf:type schema:PropertyValue
50 N9e615bce218f4ac7a2a0e0a0c3bb4a6d schema:volumeNumber 14
51 rdf:type schema:PublicationVolume
52 Nc1b26dc22629498d876ef895e9f519ee schema:name dimensions_id
53 schema:value pub.1002878479
54 rdf:type schema:PropertyValue
55 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
56 schema:name Physical Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
59 schema:name Quantum Physics
60 rdf:type schema:DefinedTerm
61 sg:journal.1052742 schema:issn 1570-0755
62 1573-1332
63 schema:name Quantum Information Processing
64 rdf:type schema:Periodical
65 sg:person.011647715651.18 schema:affiliation N26855b58ada040e1a981537bed646d58
66 schema:familyName Bera
67 schema:givenName Debajyoti
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011647715651.18
69 rdf:type schema:Person
70 https://doi.org/10.1017/cbo9780511976667 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098774954
71 rdf:type schema:CreativeWork
72 https://doi.org/10.1090/conm/305 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108334884
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1098/rspa.1985.0070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053404391
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1098/rspa.1992.0167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014216946
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1098/rspa.1998.0164 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044905446
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1103/physrevlett.80.4329 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001325486
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1109/istcs.1997.595153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093921075
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1137/s0097539795293172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880065
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1145/237814.237866 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053319325
87 rdf:type schema:CreativeWork
 




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


...