Unconditional and exponentially large violation of classicality

• URL: http://arxiv.org/abs/2511.11008v1
• Date: Fri, 14 Nov 2025 06:53:00 GMT
• Title: Unconditional and exponentially large violation of classicality
• Authors: Marcello Benedetti, Gabriel Marin-Sanchez, Jordi Weggemans, Matthias Rosenkranz, Harry Buhrman,
• Abstract summary: We propose to test non-classicality using a game based on complement sampling.<n>We execute the game on Quantinuum System Model H2 trapped-ion quantum computers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Testing the predictions of quantum mechanics has been one of the main experimental endeavors for decades. Recent advancements in technology led to a number of demonstrations which test non-classicality via specific computational tasks. Limitations of these experiments include dependence on complexity theory assumptions, susceptibility to hardware noise and inefficient verification, raising questions about their scalability. We propose to test non-classicality using a game based on complement sampling, an efficiently verifiable problem that achieves the largest possible separation between quantum and classical computation when both input and output represent samples from probability distributions. When restricting the input to instances inspired by the Bernstein-Vazirani problem, our game admits an exponentially large violation of classicality without relying on computational hardness assumptions. We execute the game on Quantinuum System Model H2 trapped-ion quantum computers, with experiments consisting of thousands of different circuits on up to 55 qubits. The observed scores can be explained by a systematic adoption of a quantum strategy, further corroborating the quantum nature of the hardware in an efficient and scalable way.

Related papers

• Quantum-Classical Separation in Bounded-Resource Tasks Arising from Measurement Contextuality [107.84586711462556]
  We show that quantum contextuality enables certain tasks to be performed with success probabilities beyond classical limits.<n>Our work proposes novel ways to benchmark quantum processors using contextuality-based algorithms.
  arXiv  Detail & Related papers  (2025-12-01T23:54:32Z)
• Demonstrating an unconditional separation between quantum and classical information resources [1.4850289280359021]
  We demonstrate an unconditional quantum advantage in information resources required for a computational task.<n>We construct a task for which the most space-efficient classical algorithm provably requires between 62 and 382 bits of memory, and solve it using only 12 qubits.<n>This form of quantum advantage represents a new benchmark in quantum computing.
  arXiv  Detail & Related papers  (2025-09-08T22:18:27Z)
• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  This thesis is centered around simulating quantum dynamics on quantum devices.<n>We present an overview of the most relevant quantum algorithms for quantum dynamics.<n>We identify relevant problems within quantum dynamics that could benefit from quantum simulation in the near future.
  arXiv  Detail & Related papers  (2025-08-29T10:37:19Z)
• Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors [0.48520567143062737]
  The Maximum Independent Set (MIS) problem is a fundamental optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors.<n>Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS.<n>We generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth.
  arXiv  Detail & Related papers  (2025-02-06T18:34:59Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Beyond-classical computation in quantum simulation [21.45294717016955]
  We show that superconducting quantum annealing processors can generate samples in close agreement with solutions of the Schr"odinger equation.<n>We demonstrate area-law scaling of entanglement in the model quench dynamics of two-, three-, and infinite-dimensional spin glasses.<n>We show that several leading approximate methods based on tensor networks and neural networks cannot achieve the same accuracy as the quantum annealer.
  arXiv  Detail & Related papers  (2024-03-01T19:00:04Z)
• The hardness of quantum spin dynamics [1.1999555634662633]
  We show that sampling from the output distribution generated by a wide class of quantum spin Hamiltonians is a hard problem for classical computers. We estimate that an instance involving about 200 spins will be challenging for classical devices but feasible for intermediate-scale quantum computers with fault-tolerant qubits.
  arXiv  Detail & Related papers  (2023-12-12T19:00:03Z)
• Machine learning on quantum experimental data toward solving quantum many-body problems [0.0]
  We demonstrate the successful implementation of classical machine learning algorithms for systems with up to 44 qubits. We extend the applicability of the hybrid approach to problems of interest in many-body physics.
  arXiv  Detail & Related papers  (2023-10-30T10:25:59Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• Experimental Implementation of an Efficient Test of Quantumness [49.588006756321704]
  A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification.
  arXiv  Detail & Related papers  (2022-09-28T18:00:04Z)
• 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)
• 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)

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.