Classical simulation of universal measurement-based quantum computation using multipartite Bell scenarios

The gist: A new classical simulation algorithm based on non-signaling polytopes of multipartite Bell scenarios is introduced, capable of simulating universal measurement-based quantum computation with single-qubit Pauli measurements.

Introduction and Motivation

The paper introduces a new classical simulation algorithm based on non-signaling polytopes of multipartite Bell scenarios, which can simulate universal measurement-based quantum computation with single-qubit Pauli measurements The region of quantum states that can be efficiently simulated includes the Bell polytope and extends beyond what is currently achievable by sampling algorithms based on phase space methods. Understanding the reasons behind quantum computational advantage is a fundamental problem in theoretical quantum computing. A cornerstone result in this direction is the Gottesman–Knill theorem [1, 2], which states that stabilizer circuits can be efficiently classically simulated. Recently, a probabilistic representation of universal quantum computation on a finite state space consisting of the vertices of Λ polytopes was introduced in [11, 12]. In this work, we ask, “Are there other polytopes that provide a probabilistic representation of universal quantum computation?” We answer this question affirmatively by introducing a new simulation polytope, which we call the local Λ polytope Our simulation has fundamentally different complexity properties than the Λ simulation since our initial computational model is different. The local Λ polytope simulates quantum computations where the resource is a magic state, whereas our model works for quantum computations where the resource is also entangled. In the latter model, only single-qubit measurements are used, highlighting its local nature, in contrast to the former. These differences manifest in several ways: (1) Our simulation polytope is defined by a subset of the half-space inequalities of Λ, making the vertex enumeration problem easier. (2) Our polytope is closed under tensor product, meaning the tensor product of two vertices remains a vertex. (3) Our computational model uses destructive measurements, where each step of the simulation decreases the number of qubits, thus reducing the computational cost.

Computational Setting and Simulation Framework

The computational setting is defined as measurement-based Pauli computation (MBPC) In this model a computation initiates at a “magic cluster” state ψG,U ⟩ associated to a subset U of the qubits and a graph G determining the entanglement structure. This state is obtained by preparing the qubits in +⟩, the +1-eigenstate of the Pauli X operator, applying the T gate to a subset U of these qubits, and then entangling with E(G) = N eij Eij, a product of controlled-Z operations Eij acting on the ith and jth qubits connected by an edge eij. The computation proceeds with a sequence of adaptive single-qubit Pauli X and Y measurements on this initial state and is universal [13], see also [14]. For a uniform treatment of computational models based on destructive (e.g., MBQC) and non-destructive (e.g., QCM) measurements, we will use instruments [17]. An adaptive instrument consists of instruments Φa labeled by inputs a ∈ Γ Given another adaptive instrument Ψ with outcome set Θ and whose input set is the same as the outcome set of Φ, we can compose them to obtain the adaptive instrument Ψ ◦ Φ defined by (Θ ◦ Φ)r a = X s∈Σ Ψ r s ◦ Φ s a with inputs a ∈ Γ and outcomes r ∈ Θ.

Classical Simulation Algorithm

Classical simulation algorithms based on quasi-probability distributions rely on the same principle of sampling from a state space The state space consists of a subset of an operator-theoretic polytope, typically the set of its vertices. Let P be a polytope in the space Herm1(H) of traceone Hermitian operators and V (P) ⊆ P be a subset of operators which will be the state space associated to the polytope We require that P is the convex hull of this set. Elements of this set will be denoted by Aα, where α is the state label. Given polytopes P ⊆ Herm1(H) and Q ⊆ Herm1(K), we say that an instrument Φ preserves the pair (P, Q) if for all A ∈ P and s ∈ Σ, we have Tr(Φs (A)) ≥ 0 and the following two properties hold: (1) Tr(Φs (A)) > 0 implies Φ s (A) Tr(Φs(A)) ∈ Q (2) Tr(Φs (A)) = 0 implies Φ s (A) = 0. If Φ preserves (P, Q) then we can define an update map q = qα α∈V (P) consisting of probability distributions qα: V (Q) × Σ → R≥0 defined by Property (1): Φ s (A) = X β∈V (Q) qα(β, s)Aβ and for all s ∈ Σ, the following equation holds: Φ s (A) = X β Pr(s, β)Aβ where Pr(s, β) is the probability that outcome s and state β are obtained in the simulation. Theorem 1 states that the classical simulation algorithm given in Algorithm 1 is correct.

Local Λ Polytope Characterization

Definition 1 defines the local Λ-polytope as Λln = The local Λ-polytope is defined by Λln = The local Λ-polytope is defined byΛln = The set of operators A in Herm1(H): Tr(ψ⟩ ⟨ψ A) ≥ 0, ∀ ψ⟩ ∈ Sln Our second main result is the operational characterization of local Λ polytopes, which, together with Theorem 1, enables classical simulation of universal quantum computation in the MBPC model. Theorem 2 states that the local Λ polytope corresponds to the largest polytope within Herm1(H) that is preserved by all single-qubit Pauli measurements, both destructive and non-destructive

Bell Scenarios and Vertices

Theorem 3 identifies the local Λ polytope with the non-signaling polytope NSn of the (n, 3, 2) Bell scenario under the mapping that sends an operator A to the probability distribution p s1···sn a1···an = Tr(Πs1 a1 · · · Πsn an A) This map is injective since the local stabilizer states are spanned by Herm1(H). The polytope Λln can be identified with the non-signaling polytope NSn of the (n, 3, 2) Bell scenario under the mapping that sends an operator A to the probability distribution p s1···sn a1···an = Tr(Πs1 a1 · · · Πsn an A).

Locally Closed Operators and Efficiency

We introduce locally closed operators A γ Ω = The associated locally closed operator is defined by A γ Ω = 1/2 n X a∈omega (−1)γ(a)Ta Lemma 1 states that if (omega, γ) is maximal with respect to the partial order ⪯ than A γ Ω is a vertex of Λlc n Corollary 2 states that the max-weight vertices of Λln are also vertices of Λlc n. The hardness of the associated classical simulation depends on the vertex enumeration problem and the update rules in Eq. (1).

Efficiency Comparison

The local robustness measure Rl(ρ) defined with respect to the polytope Λeffn defined as the convex hull of Veffn satisfies Rl(ρ) ≤ RC (ρ) ≤ RS (ρ) This implies that our methods strictly extend the known region of efficiently simulatable quantum states beyond the CNC regime. The simulation of CMBPC using operators in Veffn is more efficient than the simulation of CPBC using CNC operators. Numerical results indicate that for three qubits, Rl(ψ⟩ ⟨ψ) = Rl(ψG,U ⟩ ⟨ψG,U) where ψG,U ⟩ = E(G)T⟩ ⊗3.

Tensor Structure

The tensor product of vertices of the local Λ polytope remains to be a vertex Corollary 1 states that given vertices Aαi ∈ Λln, where i = 1, 2, the tensor product Aα1 ⊗ Aα2 is a vertex of Λn1+n2.

Supplementary Material Insights

The paper discusses two versions of the MBPC model: QCM and MBQC The initial state in QCM is the magic cluster state ψG,U ⟩ = E(G)T ⊗U +⟩ ⊗n where T ⊗U acts by T on a subset U of qubits.

1. Abstracting Quantum Computation Simulation via Local Pauli Polytopes: Enables Efficient Classical Modeling of Measurement-Based Quantum Computation (MBPC) with Single-Qubit Measurements by defining a new simulation polytope, the local Λ polytope, which simulates quantum computations where the resource is also entangled. This allows AI systems to efficiently simulate universal MBPC using only single-qubit Pauli measurements, contrasting with previous models that required magic states or non-stabilizerness for speedup.

2. Enhanced Simulation of Universal Quantum Computation via Destructive Measurements: The classical simulation algorithm, Algorithm 1, is correct because the post-measurement states match the quantum mechanical post-measurement states, allowing the simulation to produce probabilities Pr(s1s2 · · · sN) that are same as the quantum mechanical process. This enables AI systems to accurately model and predict outcomes of complex quantum processes initiated by a magic cluster state ψG,U ⟩.

3. Model for Resource-Constrained Quantum Advantage: The paper highlights that the simultaneous presence of non-stabilizerness and entanglement is necessary for quantum speedup, enabling AI to identify specific computational regimes where quantum advantage is expected. This allows AI to determine if a given problem instance falls within the efficiently simulatable region defined by the local Λ polytope, or if it requires resources beyond this class, such as those related to contextuality.

4. Categorization of Quantum State Simulation Complexity: The classification of states into classes like LC2 LC1 DET CNC STAB (Table I) allows AI systems to assess the inherent computational hardness of a quantum state simulation. By comparing the robustness measures, one can determine if simulating a specific resource state is strictly more efficient than simulations within the CNC phase space, leading to optimized classical algorithms for that specific resource type.

5. Handling Tensor Product Structure in Simulation: The theorem stating Corollary 1 Given vertices Aαi ∈ Λln, where i = 1, 2, the tensor product Aα1 ⊗ Aα2 is a vertex of Λn1+n2 allows AI systems to efficiently handle the complexity of simulating larger quantum systems by leveraging the tensor product structure in GPT frameworks. This permits the simulation of CMBPC using operators in Veff n is more efficient than the simulation of CPBC using CNC operators.