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 N13f76bef807d4190b56002ae5ad0d1a5
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 N576aa627f22e45d082cce67acdeb05d1
15 Ne8135a3962d84b158dacd714b82186b5
16 sg:journal.1140079
17 schema:name NP Problem in Quantum Algorithm
18 schema:pagination 33-39
19 schema:productId N32e95e1c6fda4432a3c932b18ec6960a
20 N6021f6e04f3e49cbb0149c6abf6153cd
21 Nedbd8a566e1443c9a9d870275d494587
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 N0e0c9ba0fd1e4cdc81d07fd0dd0f9472
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 N0e0c9ba0fd1e4cdc81d07fd0dd0f9472 schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 N13f76bef807d4190b56002ae5ad0d1a5 rdf:first sg:person.013365420775.41
34 rdf:rest Nbdaa1aa25b3146868f0fede760cfbfd6
35 N32e95e1c6fda4432a3c932b18ec6960a schema:name dimensions_id
36 schema:value pub.1012766077
37 rdf:type schema:PropertyValue
38 N576aa627f22e45d082cce67acdeb05d1 schema:issueNumber 1
39 rdf:type schema:PublicationIssue
40 N6021f6e04f3e49cbb0149c6abf6153cd schema:name readcube_id
41 schema:value 3cd0d6ff7644f12b90ae2e4d4057749b01d77757be976032dd93ce5722d543fb
42 rdf:type schema:PropertyValue
43 Nbdaa1aa25b3146868f0fede760cfbfd6 rdf:first sg:person.013632562123.23
44 rdf:rest rdf:nil
45 Ne8135a3962d84b158dacd714b82186b5 schema:volumeNumber 7
46 rdf:type schema:PublicationVolume
47 Nedbd8a566e1443c9a9d870275d494587 schema:name doi
48 schema:value 10.1023/a:1009651417615
49 rdf:type schema:PropertyValue
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)


...