Quantum learning of concentrated Boolean functions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-07-26

AUTHORS

Krishna Palem, Duc Hung Pham, M. V. Panduranga Rao

ABSTRACT

In this paper, we present a series of new results about learning of concentrated Boolean functions in the quantum computing model. Given a Boolean function f on n variables, its concentration refers to the dominant terms in its Fourier–Walsh spectrum. We show that a quantum probabilistically approximately correct learning model to learn a Boolean function characterized by its concentration yields improvements over the best-known classical method. All of our results are presented within the framework of query complexity, and therefore, our advantage represents asymptotic improvements in the number of queries using a quantum approach over its classical counterpart. Next, we prove a lower bound in the number of quantum queries needed to learn the function in the distribution-independent settings. Further, we examine the case of exact learning which is the learning variant without error. Here, we show that the query complexity grows as 2βn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{{\beta }n}$$\end{document} for some 0<β<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0< \beta < 1$$\end{document} and therefore remains intractable even when quantum approaches are considered. This proof is based on the quantum information theoretic approach developed by researchers for the restricted case of k-sparse functions. More... »

PAGES

256

References to SciGraph publications

  • 2014-07-27. Quantum principal component analysis in NATURE PHYSICS
  • 2007-09-02. Quantum Algorithms for Learning and Testing Juntas in QUANTUM INFORMATION PROCESSING
  • 2006. Machine Learning in a Quantum World in ADVANCES IN ARTIFICIAL INTELLIGENCE
  • 2012-08-31. Quantum speed-up for unsupervised learning in MACHINE LEARNING
  • 2017-09-14. Quantum machine learning in NATURE
  • 2005-10-18. Improved Bounds on Quantum Learning Algorithms in QUANTUM INFORMATION PROCESSING
  • 2002-02-21. A Quantum Goldreich-Levin Theorem with Cryptographic Applications in STACS 2002
  • 1988-04. Queries and concept learning in MACHINE LEARNING
  • 2015-04-02. Read the fine print in NATURE PHYSICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11128-022-03607-5

    DOI

    http://dx.doi.org/10.1007/s11128-022-03607-5

    DIMENSIONS

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


    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 Computer Science, Rice University, Houston, USA", 
              "id": "http://www.grid.ac/institutes/grid.21940.3e", 
              "name": [
                "Department of Computer Science, Rice University, Houston, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Palem", 
            "givenName": "Krishna", 
            "id": "sg:person.010164163375.74", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010164163375.74"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Rice University, Houston, USA", 
              "id": "http://www.grid.ac/institutes/grid.21940.3e", 
              "name": [
                "Department of Computer Science, Rice University, Houston, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pham", 
            "givenName": "Duc Hung", 
            "id": "sg:person.013533400151.35", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013533400151.35"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India", 
              "id": "http://www.grid.ac/institutes/grid.459612.d", 
              "name": [
                "Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rao", 
            "givenName": "M. V. Panduranga", 
            "id": "sg:person.015201410673.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015201410673.95"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf00116828", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030500577", 
              "https://doi.org/10.1007/bf00116828"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nphys3029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008585200", 
              "https://doi.org/10.1038/nphys3029"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45841-7_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005218766", 
              "https://doi.org/10.1007/3-540-45841-7_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nphys3272", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021586000", 
              "https://doi.org/10.1038/nphys3272"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nature23474", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091594880", 
              "https://doi.org/10.1038/nature23474"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10994-012-5316-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009584517", 
              "https://doi.org/10.1007/s10994-012-5316-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11766247_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019766388", 
              "https://doi.org/10.1007/11766247_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11128-005-0001-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021931038", 
              "https://doi.org/10.1007/s11128-005-0001-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11128-007-0061-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004454795", 
              "https://doi.org/10.1007/s11128-007-0061-6"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-07-26", 
        "datePublishedReg": "2022-07-26", 
        "description": "In this paper, we present a series of new results about learning of concentrated Boolean functions in the quantum computing model. Given a Boolean function f on n variables, its concentration refers to the dominant terms in its Fourier\u2013Walsh spectrum. We show that a quantum probabilistically approximately correct learning model to learn a Boolean function characterized by its concentration yields improvements over the best-known classical method. All of our results are presented within the framework of query complexity, and therefore, our advantage represents asymptotic improvements in the number of queries using a quantum approach over its classical counterpart. Next, we prove a lower bound in the number of quantum queries needed to learn the function in the distribution-independent settings. Further, we examine the case of exact learning which is the learning variant without error. Here, we show that the query complexity grows as 2\u03b2n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{{\\beta }n}$$\\end{document} for some 0<\u03b2<1\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0< \\beta < 1$$\\end{document} and therefore remains intractable even when quantum approaches are considered. This proof is based on the quantum information theoretic approach developed by researchers for the restricted case of k-sparse functions.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11128-022-03607-5", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052742", 
            "issn": [
              "1570-0755", 
              "1573-1332"
            ], 
            "name": "Quantum Information Processing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "7", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "21"
          }
        ], 
        "keywords": [
          "quantum approach", 
          "quantum computing models", 
          "classical counterpart", 
          "quantum learning", 
          "dominant term", 
          "quantum queries", 
          "new results", 
          "quantum", 
          "spectra", 
          "classical methods", 
          "function", 
          "query complexity", 
          "model", 
          "results", 
          "counterparts", 
          "proof", 
          "restricted case", 
          "method", 
          "terms", 
          "advantages", 
          "error", 
          "cases", 
          "concentration", 
          "number", 
          "approach", 
          "improvement", 
          "series", 
          "asymptotic improvement", 
          "number of queries", 
          "framework", 
          "computing model", 
          "information-theoretic approach", 
          "paper", 
          "Boolean functions", 
          "Correct (PAC) learning model", 
          "learning model", 
          "exact learning", 
          "theoretic approach", 
          "queries", 
          "function f", 
          "learning", 
          "sparse functions", 
          "complexity", 
          "Boolean function f", 
          "n variables", 
          "researchers", 
          "variables", 
          "setting"
        ], 
        "name": "Quantum learning of concentrated Boolean functions", 
        "pagination": "256", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1149816842"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11128-022-03607-5"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11128-022-03607-5", 
          "https://app.dimensions.ai/details/publication/pub.1149816842"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T21:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_949.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11128-022-03607-5"
      }
    ]
     

    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-022-03607-5'

    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-022-03607-5'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11128-022-03607-5'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11128-022-03607-5'


     

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

    158 TRIPLES      21 PREDICATES      81 URIs      64 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11128-022-03607-5 schema:about anzsrc-for:02
    2 anzsrc-for:0206
    3 schema:author N22966439efcb4eff8e50f93d5e73ee4d
    4 schema:citation sg:pub.10.1007/11766247_37
    5 sg:pub.10.1007/3-540-45841-7_26
    6 sg:pub.10.1007/bf00116828
    7 sg:pub.10.1007/s10994-012-5316-5
    8 sg:pub.10.1007/s11128-005-0001-2
    9 sg:pub.10.1007/s11128-007-0061-6
    10 sg:pub.10.1038/nature23474
    11 sg:pub.10.1038/nphys3029
    12 sg:pub.10.1038/nphys3272
    13 schema:datePublished 2022-07-26
    14 schema:datePublishedReg 2022-07-26
    15 schema:description In this paper, we present a series of new results about learning of concentrated Boolean functions in the quantum computing model. Given a Boolean function f on n variables, its concentration refers to the dominant terms in its Fourier–Walsh spectrum. We show that a quantum probabilistically approximately correct learning model to learn a Boolean function characterized by its concentration yields improvements over the best-known classical method. All of our results are presented within the framework of query complexity, and therefore, our advantage represents asymptotic improvements in the number of queries using a quantum approach over its classical counterpart. Next, we prove a lower bound in the number of quantum queries needed to learn the function in the distribution-independent settings. Further, we examine the case of exact learning which is the learning variant without error. Here, we show that the query complexity grows as 2βn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{{\beta }n}$$\end{document} for some 0<β<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0< \beta < 1$$\end{document} and therefore remains intractable even when quantum approaches are considered. This proof is based on the quantum information theoretic approach developed by researchers for the restricted case of k-sparse functions.
    16 schema:genre article
    17 schema:isAccessibleForFree false
    18 schema:isPartOf N28880fa1fc5c4dda81e6eb8e0c082dcb
    19 N50b70602084e469c95dac0b4678492a7
    20 sg:journal.1052742
    21 schema:keywords Boolean function f
    22 Boolean functions
    23 Correct (PAC) learning model
    24 advantages
    25 approach
    26 asymptotic improvement
    27 cases
    28 classical counterpart
    29 classical methods
    30 complexity
    31 computing model
    32 concentration
    33 counterparts
    34 dominant term
    35 error
    36 exact learning
    37 framework
    38 function
    39 function f
    40 improvement
    41 information-theoretic approach
    42 learning
    43 learning model
    44 method
    45 model
    46 n variables
    47 new results
    48 number
    49 number of queries
    50 paper
    51 proof
    52 quantum
    53 quantum approach
    54 quantum computing models
    55 quantum learning
    56 quantum queries
    57 queries
    58 query complexity
    59 researchers
    60 restricted case
    61 results
    62 series
    63 setting
    64 sparse functions
    65 spectra
    66 terms
    67 theoretic approach
    68 variables
    69 schema:name Quantum learning of concentrated Boolean functions
    70 schema:pagination 256
    71 schema:productId Nc8663483113746108bb464c076e1469a
    72 Ndcf4682eb8ea4cf7992589d9b063a0e4
    73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149816842
    74 https://doi.org/10.1007/s11128-022-03607-5
    75 schema:sdDatePublished 2022-11-24T21:09
    76 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    77 schema:sdPublisher Nbe5ed81578f04c9f86103de3fc2b2fe9
    78 schema:url https://doi.org/10.1007/s11128-022-03607-5
    79 sgo:license sg:explorer/license/
    80 sgo:sdDataset articles
    81 rdf:type schema:ScholarlyArticle
    82 N0899a3654ad9424f9acc47738dccc860 rdf:first sg:person.015201410673.95
    83 rdf:rest rdf:nil
    84 N22966439efcb4eff8e50f93d5e73ee4d rdf:first sg:person.010164163375.74
    85 rdf:rest Nb1cf59fc406e4d89aa98cddbcf0707a0
    86 N28880fa1fc5c4dda81e6eb8e0c082dcb schema:issueNumber 7
    87 rdf:type schema:PublicationIssue
    88 N50b70602084e469c95dac0b4678492a7 schema:volumeNumber 21
    89 rdf:type schema:PublicationVolume
    90 Nb1cf59fc406e4d89aa98cddbcf0707a0 rdf:first sg:person.013533400151.35
    91 rdf:rest N0899a3654ad9424f9acc47738dccc860
    92 Nbe5ed81578f04c9f86103de3fc2b2fe9 schema:name Springer Nature - SN SciGraph project
    93 rdf:type schema:Organization
    94 Nc8663483113746108bb464c076e1469a schema:name doi
    95 schema:value 10.1007/s11128-022-03607-5
    96 rdf:type schema:PropertyValue
    97 Ndcf4682eb8ea4cf7992589d9b063a0e4 schema:name dimensions_id
    98 schema:value pub.1149816842
    99 rdf:type schema:PropertyValue
    100 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Physical Sciences
    102 rdf:type schema:DefinedTerm
    103 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
    104 schema:name Quantum Physics
    105 rdf:type schema:DefinedTerm
    106 sg:journal.1052742 schema:issn 1570-0755
    107 1573-1332
    108 schema:name Quantum Information Processing
    109 schema:publisher Springer Nature
    110 rdf:type schema:Periodical
    111 sg:person.010164163375.74 schema:affiliation grid-institutes:grid.21940.3e
    112 schema:familyName Palem
    113 schema:givenName Krishna
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010164163375.74
    115 rdf:type schema:Person
    116 sg:person.013533400151.35 schema:affiliation grid-institutes:grid.21940.3e
    117 schema:familyName Pham
    118 schema:givenName Duc Hung
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013533400151.35
    120 rdf:type schema:Person
    121 sg:person.015201410673.95 schema:affiliation grid-institutes:grid.459612.d
    122 schema:familyName Rao
    123 schema:givenName M. V. Panduranga
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015201410673.95
    125 rdf:type schema:Person
    126 sg:pub.10.1007/11766247_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019766388
    127 https://doi.org/10.1007/11766247_37
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-45841-7_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005218766
    130 https://doi.org/10.1007/3-540-45841-7_26
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf00116828 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030500577
    133 https://doi.org/10.1007/bf00116828
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/s10994-012-5316-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009584517
    136 https://doi.org/10.1007/s10994-012-5316-5
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/s11128-005-0001-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021931038
    139 https://doi.org/10.1007/s11128-005-0001-2
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s11128-007-0061-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004454795
    142 https://doi.org/10.1007/s11128-007-0061-6
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1038/nature23474 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091594880
    145 https://doi.org/10.1038/nature23474
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1038/nphys3029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008585200
    148 https://doi.org/10.1038/nphys3029
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1038/nphys3272 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021586000
    151 https://doi.org/10.1038/nphys3272
    152 rdf:type schema:CreativeWork
    153 grid-institutes:grid.21940.3e schema:alternateName Department of Computer Science, Rice University, Houston, USA
    154 schema:name Department of Computer Science, Rice University, Houston, USA
    155 rdf:type schema:Organization
    156 grid-institutes:grid.459612.d schema:alternateName Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India
    157 schema:name Department of Computer Science and Engineering, IIT Hyderabad, Hyderabad, India
    158 rdf:type schema:Organization
     




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


    ...