Symmetries, graph properties, and quantum speedups

• URL: http://arxiv.org/abs/2006.12760v1
• Date: Tue, 23 Jun 2020 05:00:15 GMT
• Title: Symmetries, graph properties, and quantum speedups
• Authors: Shalev Ben-David, Andrew M. Childs, Andr\'as Gily\'en, William Kretschmer, Supartha Podder, Daochen Wang
• Abstract summary: We show that hypergraph symmetries in the adjacency matrix model allow at most a 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 super-polynomial quantum speedups.
• Score: 3.4253416336476246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Aaronson and Ambainis (2009) and Chailloux (2018) 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 super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial 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 (2010) and Montanaro and de Wolf (2013).

Related papers

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Non-equilibrium dynamics of charged dual-unitary circuits [44.99833362998488]
  interplay between symmetries and entanglement in out-of-equilibrium quantum systems is currently at the centre of an intense multidisciplinary research effort. We show that one can introduce a class of solvable states, which extends that of generic dual unitary circuits. In contrast to the known class of solvable states, which relax to the infinite temperature state, these states relax to a family of non-trivial generalised Gibbs ensembles.
  arXiv  Detail & Related papers  (2024-07-31T17:57:14Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Studying Stabilizer de Finetti Theorems and Possible Applications in Quantum Information Processing [0.0]
  In quantum information theory, if a quantum state is invariant under permutations of its subsystems, its marginal can be approximated by a mixture of powers of a state on a single subsystem. Recently, it has been discovered that a similar observation can be made for a larger symmetry group than permutations. This naturally raises the question if similar improvements could be found for applications where this symmetry appears.
  arXiv  Detail & Related papers  (2024-03-15T17:55:12Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• Quantum squeezing and sensing with pseudo anti-parity-time symmetry [0.0]
  We construct a quantum pseudo-anti-$mathcalPT$ symmetry in a two-mode bosonic system without involving Langevin noises. We show that the spontaneous pseudo-$mathcalAPT$ symmetry breaking leads to an exceptional point. Such dramatic changes of squeezing factors and quantum dynamics near the exceptional point are utilized for ultra-precision quantum sensing.
  arXiv  Detail & Related papers  (2021-08-29T16:28:28Z)
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
  Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely. We present a new approach for quantum self-testing in Bell non-locality scenarios.
  arXiv  Detail & Related papers  (2021-04-27T08:15:01Z)
• Complete entropic inequalities for quantum Markov chains [17.21921346541951]
  We prove that every GNS-symmetric quantum Markov semigroup on a finite dimensional algebra satisfies a modified log-Sobolev inequality. We also establish the first general approximateization property of relative entropy.
  arXiv  Detail & Related papers  (2021-02-08T11:47:37Z)
• On Representing (Anti)Symmetric Functions [19.973896010415977]
  We derive natural approximations in the symmetric case, and approximations based on a single generalized Slater in the anti-symmetric case. We provide a complete and explicit proof of the Equivariant MultiLayer Perceptron, which implies universality of symmetric universalitys and the FermiNet.
  arXiv  Detail & Related papers  (2020-07-30T08:23:33Z)
• Can graph properties have exponential quantum speedup? [5.101801159418223]
  In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties. We show that the answer to this question depends strongly on the input model.
  arXiv  Detail & Related papers  (2020-01-28T18:45:48Z)
• How symmetric is too symmetric for large quantum speedups? [0.0]
  We make steps towards understanding the group actions $G$ which are "quantum intolerant" We show that a "well-shuffling" property of group actions -- which happens to be preserved by several natural transformations -- does not allow a quantum speedup. This means no graph property testing problems can have super-polynomial quantum speedups.
  arXiv  Detail & Related papers  (2020-01-27T09:34:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.