In this paper, we introduce a class of highly entangled real quantum states that cannot be approximated by circuits with log -many non-Clifford gates and prove that Bell sampling enables efficient cross-device verification (or distributed inner product estimation) for these states. That is, two remote parties can estimate the inner product tr ( ρ σ ) , each having black-box access to copies of a state ρ (or respectively σ ) in this class. This is significant because it is clear that this task can be achieved in those cases (such as low entanglement or low non-Clifford gate count) where one can independently learn efficient classical descriptions of each state using established techniques and share the description to compute the overlap. Instead, our results demonstrate that this is possible even in more complex scenarios where these “learn and share” methods are insufficient. Our proposal is scalable, as it just requires a number of two-copy Bell measurements and single-copy Pauli measurements that grows polynomially with both the number of qubits and the desired inverse error, and can be implemented in the near term. Moreover, the required number of samples can be efficiently experimentally determined by the parties in advance, and our findings are robust against preparation errors. We anticipate that these results could have applications in quantum cryptography and verification.
In this paper, we introduce a class of highly entangled real quantum states that cannot be approximated by circuits with log -many non-Clifford gates and prove that Bell sampling enables efficient cross-device verification (or distributed inner product estimation) for these states. That is, two remote parties can estimate the inner product tr ( ρ σ ) , each having black-box access to copies of a state ρ (or respectively σ ) in this class. This is significant because it is clear that this task can be achieved in those cases (such as low entanglement or low non-Clifford gate count) where one can independently learn efficient classical descriptions of each state using established techniques and share the description to compute the overlap. Instead, our results demonstrate that this is possible even in more complex scenarios where these “learn and share” methods are insufficient. Our proposal is scalable, as it just requires a number of two-copy Bell measurements and single-copy Pauli measurements that grows polynomially with both the number of qubits and the desired inverse error, and can be implemented in the near term. Moreover, the required number of samples can be efficiently experimentally determined by the parties in advance, and our findings are robust against preparation errors. We anticipate that these results could have applications in quantum cryptography and verification.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn n-qubit states prepared by random T-doped Clifford circuits with T-gate density below one via O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn T-depth-one circuits using O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have k copies of unknown states ρ,σ (acting on ℂd) respectively. Their goal is to estimate Tr(ρσ) up to additive error ε∈(0,1), using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that k=O(max{1/ε2,√d/ε}) copies suffice. This achieves a savings compared to full tomography which takes Ω(d3) copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least Ω(max{1/ε2,√d/ε}), even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements.
A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this Letter, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone toward fault tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a "circuit shadow": from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give several new and efficient protocols: an estimator of state fidelity, an error-mitigated estimator of Pauli expectation values, a test for the depth of a circuit, and an algorithm to estimate a lower bound on the number of T gates in the circuit. With some additional measurements, the latter algorithm can be used to learn a full description of states prepared by circuits with low T count.
Distributed inner product estimation (DIPE) is a fundamental task in quantum information, aiming to estimate the inner product between two unknown quantum states prepared on distributed quantum platforms. Existing rigorous sample complexity analyses are limited to unitary 4-designs, which pose significant practical challenges for near-term quantum devices. This work addresses this challenge by exploring DIPE with structured random circuits. We first establish that DIPE with an arbitrary unitary 2-design ensemble achieves an average sample complexity of O(2n) , where n is the number of qubits. We then analyze ensembles below unitary 2-designs—specifically, the brickwork and local unitary 2-design ensembles—demonstrating average sample complexities of O(2.18n) and O(2.5n) , respectively. Furthermore, we analyze the state-dependent sample complexity. For brickwork ensembles, we develop a tensor network approach to compute the asymptotic state-dependent sample complexity, showing that it converges to O(2.18n) as the circuit depth increases. Remarkably, we find that DIPE with the global Clifford ensemble requires Θ(2n) copies, matching the performance of unitary 4-designs. For both local and global Clifford ensembles, we find that the efficiency can be further enhanced by the nonstabilizerness of states. Additionally, for approximate unitary 4-designs, the performance exponentially approaches that of exact unitary 4-designs as the circuit depth increases. Our results provide theoretically guaranteed methods for implementing DIPE with experimentally feasible unitary ensembles.
Full tomography of a generic many-qubit quantum state requires exponentially many copies, while suitable structural constraints can make reconstruction sample-efficient. Existing approaches exploit, for example, limited entanglement structure, low magic, or constrained state-preparation circuits. Here we consider a class of mixed states that can simultaneously exhibit extensive entanglement and extensive magic. Specifically, we introduce Clifford-encoded block-product (CEBP) states, obtained by applying an unknown global Clifford unitary to a tensor product of arbitrary mixed states supported on unknown blocks of bounded size. We show that, for a fixed block size, CEBP states can be reconstructed using polynomially many copies by exploiting Clifford-preserved Pauli correlations to recover the latent structure and reduce the remaining problem to local tomography. Our result demonstrates that sample-efficient tomography can arise from bounded complexity in a latent frame even when the physical state is highly entangled, highly magical, and mixed, and suggests complexity modulo structured transformations as a broader organizing principle for quantum-state learnability.
We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and O ( log n ) non-Clifford gates. Specifically, for an n -qubit state | ψ ⟩ prepared with at most t non-Clifford gates, our algorithms use p o l y ( n , 2 t , 1 / ε ) time and copies of | ψ ⟩ to learn | ψ ⟩ to trace distance at most ε .The first algorithm for this task is more efficient, but requires entangled measurements across two copies of | ψ ⟩ . The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension k if it is stabilized by an abelian group of 2 k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.