View in EDS

SYMMETRIES, GRAPH PROPERTIES, AND QUANTUM SPEEDUPS.

Saved in:
Bibliographic Details
Title: SYMMETRIES, GRAPH PROPERTIES, AND QUANTUM SPEEDUPS.
Authors: BEN-DAVID, SHALEV1 shalev.b@uwaterloo.ca, CHILDS, ANDREW M.2 amchilds@umd.edu, GILYÉN, ANDRÁS3 gilyen@renyi.hu, KRETSCHMER, WILLIAM4 kretsch@berkeley.edu, PODDER, SUPARTHA5 supartha@cs.stonybrook.edu, DAOCHEN WANG6 wdaochen@gmail.com
Source: SIAM Journal on Computing. 2024, Vol. 53 Issue 6, p368-415. 48p.
Subjects: Computer science conferences, Symmetric functions, Open-ended questions, Symmetry, Polynomials
Abstract: Aaronson and Ambainis [Theory Comput., 10 (2014), pp. 133--166] and Chailloux [Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1--19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently--we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365--376] and Montanaro and de Wolf [Theory Comput., 7 (2016)]. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 182390680
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: SYMMETRIES, GRAPH PROPERTIES, AND QUANTUM SPEEDUPS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22BEN-DAVID%2C+SHALEV%22">BEN-DAVID, SHALEV</searchLink><relatesTo>1</relatesTo><i> shalev.b@uwaterloo.ca</i><br /><searchLink fieldCode="AR" term="%22CHILDS%2C+ANDREW+M%2E%22">CHILDS, ANDREW M.</searchLink><relatesTo>2</relatesTo><i> amchilds@umd.edu</i><br /><searchLink fieldCode="AR" term="%22GILYÉN%2C+ANDRÁS%22">GILYÉN, ANDRÁS</searchLink><relatesTo>3</relatesTo><i> gilyen@renyi.hu</i><br /><searchLink fieldCode="AR" term="%22KRETSCHMER%2C+WILLIAM%22">KRETSCHMER, WILLIAM</searchLink><relatesTo>4</relatesTo><i> kretsch@berkeley.edu</i><br /><searchLink fieldCode="AR" term="%22PODDER%2C+SUPARTHA%22">PODDER, SUPARTHA</searchLink><relatesTo>5</relatesTo><i> supartha@cs.stonybrook.edu</i><br /><searchLink fieldCode="AR" term="%22DAOCHEN+WANG%22">DAOCHEN WANG</searchLink><relatesTo>6</relatesTo><i> wdaochen@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2024, Vol. 53 Issue 6, p368-415. 48p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+science+conferences%22">Computer science conferences</searchLink><br /><searchLink fieldCode="DE" term="%22Symmetric+functions%22">Symmetric functions</searchLink><br /><searchLink fieldCode="DE" term="%22Open-ended+questions%22">Open-ended questions</searchLink><br /><searchLink fieldCode="DE" term="%22Symmetry%22">Symmetry</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Aaronson and Ambainis [Theory Comput., 10 (2014), pp. 133--166] and Chailloux [Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2018, pp. 19:1--19:7] showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent superpolynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow superpolynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs-where graph symmetry is manifested differently--we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu [Lecture Notes in Comput. Sci. 6845, Springer, 2011, pp. 365--376] and Montanaro and de Wolf [Theory Comput., 7 (2016)]. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=182390680
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/23M1573975
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 48
        StartPage: 368
    Subjects:
      – SubjectFull: Computer science conferences
        Type: general
      – SubjectFull: Symmetric functions
        Type: general
      – SubjectFull: Open-ended questions
        Type: general
      – SubjectFull: Symmetry
        Type: general
      – SubjectFull: Polynomials
        Type: general
    Titles:
      – TitleFull: SYMMETRIES, GRAPH PROPERTIES, AND QUANTUM SPEEDUPS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: BEN-DAVID, SHALEV
      – PersonEntity:
          Name:
            NameFull: CHILDS, ANDREW M.
      – PersonEntity:
          Name:
            NameFull: GILYÉN, ANDRÁS
      – PersonEntity:
          Name:
            NameFull: KRETSCHMER, WILLIAM
      – PersonEntity:
          Name:
            NameFull: PODDER, SUPARTHA
      – PersonEntity:
          Name:
            NameFull: DAOCHEN WANG
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: 2024
              Type: published
              Y: 2024
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 53
            – Type: issue
              Value: 6
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1