NP Problem in Quantum Algorithm View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-03

AUTHORS

Masanori Ohya, Natsuki Masuda

ABSTRACT

In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0> and |1> prepared is detected physically. More... »

PAGES

33-39

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1009651417615

DOI

http://dx.doi.org/10.1023/a:1009651417615

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tokyo University of Science", 
          "id": "https://www.grid.ac/institutes/grid.143643.7", 
          "name": [
            "Science University of Tokyo, 278-8510, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Tokyo University of Science", 
          "id": "https://www.grid.ac/institutes/grid.143643.7", 
          "name": [
            "Science University of Tokyo, 278-8510, Noda City, Chiba, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Masuda", 
        "givenName": "Natsuki", 
        "id": "sg:person.013632562123.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013632562123.23"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "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.1985.0070", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053404391"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/revmodphys.68.733", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060839377"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/revmodphys.68.733", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060839377"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1364/on.11.2.000011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1065242236"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000-03", 
    "datePublishedReg": "2000-03-01", 
    "description": "In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0> and |1> prepared is detected physically.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1009651417615", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1140079", 
        "issn": [
          "1230-1612", 
          "1573-1324"
        ], 
        "name": "Open Systems and Information Dynamics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "name": "NP Problem in Quantum Algorithm", 
    "pagination": "33-39", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "3cd0d6ff7644f12b90ae2e4d4057749b01d77757be976032dd93ce5722d543fb"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1009651417615"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012766077"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1009651417615", 
      "https://app.dimensions.ai/details/publication/pub.1012766077"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T14:02", 
    "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_8660_00000486.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023/A:1009651417615"
  }
]
 

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.1023/a:1009651417615'

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.1023/a:1009651417615'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1009651417615'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1009651417615'


 

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

80 TRIPLES      21 PREDICATES      31 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1009651417615 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N86fe4c05918549008f673fc9f91f97e5
4 schema:citation https://doi.org/10.1098/rspa.1985.0070
5 https://doi.org/10.1098/rspa.1992.0167
6 https://doi.org/10.1103/revmodphys.68.733
7 https://doi.org/10.1364/on.11.2.000011
8 schema:datePublished 2000-03
9 schema:datePublishedReg 2000-03-01
10 schema:description In complexity theory, a famous unsolved problem is whether NP is equal to P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that SAT can be solved in polynomial time by means of a quantum algorithm if the superposition of two orthogonal vectors |0> and |1> prepared is detected physically.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N201794ee403e4e22a4c2eb60321e4c2b
15 Nc416f259b01d4c298d31dd4d344243ac
16 sg:journal.1140079
17 schema:name NP Problem in Quantum Algorithm
18 schema:pagination 33-39
19 schema:productId N256b8cfd9c914412bbea33c168d6ea09
20 N530b6985af834934b974485abe285f25
21 Nc6ddb6d1a0244a99a27adeb02ce11471
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012766077
23 https://doi.org/10.1023/a:1009651417615
24 schema:sdDatePublished 2019-04-10T14:02
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher Ne5ab197e5df8480d8c04e649aabfa851
27 schema:url http://link.springer.com/10.1023/A:1009651417615
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N201794ee403e4e22a4c2eb60321e4c2b schema:volumeNumber 7
32 rdf:type schema:PublicationVolume
33 N256b8cfd9c914412bbea33c168d6ea09 schema:name dimensions_id
34 schema:value pub.1012766077
35 rdf:type schema:PropertyValue
36 N530b6985af834934b974485abe285f25 schema:name readcube_id
37 schema:value 3cd0d6ff7644f12b90ae2e4d4057749b01d77757be976032dd93ce5722d543fb
38 rdf:type schema:PropertyValue
39 N5b68aca7f7b4460e9e8ff208a3881ee7 rdf:first sg:person.013632562123.23
40 rdf:rest rdf:nil
41 N86fe4c05918549008f673fc9f91f97e5 rdf:first sg:person.013365420775.41
42 rdf:rest N5b68aca7f7b4460e9e8ff208a3881ee7
43 Nc416f259b01d4c298d31dd4d344243ac schema:issueNumber 1
44 rdf:type schema:PublicationIssue
45 Nc6ddb6d1a0244a99a27adeb02ce11471 schema:name doi
46 schema:value 10.1023/a:1009651417615
47 rdf:type schema:PropertyValue
48 Ne5ab197e5df8480d8c04e649aabfa851 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
51 schema:name Information and Computing Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
54 schema:name Computation Theory and Mathematics
55 rdf:type schema:DefinedTerm
56 sg:journal.1140079 schema:issn 1230-1612
57 1573-1324
58 schema:name Open Systems and Information Dynamics
59 rdf:type schema:Periodical
60 sg:person.013365420775.41 schema:affiliation https://www.grid.ac/institutes/grid.143643.7
61 schema:familyName Ohya
62 schema:givenName Masanori
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013365420775.41
64 rdf:type schema:Person
65 sg:person.013632562123.23 schema:affiliation https://www.grid.ac/institutes/grid.143643.7
66 schema:familyName Masuda
67 schema:givenName Natsuki
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013632562123.23
69 rdf:type schema:Person
70 https://doi.org/10.1098/rspa.1985.0070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053404391
71 rdf:type schema:CreativeWork
72 https://doi.org/10.1098/rspa.1992.0167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014216946
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1103/revmodphys.68.733 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060839377
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1364/on.11.2.000011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1065242236
77 rdf:type schema:CreativeWork
78 https://www.grid.ac/institutes/grid.143643.7 schema:alternateName Tokyo University of Science
79 schema:name Science University of Tokyo, 278-8510, Noda City, Chiba, Japan
80 rdf:type schema:Organization
 




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


...