Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability

• URL: http://arxiv.org/abs/2602.20299v1
• Date: Mon, 23 Feb 2026 19:29:04 GMT
• Title: Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability
• Authors: Tim Pokart, Frank Pollmann, Jan Carl Budich,
• Abstract summary: We argue that a quantum entanglement barrier emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem.<n>Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement.
• Score: 0.003748389192021574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We approach the 3-SAT satisfiability problem with the quantum-inspired method of imaginary time propagation (ITP) applied to matrix product states (MPS) on a classical computer. This ansatz is fundamentally limited by a quantum entanglement barrier that emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem. Strikingly, we argue based on careful analysis of the structure imprinted onto the MPS by the 3-SAT instances that this barrier arises from classical computational complexity. To reveal this connection, we elucidate with stochastic models the specific relationship between the classical hardness of the $\sharp$P $\supseteq$ NP-complete counting problem $\sharp$3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.

Related papers

• Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set [0.0]
  We identify a family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm.<n>The algorithm runs in time and achieves an exponential speedup over both transverse-field quantum and state-of-the-art classical solvers.<n>This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist.
  arXiv  Detail & Related papers  (2026-01-25T04:18:35Z)
• Optimal quantum learning in proximity to universality [0.0]
  boundary between classically simulable and computationally superior quantum systems is fundamental to identifying true quantum advantage.<n>We introduce a tunable $N$-qubit random circuit model, where a fraction $p$ of Clifford gates are probabilistically substituted with nonstabilizing conditional-$hatT$ gates.<n>We establish a direct correspondence between the reservoir's performance on temporal processing tasks and its entanglement spectrum statistics and long-range nonstabilizer resource content.
  arXiv  Detail & Related papers  (2025-10-21T13:27:41Z)
• 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)
• 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)
• Limitations of Fault-Tolerant Quantum Linear System Solvers for Quantum Power Flow [1.0032961794537367]
  Quantum computers hold promise for solving problems intractable for classical computers.<n>Practical quantum advantage can be said to exist for such problems when the end-to-end time for solving such a problem exceeds that required by a quantum algorithm.<n>Speedup from using QPF algorithms is often claimed to be exponential when compared to classical PF solved by state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2024-02-13T17:36:18Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.306949367777188]
  There are problems for which there is no trivial' computational advantage possible with the current quantum hardware.<n>We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity?<n>By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
  arXiv  Detail & Related papers  (2023-09-28T13:30:20Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Learning the Complexity of Weakly Noisy Quantum States [0.5662299435213419]
  We present an efficient learning algorithm, that leverages the classical shadow representation of target quantum states, to predict the circuit complexity of weakly noisy quantum states.<n>Our result builds a bridge between the learning algorithm and quantum state complexity, highlighting the power of the learning algorithm in characterizing intrinsic properties of quantum states.
  arXiv  Detail & Related papers  (2023-03-31T06:02:44Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• 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)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)

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.