The role of quantum correlations in Cop and Robber game View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-03

AUTHORS

Adam Glos, Jarosław Adam Miszczak

ABSTRACT

We introduce and study quantized versions of Cop and Robber game. We achieve this by using graph-preserving quantum operations, which are the quantum analogues of stochastic operations preserving the graph. We provide the tight bound for the number of operations required to reach the given state. By extending them to the controlled operations, we define a quantum-controlled Cop and Robber game, which expands the classical Cop and Robber game, as well as the classically controlled quantum Cop and Robber game. In contrast to the typical scheme for introducing quantum games, we assume that both parties can utilise full information about the opponent’s strategy. We show that the utilisation of the full knowledge about the opponent’s state does not provide the advantage. Moreover, the chances of catching the Robber decrease for classical cop-win graphs. This result does not depend on the chosen model of evolution. On the other hand, the possibility to execute controlled quantum operations allows catching the Robber on almost all classical cop-win graphs. By this, we demonstrate that it is necessary to enrich the structure of correlations between the players’ systems to provide a non-trivial quantized Cop and Robber game. Thus the quantum controlled operations offer a significant advantage over the classically controlled quantum operations. More... »

PAGES

15-26

References to SciGraph publications

  • 2003-05. An Invitation to Quantum Game Theory in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 2013. Graph Searching and Related Problems in HANDBOOK OF COMBINATORIAL OPTIMIZATION
  • 2011-11. Search and pursuit-evasion in mobile robotics in AUTONOMOUS ROBOTS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s40509-017-0148-4

    DOI

    http://dx.doi.org/10.1007/s40509-017-0148-4

    DIMENSIONS

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


    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": "Institute of Theoretical and Applied Informatics", 
              "id": "https://www.grid.ac/institutes/grid.460371.7", 
              "name": [
                "Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Ba\u0142tycka 5, 44-100, Gliwice, Poland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Glos", 
            "givenName": "Adam", 
            "id": "sg:person.014051442432.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014051442432.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Theoretical and Applied Informatics", 
              "id": "https://www.grid.ac/institutes/grid.460371.7", 
              "name": [
                "Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Ba\u0142tycka 5, 44-100, Gliwice, Poland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Miszczak", 
            "givenName": "Jaros\u0142aw Adam", 
            "id": "sg:person.011530055313.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011530055313.09"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.tcs.2015.12.012", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001995212"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10514-011-9241-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003803092", 
              "https://doi.org/10.1007/s10514-011-9241-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.83.3077", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019919873"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.83.3077", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019919873"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(83)90160-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021809830"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.physd.2013.04.010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030916908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2016.06.039", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031292620"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(87)90033-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039434908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2012.02.018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040997967"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0898-1221(87)90105-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042674921"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4419-7997-1_76", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042784683", 
              "https://doi.org/10.1007/978-1-4419-7997-1_76"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2016.06.019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044737615"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/15427951.2007.10129149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044896315"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1025443111388", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046374538", 
              "https://doi.org/10.1023/a:1025443111388"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3923/itj.2013.2358.2365", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046412805"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1751-8113/49/37/375302", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059174527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0317049", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062843492"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/060672054", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062849773"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2200/s00422ed1v01y201205qmc006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069288304"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/stml/061", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098741697"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03", 
        "datePublishedReg": "2019-03-01", 
        "description": "We introduce and study quantized versions of Cop and Robber game. We achieve this by using graph-preserving quantum operations, which are the quantum analogues of stochastic operations preserving the graph. We provide the tight bound for the number of operations required to reach the given state. By extending them to the controlled operations, we define a quantum-controlled Cop and Robber game, which expands the classical Cop and Robber game, as well as the classically controlled quantum Cop and Robber game. In contrast to the typical scheme for introducing quantum games, we assume that both parties can utilise full information about the opponent\u2019s strategy. We show that the utilisation of the full knowledge about the opponent\u2019s state does not provide the advantage. Moreover, the chances of catching the Robber decrease for classical cop-win graphs. This result does not depend on the chosen model of evolution. On the other hand, the possibility to execute controlled quantum operations allows catching the Robber on almost all classical cop-win graphs. By this, we demonstrate that it is necessary to enrich the structure of correlations between the players\u2019 systems to provide a non-trivial quantized Cop and Robber game. Thus the quantum controlled operations offer a significant advantage over the classically controlled quantum operations.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s40509-017-0148-4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7404421", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1135937", 
            "issn": [
              "2196-5609", 
              "2196-5617"
            ], 
            "name": "Quantum Studies: Mathematics and Foundations", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "name": "The role of quantum correlations in Cop and Robber game", 
        "pagination": "15-26", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "39238993858a3fd54052b7a261e4565f147eccdeda6aad2719b94153339f063f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s40509-017-0148-4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1093045305"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s40509-017-0148-4", 
          "https://app.dimensions.ai/details/publication/pub.1093045305"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:13", 
        "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/0000000361_0000000361/records_53999_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs40509-017-0148-4"
      }
    ]
     

    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/s40509-017-0148-4'

    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/s40509-017-0148-4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s40509-017-0148-4'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s40509-017-0148-4'


     

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

    130 TRIPLES      21 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s40509-017-0148-4 schema:about anzsrc-for:02
    2 anzsrc-for:0206
    3 schema:author N67fd2f9402114a76934bbc207a32736a
    4 schema:citation sg:pub.10.1007/978-1-4419-7997-1_76
    5 sg:pub.10.1007/s10514-011-9241-4
    6 sg:pub.10.1023/a:1025443111388
    7 https://doi.org/10.1016/0012-365x(83)90160-7
    8 https://doi.org/10.1016/0166-218x(87)90033-3
    9 https://doi.org/10.1016/0898-1221(87)90105-2
    10 https://doi.org/10.1016/j.dam.2016.06.019
    11 https://doi.org/10.1016/j.disc.2012.02.018
    12 https://doi.org/10.1016/j.physd.2013.04.010
    13 https://doi.org/10.1016/j.tcs.2015.12.012
    14 https://doi.org/10.1016/j.tcs.2016.06.039
    15 https://doi.org/10.1080/15427951.2007.10129149
    16 https://doi.org/10.1088/1751-8113/49/37/375302
    17 https://doi.org/10.1090/stml/061
    18 https://doi.org/10.1103/physrevlett.83.3077
    19 https://doi.org/10.1137/0317049
    20 https://doi.org/10.1137/060672054
    21 https://doi.org/10.2200/s00422ed1v01y201205qmc006
    22 https://doi.org/10.3923/itj.2013.2358.2365
    23 schema:datePublished 2019-03
    24 schema:datePublishedReg 2019-03-01
    25 schema:description We introduce and study quantized versions of Cop and Robber game. We achieve this by using graph-preserving quantum operations, which are the quantum analogues of stochastic operations preserving the graph. We provide the tight bound for the number of operations required to reach the given state. By extending them to the controlled operations, we define a quantum-controlled Cop and Robber game, which expands the classical Cop and Robber game, as well as the classically controlled quantum Cop and Robber game. In contrast to the typical scheme for introducing quantum games, we assume that both parties can utilise full information about the opponent’s strategy. We show that the utilisation of the full knowledge about the opponent’s state does not provide the advantage. Moreover, the chances of catching the Robber decrease for classical cop-win graphs. This result does not depend on the chosen model of evolution. On the other hand, the possibility to execute controlled quantum operations allows catching the Robber on almost all classical cop-win graphs. By this, we demonstrate that it is necessary to enrich the structure of correlations between the players’ systems to provide a non-trivial quantized Cop and Robber game. Thus the quantum controlled operations offer a significant advantage over the classically controlled quantum operations.
    26 schema:genre research_article
    27 schema:inLanguage en
    28 schema:isAccessibleForFree true
    29 schema:isPartOf N3f2e6c3f1ac04d65815449db4fa7b788
    30 N7fd85bd59abd456294f280e09340b1bf
    31 sg:journal.1135937
    32 schema:name The role of quantum correlations in Cop and Robber game
    33 schema:pagination 15-26
    34 schema:productId N88a59efd8c23458598e57a64e8e90cdc
    35 Nb01a60d864b348b5aac0e0aa396bc045
    36 Nf91c14db617245ad8bfd0f2841896112
    37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093045305
    38 https://doi.org/10.1007/s40509-017-0148-4
    39 schema:sdDatePublished 2019-04-11T12:13
    40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    41 schema:sdPublisher N74847264787b490a97b074a44c7bc253
    42 schema:url https://link.springer.com/10.1007%2Fs40509-017-0148-4
    43 sgo:license sg:explorer/license/
    44 sgo:sdDataset articles
    45 rdf:type schema:ScholarlyArticle
    46 N3f2e6c3f1ac04d65815449db4fa7b788 schema:issueNumber 1
    47 rdf:type schema:PublicationIssue
    48 N67fd2f9402114a76934bbc207a32736a rdf:first sg:person.014051442432.49
    49 rdf:rest Nddc3f8702dfe4092983300ddd6710dad
    50 N74847264787b490a97b074a44c7bc253 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N7fd85bd59abd456294f280e09340b1bf schema:volumeNumber 6
    53 rdf:type schema:PublicationVolume
    54 N88a59efd8c23458598e57a64e8e90cdc schema:name readcube_id
    55 schema:value 39238993858a3fd54052b7a261e4565f147eccdeda6aad2719b94153339f063f
    56 rdf:type schema:PropertyValue
    57 Nb01a60d864b348b5aac0e0aa396bc045 schema:name doi
    58 schema:value 10.1007/s40509-017-0148-4
    59 rdf:type schema:PropertyValue
    60 Nddc3f8702dfe4092983300ddd6710dad rdf:first sg:person.011530055313.09
    61 rdf:rest rdf:nil
    62 Nf91c14db617245ad8bfd0f2841896112 schema:name dimensions_id
    63 schema:value pub.1093045305
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Physical Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Quantum Physics
    70 rdf:type schema:DefinedTerm
    71 sg:grant.7404421 http://pending.schema.org/fundedItem sg:pub.10.1007/s40509-017-0148-4
    72 rdf:type schema:MonetaryGrant
    73 sg:journal.1135937 schema:issn 2196-5609
    74 2196-5617
    75 schema:name Quantum Studies: Mathematics and Foundations
    76 rdf:type schema:Periodical
    77 sg:person.011530055313.09 schema:affiliation https://www.grid.ac/institutes/grid.460371.7
    78 schema:familyName Miszczak
    79 schema:givenName Jarosław Adam
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011530055313.09
    81 rdf:type schema:Person
    82 sg:person.014051442432.49 schema:affiliation https://www.grid.ac/institutes/grid.460371.7
    83 schema:familyName Glos
    84 schema:givenName Adam
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014051442432.49
    86 rdf:type schema:Person
    87 sg:pub.10.1007/978-1-4419-7997-1_76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042784683
    88 https://doi.org/10.1007/978-1-4419-7997-1_76
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/s10514-011-9241-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003803092
    91 https://doi.org/10.1007/s10514-011-9241-4
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1023/a:1025443111388 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046374538
    94 https://doi.org/10.1023/a:1025443111388
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/0012-365x(83)90160-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021809830
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0166-218x(87)90033-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039434908
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0898-1221(87)90105-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042674921
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.dam.2016.06.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044737615
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/j.disc.2012.02.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040997967
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/j.physd.2013.04.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030916908
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/j.tcs.2015.12.012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001995212
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/j.tcs.2016.06.039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031292620
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1080/15427951.2007.10129149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044896315
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1088/1751-8113/49/37/375302 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059174527
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1090/stml/061 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098741697
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1103/physrevlett.83.3077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019919873
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/0317049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062843492
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1137/060672054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062849773
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.2200/s00422ed1v01y201205qmc006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069288304
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.3923/itj.2013.2358.2365 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046412805
    127 rdf:type schema:CreativeWork
    128 https://www.grid.ac/institutes/grid.460371.7 schema:alternateName Institute of Theoretical and Applied Informatics
    129 schema:name Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100, Gliwice, Poland
    130 rdf:type schema:Organization
     




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


    ...