Certifying localizable quantum properties with constant sample complexity

This paper introduces a scalable certification framework based on "localizable quantumness" that enables the verification of global quantum properties like entanglement, complexity, and magic in large many-body systems using only local measurements with constant sample complexity and robustness, thereby overcoming the prohibitive experimental costs of previous methods.

The Gist

Imagine you have a giant, incredibly complex quantum machine with hundreds of tiny parts (qubits). You want to know if it's working correctly and if it possesses special "quantum magic" (like entanglement or high complexity).

The problem is that checking the whole machine is like trying to read every single page of a million-page book to find one typo. It takes too long, costs too much, and is practically impossible.

This paper introduces a clever new way to check these machines. Instead of reading the whole book, you only need to read a few pages, but you do it in a very specific way that tells you everything about the whole story.

Here is the breakdown of their method using simple analogies:

1. The Core Idea: "Localizable Quantumness"

Think of the quantum system as a giant, intricate tapestry. Usually, if you cut out a small square of the tapestry, it looks like just a bunch of random threads. It doesn't tell you the whole picture.

The authors discovered a special property they call "Localizable Quantumness." They found that for many complex quantum states, the "specialness" of the whole tapestry is actually hidden inside small patches of it.

The Analogy: Imagine a massive, complex orchestra playing a symphony. If you listen to the whole room, it's a wall of sound. But the authors found that if you put a microphone on just one violin (a small part) while the rest of the orchestra plays a specific, random rhythm, that single violin will suddenly start playing a melody that proves the entire orchestra is playing a complex, high-level symphony. The "complexity" of the whole group gets "concentrated" into that one small spot.

2. The Method: The "Shadow" Trick

How do they check this small spot?

• Step 1: The Big Cut. They take the big quantum system and measure most of it (the "complement"). This is like asking the rest of the orchestra to play a specific, random note and then going silent.
• Step 2: The Projection. Because of the laws of quantum physics, measuring the big part forces the small part (the "subsystem") to collapse into a specific state. This is called a "projected ensemble."
• Step 3: The Comparison. They then take a simple look at this small, collapsed state. They compare it to what they expected it to look like if the machine was perfect.

The Analogy: It's like a detective solving a crime. Instead of interviewing every suspect in the city (the whole system), the detective asks the city to "freeze" in a specific way. When the city freezes, a single witness (the small subsystem) steps forward. If that witness looks exactly like the "perfect" witness the detective expects, the detective knows the whole city is innocent. If the witness looks weird, the whole system is flawed.

3. Why This is a Game-Changer

Previous methods had two big problems:

1. They needed too many samples: To be sure, you had to check the system thousands or millions of times.
2. They were fragile: If the machine was even a little bit noisy (like a slightly out-of-tune violin), the test would fail, even if the machine was mostly working.

The Paper's Solution:

• Constant Samples: Their method works with a fixed, tiny number of samples, no matter how big the machine is. Whether you have 10 qubits or 1,000 qubits, you only need to check a few times. It's like needing only 5 seconds of listening to know if the orchestra is playing a symphony, rather than 5 hours.
• Robustness: It works even if the machine is a bit "noisy" or imperfect. It can tell the difference between a machine that is "mostly good" and one that is "completely broken."
• Mixed States: It works even if the machine isn't in a perfect, pure state (which is almost always the case in real life).

4. What They Can Check

Using this "small patch" method, they can certify three major things:

• Entanglement: Proving that parts of the machine are deeply connected in a way classical computers can't do.
• Circuit Complexity: Proving that the machine is doing something truly hard and complex, not just a simple trick.
• Quantum Magic: Proving the machine has the specific "fuel" (non-stabilizer states) needed for advanced quantum computing tasks.

5. The "Random Basis" Bonus

For checking how close the machine is to the exact ideal state (Fidelity), they added a twist: instead of measuring the big part in just one way, they measure it in random directions (like looking at the tapestry from different angles).

• The Result: They proved mathematically that for certain types of states (like "graph states"), this random approach also works with a constant, tiny number of samples.
• The Evidence: For other types of states, their computer simulations strongly suggest it works just as well, even though they haven't mathematically proven it for every possible state yet.

Summary

The paper says: "We found a way to check if a giant, complex quantum computer is working correctly by only looking at a tiny piece of it, after asking the rest of it to do a specific random dance. This check is fast (constant samples), tough against noise, and works for many different types of quantum 'magic'."

This provides a practical toolkit for scientists to verify large-scale quantum processors without needing impossible amounts of time or resources.

Technical Summary

Technical Summary: Certifying Localizable Quantum Properties with Constant Sample Complexity

Problem Statement

Characterizing increasingly complex quantum systems is a central challenge in quantum information science. While full state tomography provides complete information, its experimental cost scales exponentially with system size, rendering it prohibitive for large-scale devices. Existing certification protocols that rely on simple local measurements face significant limitations: they are often tailored to specific states or properties, require demanding adaptive measurement schemes, guarantee soundness only for pure states, or suffer from sample complexity that grows with system size and diminishing robustness against noise. There is a critical need for a general, scalable, and experimentally feasible framework to certify global quantum properties—such as entanglement, circuit complexity, and quantum magic—using only local measurements with constant sample complexity and robustness, even for mixed states.

Methodology

The authors introduce a unified certification framework based on a physical phenomenon they term localizable quantumness. The core insight is that for generic many-body states, essential global quantum properties are robustly preserved within the projected ensembles on small subsystems after performing local projective measurements on the rest of the system.

The methodology proceeds in three main stages:

1. Partitioning and Projection: The $n$-qubit system is partitioned into a small, accessible subsystem $A$ and a large complement $B$. Local projective measurements (typically in the computational basis, though a random-basis variant is also proposed) are performed on $B$. This generates a projected ensemble $\mathcal{E}_\rho = \{p_\rho(z), \rho_z\}$ on subsystem $A$, where $z$ is the measurement outcome and $\rho_z$ is the resulting state on $A$.
2. Conditional Fidelity Witness: The framework defines a conditional fidelity observable, $\eta_\psi(\rho)$, which acts as a witness for a target property $P$. This observable compares the projected ensemble of the experimental state $\rho$ against that of a known target state $\psi$. Specifically, it evaluates the ensemble-averaged local fidelity between projected states $\rho_z$ and $\psi_z$, shifted by the maximal fidelity of $\psi_z$ to any "free" state (a state lacking property $P$).
   • If the target state $\psi$ exhibits localizable quantumness, its projected states $\psi_z$ remain far from the set of free projected states ($F_{PP}$) even after measurements on $B$.
   • Consequently, $\eta_\psi(\rho)$ yields a positive value for $\psi$ but remains non-positive for any free state $\rho \in F_P$.
3. Estimation via Local Shadows: The protocol estimates $\eta_\psi(\rho)$ using only non-adaptive local Pauli measurements on the small subsystem $A$. By employing local classical shadows and the median-of-means estimator, the protocol efficiently estimates the required ensemble averages. This avoids the intractable task of directly evaluating nonlinear quantities over the full projected ensemble.

Key Contributions

The paper makes several theoretical and practical contributions:

• Formalization of Localizable Quantumness: The authors formalize the concept that global quantum resources (entanglement, complexity, magic) can be concentrated into small subsystems via local measurements on the complement. They prove that this phenomenon holds with high probability for Haar-random states, random brickwork-circuit states, and generic states generated by shallow chaotic circuits.
• Constant Sample Complexity: The protocol achieves $O(1)$ sample complexity for certifying properties like bipartite entanglement, quantum magic, and circuit complexity (for constant depth), provided the subsystem size $|A|$ is constant. This represents an exponential improvement over previous methods where sample complexity typically scales with system size.
• Soundness for Mixed States: Unlike many prior approaches restricted to pure states, this framework guarantees soundness for mixed states. It robustly rejects any mixed state lacking the target property.
• Constant Robustness: The protocol maintains constant-level robustness ($\epsilon = \Omega(1)$) against deviations from the target state. This is a significant improvement over methods where robustness diminishes as $O(1/\text{poly}(n))$, making the protocol viable for realistic, noisy intermediate-scale quantum (NISQ) devices.
• Unified Framework for Diverse Properties: The framework is applied to certify:
  • Quantum Circuit Complexity: Certifying that a state requires a circuit depth exceeding a constant threshold, including for measurement-assisted circuits.
  • Entanglement: Certifying bipartite entanglement across exponentially many partitions and fully inseparable entanglement (entanglement across all bipartitions) with logarithmic sample complexity $O(\log n)$.
  • Quantum Magic: Certifying non-stabilizerness using only single-copy local measurements, a first for mixed-state soundness.
  • State Fidelity: A random-basis enhanced variant is proposed to certify global state fidelity. The authors prove constant sample complexity and robustness for random graph states and provide strong numerical evidence for generic states.

Results

The paper presents rigorous proofs and numerical simulations supporting the following results:

• Theoretical Guarantees: Theorem 1 establishes that for any property with a localizable quantumness metric $LQP(\psi) = \Omega(1)$, the protocol achieves constant sample complexity, constant robustness, and soundness for mixed states.
• Complexity Certification: The protocol successfully certifies high circuit complexity (both unitary and measurement-assisted) for states generated by random brickwork circuits and deep-thermalized states.
• Entanglement Certification: For fully inseparable entanglement, the protocol reduces the sample complexity from linear to logarithmic in system size by reusing a single dataset across all nearest-neighbor pairs. Numerical studies on Hamiltonian ground states (XXZ and $J_1-J_2$ chains) confirm that localizable entanglement remains non-vanishing across critical regimes.
• Magic Certification: Numerical simulations on magic-injection circuits up to 512 qubits demonstrate that localizable magic concentrates effectively, allowing for efficient certification with constant sample complexity and high robustness against depolarizing noise.
• Fidelity Certification: For random graph states, the spectral gap of the conditional fidelity observable is proven to be constant ($\Omega(1)$), ensuring efficient certification. Numerical evidence suggests this scaling extends to generic states generated by polynomial-depth circuits.

Significance

The authors claim that this work establishes localizable quantumness as a unifying principle for understanding many-body quantum systems and provides a practical, scalable toolkit for certifying large-scale quantum processors.

• Scalability: By relying solely on local Pauli measurements and achieving constant sample complexity, the method overcomes the exponential scaling barrier of traditional tomography and many existing certification protocols.
• Experimental Feasibility: The non-adaptive nature of the measurements and the ability to certify mixed states make the protocol highly compatible with current and near-term quantum hardware, which often lacks long-lived quantum memory or adaptive feedback capabilities.
• New Perspective: The work reframes global certification as a local problem, offering a novel lens for probing complex phenomena such as measurement-induced phase transitions, topological order, and the concentration of quantum resources.
• Broad Applicability: The framework applies to a wide range of physically relevant states, including those generated by Hamiltonian dynamics and random circuits, bridging the gap between theoretical certification and experimental benchmarking.

The paper concludes by noting that while current complexity witnesses target relatively shallow circuits, the phenomenon of complexity concentration suggests potential for extending these methods to higher complexities. Future directions include developing a theory of localizable magic and extending the framework to certify properties of mixed states more broadly.