The membership problem for constant-sized quantum correlations is undecidable

• URL: http://arxiv.org/abs/2101.11087v5
• Date: Wed, 09 Apr 2025 14:44:10 GMT
• Title: The membership problem for constant-sized quantum correlations is undecidable
• Authors: Honghao Fu, Carl A. Miller, William Slofstra,
• Abstract summary: We show there is a family of constant-sized correlations for which the number of measurements and number of measurement outcomes are fixed.<n>This places strong constraints on the types of descriptions that can be given for quantum correlation sets.<n>Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.
• Score: 0.8192907805418583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.

Related papers

• Experimental Test of Nonlocality Limits from Relativistic Independence [0.0]
  We show the existence of a fundamental limit on the extent of quantum correlations. Our results shed light on the profound role of uncertainty in both enabling and balancing them.
  arXiv  Detail & Related papers  (2025-01-10T23:29:00Z)
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits [37.69303106863453]
  We implement parameterized quantum circuits with definite and indefinite causal order. One of these is the expressibility, which measures how uniformly a given quantum circuit can reach the whole Hilbert space. We find a correlation between the quantum average causal effect and the entangling power.
  arXiv  Detail & Related papers  (2024-11-13T13:53:02Z)
• A computational test of quantum contextuality, and even simpler proofs of quantumness [43.25018099464869]
  We show that an arbitrary contextuality game can be compiled into an operational "test of contextuality" involving a single quantum device. Our work can be seen as using cryptography to enforce spatial separation within subsystems of a single quantum device.
  arXiv  Detail & Related papers  (2024-05-10T19:30:23Z)
• Semidefinite programming relaxations for quantum correlations [45.84205238554709]
  We discuss how the core idea of semidefinite relaxations can be adapted for a variety of research topics in quantum correlations. These topics include nonlocality, quantum communication, quantum networks, entanglement, and quantum cryptography.
  arXiv  Detail & Related papers  (2023-07-05T18:00:07Z)
• Quantifying total correlations in quantum systems through the Pearson correlation coefficient [0.23999111269325263]
  We show that a quantum state can be correlated in either a classical or a quantum way, i.e., the two cases are mutually exclusive. We also illustrate that, at least for the case of two-qubit systems, the distribution of the correlations among certain locally incompatible pairs of observables provides insight in regards to whether a system contains classical or quantum correlations.
  arXiv  Detail & Related papers  (2023-06-26T07:01:28Z)
• Causal classification of spatiotemporal quantum correlations [0.0]
  We show that certain quantum correlations possess an intrinsic arrow of time, and enable classification of general quantum correlations across space-time. Our results indicate that certain quantum correlations possess an intrinsic arrow of time, and enable classification of general quantum correlations across space-time based on their (in)compatibility with various underlying causal structures.
  arXiv  Detail & Related papers  (2023-06-15T17:59:18Z)
• Bell inequalities with overlapping measurements [52.81011822909395]
  We study Bell inequalities where measurements of different parties can have overlap. This allows to accommodate problems in quantum information. The scenarios considered show an interesting behaviour with respect to Hilbert space dimension, overlap, and symmetry.
  arXiv  Detail & Related papers  (2023-03-03T18:11:05Z)
• Entropic Accord: A new measure in the quantum correlation hierarchy [0.5039813366558306]
  We show a new measure of quantum correlations which we call entropic accord that fits between entanglement and discord. We study two-qubit states which shows the relationship between the three entropic quantities.
  arXiv  Detail & Related papers  (2022-05-13T07:16:50Z)
• 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)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• 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)
• Sampling and the complexity of nature [0.0]
  I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. I shed light on how and under which conditions quantum sampling devices can be tested or verified. An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths.
  arXiv  Detail & Related papers  (2020-12-14T19:35:27Z)
• Correlations for computation and computation for correlations [0.0]
  We connect quantum correlations with computation using 4-photon Greenberger-Horne-Zeilinger (GHZ) states. We show how the generated states can be used to specifically compute Boolean functions. The connection between quantum correlation and computability shown here has applications in quantum technologies.
  arXiv  Detail & Related papers  (2020-05-04T18:33:13Z)

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.