Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-07-13

AUTHORS

Byung-Soo Choi, Samuel L. Braunstein

ABSTRACT

As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0 < w1 < w2 < 1, w1 + w2 = 1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0 < w1 < w2 < 1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0 < w1 < w2 < · · · < wm < 1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, the weight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem. More... »

PAGES

177-188

References to SciGraph publications

  • 2006-11-28. Sure Success Partial Search in QUANTUM INFORMATION PROCESSING
  • 1999-11-19. Designs, Intersecting Families, and Weight of Boolean Functions in CRYPTOGRAPHY AND CODING
  • 1998. Quantum counting in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1998. Highly nonlinear balanced Boolean functions with a good correlation-immunity in ADVANCES IN CRYPTOLOGY — EUROCRYPT'98
  • 1996-02. Balance testing and balance-testable design of logic circuits in JOURNAL OF ELECTRONIC TESTING
  • 2006-02. Simple Algorithm for Partial Quantum Search in QUANTUM INFORMATION PROCESSING
  • 2007-08-22. Quantum Partial Search of a Database with Several Target Items in QUANTUM INFORMATION PROCESSING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11128-010-0187-9

    DOI

    http://dx.doi.org/10.1007/s11128-010-0187-9

    DIMENSIONS

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


    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/02", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Physical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea)", 
              "id": "http://www.grid.ac/institutes/grid.255649.9", 
              "name": [
                "Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea)"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Choi", 
            "givenName": "Byung-Soo", 
            "id": "sg:person.013453142634.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013453142634.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of York, YO10 5DD, York, United Kingdom", 
              "id": "http://www.grid.ac/institutes/grid.5685.e", 
              "name": [
                "Department of Computer Science, University of York, YO10 5DD, York, United Kingdom"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Braunstein", 
            "givenName": "Samuel L.", 
            "id": "sg:person.0666766367.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0666766367.22"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s11128-007-0056-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038319959", 
              "https://doi.org/10.1007/s11128-007-0056-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11128-006-0037-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012886712", 
              "https://doi.org/10.1007/s11128-006-0037-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11128-005-0004-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016365980", 
              "https://doi.org/10.1007/s11128-005-0004-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0054147", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030033743", 
              "https://doi.org/10.1007/bfb0054147"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46665-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041679075", 
              "https://doi.org/10.1007/3-540-46665-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00136077", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011773432", 
              "https://doi.org/10.1007/bf00136077"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0055105", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043038508", 
              "https://doi.org/10.1007/bfb0055105"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-07-13", 
        "datePublishedReg": "2010-07-13", 
        "description": "As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0\u00a0<\u00a0w1\u00a0<\u00a0w2\u00a0<\u00a01, w1\u00a0+\u00a0w2\u00a0=\u00a01}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0\u00a0<\u00a0w1\u00a0<\u00a0w2\u00a0<\u00a01}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0\u00a0<\u00a0w1\u00a0<\u00a0w2\u00a0<\u00a0\u00b7 \u00b7 \u00b7\u00a0<\u00a0wm\u00a0<\u00a01}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, the weight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11128-010-0187-9", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052742", 
            "issn": [
              "1570-0755", 
              "1573-1332"
            ], 
            "name": "Quantum Information Processing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "10"
          }
        ], 
        "keywords": [
          "quantum algorithms", 
          "decision problem", 
          "number of solutions", 
          "Boolean functions", 
          "exact quantum algorithm", 
          "number of weights", 
          "quadratic speedup", 
          "quantum advantage", 
          "classical methods", 
          "general asymmetric case", 
          "classical approach", 
          "symmetric case", 
          "Grover search", 
          "extended algorithm", 
          "low complexity", 
          "multiple weights", 
          "algorithm", 
          "problem", 
          "better performance", 
          "solution", 
          "discrimination problems", 
          "asymmetric case", 
          "generalization", 
          "W1", 
          "large number", 
          "different performance", 
          "decision algorithm", 
          "small number", 
          "function", 
          "approach", 
          "state discrimination problem", 
          "speedup", 
          "W2", 
          "complexity", 
          "weight cases", 
          "performance", 
          "number", 
          "counting method", 
          "cases", 
          "applications", 
          "advantages", 
          "search", 
          "way", 
          "pairs", 
          "weight", 
          "article", 
          "relationship", 
          "quantum state discrimination problem", 
          "method", 
          "symmetric weight decision problem", 
          "weight decision problem", 
          "multiple weight decision problem", 
          "quantum counting method", 
          "multiple weight case", 
          "weight decision algorithm", 
          "asymmetric weight decision problem"
        ], 
        "name": "Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights", 
        "pagination": "177-188", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045811815"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11128-010-0187-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11128-010-0187-9", 
          "https://app.dimensions.ai/details/publication/pub.1045811815"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2021-12-01T19:23", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_504.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11128-010-0187-9"
      }
    ]
     

    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-010-0187-9'

    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-010-0187-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11128-010-0187-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11128-010-0187-9'


     

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

    152 TRIPLES      22 PREDICATES      87 URIs      72 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11128-010-0187-9 schema:about anzsrc-for:02
    2 anzsrc-for:0206
    3 schema:author Nec3ca15c493c44759e47f2e79b5e62f8
    4 schema:citation sg:pub.10.1007/3-540-46665-7_7
    5 sg:pub.10.1007/bf00136077
    6 sg:pub.10.1007/bfb0054147
    7 sg:pub.10.1007/bfb0055105
    8 sg:pub.10.1007/s11128-005-0004-z
    9 sg:pub.10.1007/s11128-006-0037-y
    10 sg:pub.10.1007/s11128-007-0056-3
    11 schema:datePublished 2010-07-13
    12 schema:datePublishedReg 2010-07-13
    13 schema:description As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0 < w1 < w2 < 1, w1 + w2 = 1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0 < w1 < w2 < 1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0 < w1 < w2 < · · · < wm < 1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, the weight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf N28eb2f1a78484b6fb1c5f2ae81c7d698
    18 N6b783997dd3047adb3fdcd9b169423f7
    19 sg:journal.1052742
    20 schema:keywords Boolean functions
    21 Grover search
    22 W1
    23 W2
    24 advantages
    25 algorithm
    26 applications
    27 approach
    28 article
    29 asymmetric case
    30 asymmetric weight decision problem
    31 better performance
    32 cases
    33 classical approach
    34 classical methods
    35 complexity
    36 counting method
    37 decision algorithm
    38 decision problem
    39 different performance
    40 discrimination problems
    41 exact quantum algorithm
    42 extended algorithm
    43 function
    44 general asymmetric case
    45 generalization
    46 large number
    47 low complexity
    48 method
    49 multiple weight case
    50 multiple weight decision problem
    51 multiple weights
    52 number
    53 number of solutions
    54 number of weights
    55 pairs
    56 performance
    57 problem
    58 quadratic speedup
    59 quantum advantage
    60 quantum algorithms
    61 quantum counting method
    62 quantum state discrimination problem
    63 relationship
    64 search
    65 small number
    66 solution
    67 speedup
    68 state discrimination problem
    69 symmetric case
    70 symmetric weight decision problem
    71 way
    72 weight
    73 weight cases
    74 weight decision algorithm
    75 weight decision problem
    76 schema:name Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights
    77 schema:pagination 177-188
    78 schema:productId N9a6fcbe31894484589a2d6de594e4708
    79 Nc027334e7031404e9209a331defabe0e
    80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045811815
    81 https://doi.org/10.1007/s11128-010-0187-9
    82 schema:sdDatePublished 2021-12-01T19:23
    83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    84 schema:sdPublisher Ndc3d512044cc463c8daae1b12c1991e4
    85 schema:url https://doi.org/10.1007/s11128-010-0187-9
    86 sgo:license sg:explorer/license/
    87 sgo:sdDataset articles
    88 rdf:type schema:ScholarlyArticle
    89 N28eb2f1a78484b6fb1c5f2ae81c7d698 schema:issueNumber 2
    90 rdf:type schema:PublicationIssue
    91 N5d210bdb89ee45d8a4f1b3f7efc7b666 rdf:first sg:person.0666766367.22
    92 rdf:rest rdf:nil
    93 N6b783997dd3047adb3fdcd9b169423f7 schema:volumeNumber 10
    94 rdf:type schema:PublicationVolume
    95 N9a6fcbe31894484589a2d6de594e4708 schema:name doi
    96 schema:value 10.1007/s11128-010-0187-9
    97 rdf:type schema:PropertyValue
    98 Nc027334e7031404e9209a331defabe0e schema:name dimensions_id
    99 schema:value pub.1045811815
    100 rdf:type schema:PropertyValue
    101 Ndc3d512044cc463c8daae1b12c1991e4 schema:name Springer Nature - SN SciGraph project
    102 rdf:type schema:Organization
    103 Nec3ca15c493c44759e47f2e79b5e62f8 rdf:first sg:person.013453142634.28
    104 rdf:rest N5d210bdb89ee45d8a4f1b3f7efc7b666
    105 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Physical Sciences
    107 rdf:type schema:DefinedTerm
    108 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Quantum Physics
    110 rdf:type schema:DefinedTerm
    111 sg:journal.1052742 schema:issn 1570-0755
    112 1573-1332
    113 schema:name Quantum Information Processing
    114 schema:publisher Springer Nature
    115 rdf:type schema:Periodical
    116 sg:person.013453142634.28 schema:affiliation grid-institutes:grid.255649.9
    117 schema:familyName Choi
    118 schema:givenName Byung-Soo
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013453142634.28
    120 rdf:type schema:Person
    121 sg:person.0666766367.22 schema:affiliation grid-institutes:grid.5685.e
    122 schema:familyName Braunstein
    123 schema:givenName Samuel L.
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0666766367.22
    125 rdf:type schema:Person
    126 sg:pub.10.1007/3-540-46665-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041679075
    127 https://doi.org/10.1007/3-540-46665-7_7
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf00136077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011773432
    130 https://doi.org/10.1007/bf00136077
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bfb0054147 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030033743
    133 https://doi.org/10.1007/bfb0054147
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/bfb0055105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043038508
    136 https://doi.org/10.1007/bfb0055105
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/s11128-005-0004-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1016365980
    139 https://doi.org/10.1007/s11128-005-0004-z
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s11128-006-0037-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1012886712
    142 https://doi.org/10.1007/s11128-006-0037-y
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/s11128-007-0056-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038319959
    145 https://doi.org/10.1007/s11128-007-0056-3
    146 rdf:type schema:CreativeWork
    147 grid-institutes:grid.255649.9 schema:alternateName Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea)
    148 schema:name Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea)
    149 rdf:type schema:Organization
    150 grid-institutes:grid.5685.e schema:alternateName Department of Computer Science, University of York, YO10 5DD, York, United Kingdom
    151 schema:name Department of Computer Science, University of York, YO10 5DD, York, United Kingdom
    152 rdf:type schema:Organization
     




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


    ...