Classical Simulation of Quantum CSP Strategies

• URL: http://arxiv.org/abs/2503.23206v1
• Date: Sat, 29 Mar 2025 20:06:50 GMT
• Title: Classical Simulation of Quantum CSP Strategies
• Authors: Demian Banakh, Lorenzo Ciardo, Marcin Kozik, Jan Tułowiecki,
• Abstract summary: We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem can be simulated via a perfect classical strategy.<n>A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.
• Score: 2.7998963147546148
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on $(i)$ the size of the shared quantum system used in the quantum strategy, and $(ii)$ structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies. A key intermediate step of our proof is to establish that the gap between the classical chromatic number of graphs and its quantum variant is bounded when the quantum strategy involves shared quantum information of bounded size.

Related papers

• Multi-channel convolutional neural quantum embedding [10.620759775107787]
  We introduce a classical-quantum hybrid approach for optimizing quantum embedding beyond the limitations of the standard circuit model of quantum computation.<n>We benchmark the performance of various models in our framework using the CIFAR-10 and Tiny ImageNet datasets.
  arXiv  Detail & Related papers  (2025-09-26T13:51:40Z)
• QPing: a Quantum Ping Primitive for Quantum Networks [40.350859102407505]
  We introduce the concept of Quantum Ping (QPing) as a diagnostic primitive for future quantum networks.<n>We develop a formal framework for QPing and leverage different tools such as sequential hypothesis testing.<n>We present several strategies, including active strategies, with path-based and segment-based variants, and passive strategies that utilize pre-shared entangled resources.
  arXiv  Detail & Related papers  (2025-08-05T18:00:06Z)
• A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits [15.77466323653959]
  The intersection of quantum computing and quantum chemistry represents a promising frontier for achieving quantum utility in domains of both scientific and societal relevance.<n>We highlight near-term opportunities in algorithm and software design, discuss chemical problems suited to quantum acceleration, and propose strategic roadmaps and collaborative pathways for advancing practical quantum utility in quantum chemistry.
  arXiv  Detail & Related papers  (2025-06-24T06:02:25Z)
• Simulating quantum circuits with restricted quantum computers [0.0]
  This thesis is dedicated to the simulation of nonlocal quantum computation using local quantum operations. We characterize the optimal simulation overhead for a broad range of practically relevant nonlocal states and channels. We also investigate the utility of classical communication between the local parties.
  arXiv  Detail & Related papers  (2025-03-27T17:59:45Z)
• 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)
• Quantum Natural Stochastic Pairwise Coordinate Descent [6.187270874122921]
  Quantum machine learning through variational quantum algorithms (VQAs) has gained substantial attention in recent years. This paper introduces the quantum natural pairwise coordinate descent (2QNSCD) optimization method. We develop a highly sparse unbiased estimator of the novel metric tensor using a quantum circuit with gate complexity $Theta(1)$ times that of the parameterized quantum circuit and single-shot quantum measurements.
  arXiv  Detail & Related papers  (2024-07-18T18:57:29Z)
• An Operational Framework for Nonclassicality in Quantum Communication Networks [9.312605205492458]
  entanglement and quantum communication offer significant advantages in distributed information processing.<n>We develop an operational framework for realizing these enhancements in resource-constrained quantum networks.<n>In all cases, we find that entanglement-assisted communication, both classical and quantum, leads to nonclassicality.
  arXiv  Detail & Related papers  (2024-03-05T14:07:37Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Quantum Advantage Actor-Critic for Reinforcement Learning [5.579028648465784]
  We propose a novel quantum reinforcement learning approach that combines the Advantage Actor-Critic algorithm with variational quantum circuits. We empirically test multiple quantum Advantage Actor-Critic configurations with the well known Cart Pole environment to evaluate our approach in control tasks with continuous state spaces.
  arXiv  Detail & Related papers  (2024-01-13T11:08:45Z)
• Quantum Signal Processing with the one-dimensional quantum Ising model [0.0]
  Quantum Signal Processing (QSP) has emerged as a promising framework to manipulate and determine properties of quantum systems. We provide examples and applications of our approach in diverse fields ranging from space-time dual quantum circuits and quantum simulation, to quantum control.
  arXiv  Detail & Related papers  (2023-09-08T18:01:37Z)
• The Min-Entropy of Classical-Quantum Combs for Measurement-Based Applications [0.5999777817331317]
  We formalise multi-round learning processes using a generalisation of classical-quantum states, called classical-quantum combs. We focus attention on an array of problems derived from measurement-based quantum computation (MBQC) and related applications.
  arXiv  Detail & Related papers  (2022-12-01T15:01:19Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
  This letter proposes a novel quantum semantic communications (QSC) framework exploiting advancements in quantum machine learning and quantum semantic representations. The proposed framework achieves approximately 50-75% reduction in quantum communication resources needed, while achieving a higher quantum semantic fidelity.
  arXiv  Detail & Related papers  (2022-05-05T03:49:19Z)
• Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
  We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems. Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
  arXiv  Detail & Related papers  (2021-08-30T23:50:05Z)
• 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)

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.