Quantum states supported by matroids
arXiv:2607.15548 · doi:10.1103/mx1w-k8fg
Abstract
In this work, we establish a structural correspondence between quantum states and matroid theory. This connection demonstrates that key properties of quantum states, including entanglement and measurement, can be characterized in purely combinatorial terms via matroids, despite the apparent conceptual distance between these two fields. Using this framework, we show that a matroid-supported state is genuinely entangled when its underlying matroid is connected. Moreover, a uniform superposition over all bases of a matroid is genuinely entangled if and only if the matroid is connected. We also demonstrate that a local measurement in the -basis on such a state yields another matroid-supported state, whose underlying matroid is a minor of the original one. Inspired by matroid duality, we further propose a notion of quantum state duality, uncovering a deep structural symmetry in state transformations.
This paper has been published in Physical Review A. Commements are welcome
References in corpus (26)
- Quantum entanglement
- Measurement-based quantum computation with cluster states
- Multi-party entanglement in graph states
- Quantum walks: a comprehensive review
- Quantum Metrology in Non-Markovian Environments
- Using entanglement against noise in quantum metrology
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Quantum Hypergraph States
- Instantaneous Quantum Computation
- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
- Homogeneous multivariate polynomials with the half-plane property
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- Matroids and Quantum Secret Sharing Schemes
- Entanglement quantification by local unitaries
- Entanglement accelerates quantum simulation
- Self-testing maximally-dimensional genuinely entangled subspaces within the stabilizer formalism
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Deterministic Bethe state preparation
- On Local Equivalence, Surface Code States and Matroids
- Simulating Quantum Computations with Tutte Polynomials
- Quantum encoder for fixed Hamming-weight subspaces
- Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
- Derandomization of quantum algorithm for triangle finding
- All genuinely entangled stabilizer subspaces are multipartite fully nonlocal
- Unbounded quantum-classical separation in sample complexity for sphere center finding