Quantum Advantage and CSP Complexity

• URL: http://arxiv.org/abs/2404.13186v1
• Date: Fri, 19 Apr 2024 21:23:03 GMT
• Title: Quantum Advantage and CSP Complexity
• Authors: Lorenzo Ciardo,
• Abstract summary: Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as a computational resource. We prove that the occurrence of quantum advantage is determined by the same type of algebraic structure that captures the polymorphism identities of CSPs.
• Score: 1.90365714903665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as a computational resource. We prove that the occurrence of quantum advantage is determined by the same type of algebraic structure (known as a minion) that captures the polymorphism identities of CSPs and, thus, CSP complexity. We investigate the connection between the minion of quantum advantage and other known minions controlling CSP tractability and width. In this way, we make use of complexity results from the algebraic theory of CSPs to characterise the occurrence of quantum advantage in the case of graphs, and to obtain new necessary and sufficient conditions in the case of arbitrary relational structures.

Related papers

• Quantum Polymorphisms and Commutativity Gadgets [2.8726155411976535]
  We give a full characterisation of the existence of commutativity gadgets for relational structures.<n>We prove that the entangled CSP parameterised by odd cycles is undecidable.<n>We establish a quantum version of Galois connection for entangled CSPs in the case of non-oracular quantum homomorphisms.
  arXiv  Detail & Related papers  (2025-11-28T18:37:36Z)
• Temporal Complexity Hierarchies in Solvable Quantum Many-Body Dynamics [0.3499902777050122]
  The influence matrix (IM) provides a powerful framework for characterizing nonequilibrium quantum many-body dynamics.<n>Here, we analyze the memory structure of the IM and distinguish between classical and quantum temporal correlations.<n>Our results establish a new connection between quantum many-body dynamics and group theory.
  arXiv  Detail & Related papers  (2025-10-24T18:00:08Z)
• Quantum complexity phase transition in fermionic quantum circuits [14.723621424225973]
  We develop a general scaling theory for Krylov complexity phase transitions on quantum percolation models.<n>For non-interacting systems across diverse lattices, our scaling theory reveals that the KCPT coincides with the classical percolation transition.<n>For interacting systems, we find the KCPT develops a generic separation from the percolation transition due to the highly complex quantum many-body effects.
  arXiv  Detail & Related papers  (2025-07-29T18:00:25Z)
• Bounding the computational power of bosonic systems [0.0]
  We show that universal bosonic quantum computations can be simulated in exponential time on a classical computer.<n>We also present arguments supporting the plausibility of an exponential computational advantage of bosonic quantum computers over their discrete-variable counterparts.
  arXiv  Detail & Related papers  (2025-03-05T15:33:51Z)
• Quantum reservoir computing on random regular graphs [0.0]
  Quantum reservoir computing (QRC) is a low-complexity learning paradigm that combines input-driven many-body quantum systems with classical learning techniques. We study information localization, dynamical quantum correlations, and the many-body structure of the disordered Hamiltonian. Our findings thus provide guidelines for the optimal design of disordered analog quantum learning platforms.
  arXiv  Detail & Related papers  (2024-09-05T16:18:03Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  We study the query complexity of Boolean functions under general higher order quantum computations. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity. We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
  arXiv  Detail & Related papers  (2023-07-18T13:12:55Z)
• Resource-Dependent Complexity of Quantum Channels [5.633571140534384]
  We introduce a new framework for quantifying the complexity of quantum channels.<n>This class of convex functions is designed to analyze the complexity of both open and closed quantum systems.
  arXiv  Detail & Related papers  (2023-03-20T17:44:57Z)
• stateQIP = statePSPACE [0.15229257192293197]
  We study the relation between two such state classes:SDPPSPACE, and stateQIP. Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE. We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
  arXiv  Detail & Related papers  (2023-01-18T19:00:17Z)
• Quantum Causal Unravelling [44.356294905844834]
  We develop the first efficient method for unravelling the causal structure of the interactions in a multipartite quantum process. Our algorithms can be used to identify processes that can be characterized efficiently with the technique of quantum process tomography.
  arXiv  Detail & Related papers  (2021-09-27T16:28:06Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Entanglement Classification via Neural Network Quantum States [58.720142291102135]
  In this paper we combine machine-learning tools and the theory of quantum entanglement to perform entanglement classification for multipartite qubit systems in pure states. We use a parameterisation of quantum systems using artificial neural networks in a restricted Boltzmann machine (RBM) architecture, known as Neural Network Quantum States (NNS)
  arXiv  Detail & Related papers  (2019-12-31T07:40:23Z)

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.