The trading of fidelity for scale enables approximate classical simulators such as matrix product states (MPSs) to run quantum circuits beyond exact methods.A control parameter, the so-called bond dimension χ for MPSs, governs the allocated computational resources and the output fidelity.Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function that it seeks to minimize and find that it follows a scaling law F ln χ N , where N is the number of qubits.With ln χ amounting to the entanglement that a MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit.Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup.For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function.Moreover, we relate the global fidelity to that of individual operations and establish its relationship with χ and N .We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.
The trading of fidelity for scale enables approximate classical simulators such as matrix product states (MPSs) to run quantum circuits beyond exact methods.A control parameter, the so-called bond dimension χ for MPSs, governs the allocated computational resources and the output fidelity.Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function that it seeks to minimize and find that it follows a scaling law F ln χ N , where N is the number of qubits.With ln χ amounting to the entanglement that a MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit.Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup.For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function.Moreover, we relate the global fidelity to that of individual operations and establish its relationship with χ and N .We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.
The role of entanglement in quantum optimization remains actively debated. To address this question, we focus on the fixed-parameter expanding-depth regime of the quantum approximate optimization algorithm (QAOA), where a compact two-parameter schedule is trained once on small instances and then applied as the problem size and circuit depth increase. To probe this regime beyond full state-vector simulation, we perform approximate matrix product state simulations for up to 50 qubits and 100 layers and quantify entanglement by the bond dimension. We observe an entangle--disentangle profile, with the peak bond dimension decreasing with depth and eventually saturating. This observation motivates an extreme approximation: projecting the state onto the product-state manifold (bond dimension one) after every two-qubit interaction. Based on this approximation, we introduce BOND-1, a quantum-inspired classical solver. Despite the drastic simplification, BOND-1 achieves cut ratios above 0.95 relative to the best known values on standard GSet MaxCut benchmarks with up to 20000 variables, and in some cases it matches those values. It achieves these results without per-instance optimization and has linear memory cost, while per-instance tuning can provide further improvement. These results show that, in this regime, a substantial fraction of the optimization power of QAOA survives even in the complete absence of entanglement. Our conclusions, however, are specific to this setting and do not imply that entanglement is unnecessary for quantum optimization in general.
The advent of quantum computers promises exponential speed ups in the execution of various computational tasks. While their capabilities are hindered by quantum decoherence, they can be exactly simulated on classical hardware at the cost of an exponential scaling in terms of number of qubits. To circumvent this, quantum states can be represented as matrix product states (MPS), a product of tensors separated by so-called bond dimensions. Limiting bond dimensions growth approximates the state, but also limits its ability to represent entanglement. Methods based on this representation have been the most popular tool at simulating large quantum systems. But how to trust resulting approximate quantum states for such intractable systems sizes ? I propose here a method for inferring the fidelity of an approximate quantum state without direct comparison to its exact counterpart, and use it to design an ``entanglement-aware'' (EA) algorithm for both pure and mixed states. As opposed to state of the art methods which limit bond dimensions up to an arbitrary maximum value, this algorithm receives as input a fidelity, and adapts dynamically its bond dimensions to both local entanglement and noise such that the final quantum state fidelity at least reaches the input fidelity. I show that this algorithm far surpasses standard fixed bond dimension truncation schemes. In particular, a noiseless random circuit of 300 qubits and depth 75 simulated using MPS methods takes one week of computation time, while EA-MPS only needs 2 hours to reach similar quantum state fidelity.
Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers. However, it is unknown if these heuristic algorithms provide any quantum-computational speedup, although we cannot simulate them classically for intermediate sizes. Since entanglement lies at the core of quantum computing power, we investigate its role in these heuristic methods for solving optimization problems. In particular, we use matrix product states to simulate the quantum approximate optimization algorithm with reduced bond dimensions D, a parameter bounding the system entanglement. Moreover, we restrict the simulation further by deterministically sampling solutions. We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here since the simulated algorithm analysis, with up to 60 qubits and p=100 algorithm layers, shows that it provides solutions for bond dimension D≈10 and depth p≈30. Additionally, we study the classical optimization loop in the approximated algorithm simulation with 12 qubits and depth up to p=4 and show that the approximated optimal parameters with low entanglement approach the exact ones.
We introduce a family of quantum circuits that possess standard indicators of classical simulation hardness including high entanglement entropy, magic, and non-Gaussianity, yet admit efficient classical simulation via matrix product states (MPS). Our construction uses logical circuits of high-rate Calderbank-Shor-Steane (CSS) codes with enhanced symmetries. Using code automorphisms and transversal diagonal gates from higher levels of the Clifford hierarchy, we realize nonlocal logical Clifford and non-Clifford gates, showing how error-correcting codes can compile complex logical circuits into simple physical operations. Simulation efficiency rests on two properties: (i) diagonal transversal gates do not increase bond dimension, and (ii) permutations are tracked classically via on-the-fly relabeling, avoiding costly SWAP networks. Unlike Clifford or matchgate simulation, our method accepts a broad class of initial states, including dense entangled, magic, and non-Gaussian inputs, provided the encoded state retains an efficient MPS representation. We also release an exact phase-polynomial backend for monomial subfamilies, whose cost is set by higher-degree phase terms rather than entanglement growth. We demonstrate the method on an infinite polar CSS code family, showing bond dimension stays bounded by the encoding cost regardless of circuit depth. These results show that for some circuit families, standard resource measures are individually insufficient to indicate simulation hardness. As a near-term application, we use the compiled MPS as a classical reference for direct fidelity estimation of a quantum device running nontrivial logical circuits. Pauli sampling on the encoded reference, with a Clifford pushback through the known encoder, provides the ideal expectation values, so the logical output fidelity can be estimated from local Pauli readout alone, without costly state tomography.
Multipartite entanglement offers a powerful framework for understanding the complex collective phenomena in quantum many-body systems that are often beyond the description of conventional bipartite entanglement measures. Here, we propose a class of multipartite entanglement measures that incorporate the matrix product state (MPS) representation, enabling the characterization of the optimality of quantum circuits for state preparation. These measures are defined as the minimal distances from a target state to the manifolds of MPSs with specified virtual bond dimensions χ, and thus are dubbed as χ-specified matrix product entanglement (χ-MPE). We demonstrate superlinear, linear, and sublinear scaling behaviors of χ-MPE with respect to the negative logarithmic fidelity F in state preparation, which correspond to excessive, optimal, and insufficient circuit depth D for preparing χ-virtual-dimensional MPSs, respectively. Specifically, a linearly growing χ-MPE with F suggests H_{χ}≃H_{D}, where H_{χ} denotes the manifold of the χ-virtual-dimensional MPSs and H_{D} denotes that of the states accessible by the D-layer circuits. We provide an exact proof that H_{χ=2}≡H_{D=1}. Our results establish tensor networks as a powerful and general tool for developing parametrized measures of multipartite entanglement. The matrix product form adopted in χ-MPE can be readily extended to other tensor network Ansätze, whose scaling behaviors are expected to assess the optimality of quantum circuit in preparing the corresponding tensor network states.
Matrix product states (MPSs) and matrix product operators (MPOs) have been proven to be a powerful tool to study quantum many-body systems but are restricted to moderately entangled states as the number of parameters scales exponentially with the entanglement entropy. While MPSs can efficiently find ground states of one-dimensional systems, their capacities are limited when simulating their dynamics, where the entanglement can increase ballistically with time. On the other hand, quantum devices appear as a natural platform to encode and perform the time evolution of correlated many-body states. However, accessing the regime of long-time dynamics is hampered by quantum noise. In this paper we use the best of worlds: the short-time dynamics is efficiently performed by MPSs, compiled into short-depth quantum circuits, and performed further in time on a quantum computer thanks to efficient MPO-optimized quantum circuits. We quantify the capacities of this hybrid classical-quantum scheme in terms of fidelities taking into account a noise model. We show that using classical knowledge in the form of tensor networks provides a way to better use limited quantum resources and lowers the noise requirements to reach a practical quantum advantage. Finally, we successfully demonstrate our approach with an experimental realization of the technique. Combined with efficient circuit transpilation we simulate a ten-qubit system on an actual quantum device over a longer time scale than low-bond-dimension MPSs and purely quantum Trotter evolution.