Linear programming with unitary-equivariant constraints

Abstract

Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics. Optimization problems with such symmetry can often be formulated as semidefinite programs for a $d^{p+q}$-dimensional matrix variable that commutes with $U^{\otimes p}\otimes {\bar{U}}^{\otimes q}$, for all $U\in \mathrm{U}(d)$. Solving such problems naively can be prohibitively expensive even if $p+q$ is small but the local dimension $d$ is large. We show that, under additional symmetry assumptions, this problem reduces to a linear program that can be solved in time that does not scale in $d$, and we provide a general framework to execute this reduction under different types of symmetries. The key ingredient of our method is a compact parametrization of the solution space by linear combinations of walled Brauer algebra diagrams. This parametrization requires the idempotents of a Gelfand-Tsetlin basis, which we obtain by adapting a general method arXiv:1606.08900 inspired by the Okounkov-Vershik approach. To illustrate potential applications, we use several examples from quantum information: deciding the principal eigenvalue of a quantum state, quantum majority vote, asymmetric cloning and transformation of a black-box unitary. We also outline a possible route for extending our method to general unitary-equivariant semidefinite programs.

arXiv comment68 pages; new application: transformation (transposition) of a black-box unitary

References in corpus (71)

• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Quantum cloning
• Restrictions on Transversal Encoded Quantum Gate Sets
• Quantum Circuits Architecture
• Programmable quantum gate arrays
• Fundamentals of Quantum Information Theory
• The entanglement cost under operations preserving the positivity of partial transpose
• Exploiting symmetry in variational quantum machine learning
• Asymmetric quantum cloning machines in any dimension
• Sample-optimal tomography of quantum states
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Estimating the spectrum of a density operator
• Group-Invariant Quantum Machine Learning
• Asymptotic teleportation scheme as a universal programmable quantum processor
• Branes, Anti-Branes and Brauer Algebras in Gauge-Gravity duality
• Separability properties of tripartite states with UxUxU-symmetry
• Quantum Cloning Machines and the Applications
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Informing Geometric Deep Learning with Electronic Interactions to Accelerate Quantum Chemistry
• Continuous symmetries and approximate quantum error correction
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• On the power of PPT-preserving and non-signalling codes
• Restrictions on realizable unitary operations imposed by symmetry and locality
• Cost of quantum entanglement simplified
• Asymptotics of random density matrices
• The Weingarten Calculus
• Probabilistic exact universal quantum circuits for transforming unitary operations
• Port-based teleportation in arbitrary dimension
• Error Correction of Quantum Reference Frame Information
• Optimal Port-based Teleportation
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Measuring Quantum Entropy
• Invariant semidefinite programs
• Near-optimal covariant quantum error-correcting codes from random unitaries with symmetries
• Structure of irreducibly covariant quantum channels for finite groups
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality
• Compatible quantum correlations: on extension problems for Werner and isotropic states
• Quantum state estimation and large deviations
• Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly
• Asymptotic performance of port-based teleportation
• Efficient multi port-based teleportation schemes
• Simplified formalism of the algebra of partially transposed permutation operators with applications
• Dimension-free entanglement detection in multipartite Werner states
• A generalization of Schur-Weyl duality with applications in quantum estimation
• Structure and properties of the algebra of partially transposed permutation operators
• Multiport based teleportation -- transmission of a large amount of quantum information
• Programmability of covariant quantum channels
• Positive maps and trace polynomials from the symmetric group
• A Practical Quantum Algorithm for the Schur Transform
• Optimality of the pretty good measurement for port-based teleportation
• Optimal Multi-port-based Teleportation Schemes
• On a family of a linear maps from $M_n(\mathbb{C})$ to $M_{n^2}(\mathbb{C})$
• RepLAB: a computational/numerical approach to representation theory
• Characterization of equivariant maps and application to entanglement detection
• How to check universality of quantum gates?
• Supersymmetric polynomials and the center of the walled Brauer algebra
• An Improved Approximation Algorithm for Quantum Max-Cut
• Quantifying the performance of approximate teleportation and quantum error correction via symmetric two-PPT-extendibility
• Optimal universal quantum circuits for unitary complex conjugation
• Continuum Limit of gl(M/N) Spin Chains
• Universal construction of decoders from encoding black boxes
• Canonical idempotents of multiplicity-free families of algebras
• Beyond product state approximations for a quantum analogue of Max Cut
• Calculable lower bounds on the efficiency of universal sets of quantum gates
• Fusion procedure for the walled Brauer algebra
• Application of the Level-$2$ Quantum Lasserre Hierarchy in Quantum Approximation Algorithms
• Infinite-Dimensional Programmable Quantum Processors
• A geometrical description of the universal $1\to 2$ asymmetric quantum cloning region
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates
• Five Starter Pieces: Quantum Information Science via Semi-definite Programs

Cited by in corpus (3)

• Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
• Universal adjointation of isometry operations using conversion of quantum supermaps
• Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations