Semidefinite block-matrix relaxations for computing quantum correlations

1. Problem Statement

Bounding quantum correlations is a fundamental challenge in quantum information science, essential for tasks like entanglement detection, device certification, and benchmarking. While Semidefinite Programming (SDP) relaxations (specifically the Navascués-Pironio-Acín or NPA hierarchy) are the state-of-the-art for problems with simple algebraic structures (e.g., quantum nonlocality), they struggle when problems involve general structural constraints.

Existing methods often fail to efficiently incorporate constraints related to:

• Dimensionality: Fixed or bounded Hilbert space dimensions.
• Fidelity: Imperfections in state preparation or measurement alignment.
• Operator Norms: Calibration errors or "almost" anticommuting observables.
• Mixed Resources: Combinations of separability, partial transposition, and classical randomness.

The authors address the gap: How can SDP relaxations efficiently approximate quantum correlations in physics problems involving general structural constraints on quantum resources?

2. Methodology: Block-Moment Matrix (BMM) Relaxations

The authors propose a generalized SDP relaxation framework based on Block-Moment Matrices (BMM). This approach extends the NPA hierarchy by treating the moment matrix not as a matrix of scalars, but as a matrix of blocks (operators), allowing for the direct encoding of operator-level constraints.

Core Construction

1. Operator Set: Define a set of bounded operators $\mathcal{L} = \{O_1, \dots, O_n\}$ representing states, measurements, or transformations.
2. Monomial List: Construct a list $S$ of monomials (products) of these operators up to a certain order $K$.
3. The Map $\Theta$: Introduce a completely positive map $\Theta: \mathcal{B}(\mathcal{H}') \to \mathcal{B}(\mathcal{H})$.
   • For fixed-dimension problems, $\Theta$ is typically the identity map ($\Theta = \text{id}$).
   • For unbounded/infinite-dimensional problems, $\Theta$ acts as a compression map (e.g., tracing out parts of the Hilbert space or projecting onto a subspace) to ensure the resulting blocks are finite-dimensional.
4. The BMM ($\Gamma$): Construct a block matrix where the entry at block-row $u$ and block-column $v$ is $\Gamma_{u,v} = \Theta(u v^\dagger)$.
   • By construction, $\Gamma \succeq 0$ (positive semidefinite).
5. Constraint Integration:
   • Reduction Rules: Algebraic identities (e.g., $O^2=1$, commutativity) are enforced as linear equalities between blocks.
   • External Constraints: Constraints on the original problem (e.g., fidelity bounds, dimension limits) are mapped to the BMM via linear maps $\Omega$ such that $\Omega(\Gamma) \succeq 0$ or $\Omega(\Gamma) = 0$.
   • Localizing Matrices: For polynomial constraints (e.g., $g(L) \succeq 0$), localizing matrices are constructed to enforce positivity without adding new variables.

This methodology allows the formulation of complex quantum correlation problems as SDPs where the block size and linear constraints directly reflect the physical limitations of the system.

3. Key Contributions and Applications

The authors demonstrate the versatility of the BMM method by solving five distinct open problems in quantum information:

Problem 1: Entanglement Witnessing with Imperfect Measurements

• Challenge: Standard entanglement witnesses fail if measurement devices are misaligned. Existing corrections are limited to special cases.
• Solution: The BMM method incorporates fidelity constraints ($\text{tr}(A \tilde{A}) \geq 1-\epsilon$) directly into the SDP.
• Result: Provides tight, analytically derived upper bounds for entanglement witnesses under arbitrary measurement imperfections for qubits and qutrits, eliminating false positives.

Problem 2: Certification in Prepare-and-Measure Scenarios

• Challenge: Certifying measurement devices usually requires perfect state sources. Real sources have bounded fidelity.
• Solution: The method handles unbounded Hilbert spaces by using a map $\Theta$ that projects onto the trusted $d$-dimensional subspace while tracing out the rest. It incorporates fidelity bounds ($\langle \psi | \rho | \psi \rangle \geq 1-\omega$).
• Result: Successfully certifies quantum features in measurement devices even with imperfect sources, outperforming previous bounds for both classical and quantum measurement models.

Problem 3: Genuine Multipartite Entanglement (GME) Dimensionality

• Challenge: Determining the dimensionality of multipartite entanglement is computationally hard; standard fidelity criteria are often loose.
• Solution: The method constructs an SDP to bound the Schmidt number across all bipartitions. It uses projectors $\Pi$ of rank $r$ to enforce dimensionality constraints.
• Result: The BMM relaxation is strictly stronger than standard fidelity criteria for all target states. It detects GME dimensionality in high-dimensional systems (e.g., 4-qutrit Dicke states) where previous numerical methods were too expensive.

Problem 4: Operational Dimension of Quantum Preparation Devices

• Challenge: Determining the minimum dimension $r$ required to simulate a set of quantum states (operational dimension) without assuming a privileged basis.
• Solution: The SDP searches for a convex decomposition of the target states using subspaces of dimension $r$.
• Result: Provides rigorous upper bounds on the critical noise visibility required to reduce operational dimension. The method scales efficiently to dimensions ($d=15$) where brute-force methods fail.

Problem 5: Uncertainty Relations for Nearly Anticommuting Observables

• Challenge: Standard uncertainty relations assume perfect anticommutation. Real devices have calibration errors ($\{O_i, O_j\} \approx 0$).
• Solution: The method incorporates operator norm constraints on the anticommutator ($-\eta I \preceq \{O_i, O_j\} \preceq \eta I$) into the BMM.
• Result: Derives tight, linear scaling bounds for uncertainty relations in "almost" anticommuting scenarios (e.g., ring graphs of observables). These bounds are optimal and directly yield robust entanglement witnesses.

4. Results and Performance

• Accuracy: In all five cases, the method produces bounds that are either optimal (matching brute-force lower bounds) or significantly tighter than existing analytical criteria.
• Efficiency: The method remains computationally feasible for systems with dimensions and particle counts that are intractable for previous numerical approaches (e.g., 6 ququarts, 21 observables).
• Generality: The framework successfully handles a mix of constraints: separability, fidelity, dimensionality, and operator norms, which were previously difficult to combine in a single SDP.

5. Significance and Outlook

• Generalization of NPA: This work generalizes the seminal NPA hierarchy, transforming it from a tool primarily for nonlocality into a universal framework for quantum correlation problems with structural constraints.
• Experimental Relevance: By explicitly accounting for imperfections (fidelity, calibration errors, dimensionality limits), the method bridges the gap between theoretical bounds and experimental reality, making it a vital tool for device benchmarking and quantum certification.
• Future Applications: The authors suggest the methodology is applicable to quantum key distribution (QKD) security proofs, quantum random number generation, and falsifying alternative physical models (e.g., superposition-free models).

In summary, the paper introduces a powerful, flexible Block-Moment Matrix framework that enables the efficient computation of quantum correlation bounds in complex, constrained physical scenarios, offering significant improvements over existing analytical and numerical methods.