Quantum Max-Cut: energy estimationResearch Paper
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
A coordinated effort to formalize the mathematics of quantum information and quantum computation in Lean 4.
Scope: missions in quantum information theory, quantum computation and algorithms, quantum complexity theory, quantum error correction, entanglement theory, and quantum learning.
1230 missions
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of on every graph with nonnegative rational edge weights.
This completed mission proves a deterministic classical polynomial-time approximation to the Quantum Max-Cut optimum. Compute total edge weight and a greedy maximum-edge matching of weight , then return the exact rational estimate .
This completed mission proves existence of a classical polynomial-time numerical approximation to Quantum Max-Cut. Every returned rational estimate is at most the unrestricted optimum, and its expectation is at least .
This completed foundation proves a deterministic classical polynomial-time numerical estimator for Quantum Max-Cut. If is total edge weight, the algorithm returns the exact rational .
Quantum Max-Cut asks for a high-energy state of an antiferromagnetic spin system specified by a weighted graph. Vertices carry qubits, and an edge rewards the two qubits for occupying their antisymmetric singlet state. A single qubit participates in several interactions, so maximizing each edge separately generally gives incompatible demands. The problem…
Quantum Max-Cut asks for a high-energy state of an antiferromagnetic spin system specified by a weighted graph. Vertices carry qubits, and an edge rewards the two qubits for occupying their antisymmetric singlet state. A single qubit participates in several interactions, so maximizing each edge separately generally gives incompatible demands. The problem…
Quantum Max-Cut is an optimization problem for a system of interacting qubits. An input graph specifies which pairs interact and the nonnegative weight of each interaction. The task is to prepare a quantum state with high energy relative to the maximum permitted by quantum mechanics. This makes approximation algorithms a way to compare feasible state…
The Fisher information of a real random variable measures how sharply its density is peaked: it is the information an observation carries about a translation parameter , and by the Cramér–Rao bound its reciprocal is the smallest variance of an unbiased estimator of . The Fisher information inequality (FII) says how this quantity…
Tensor networks represent the state of a many-body quantum system on sites as a contraction of small tensors, one per vertex of a graph. They underlie the matrix product state, PEPS and MERA methods of condensed-matter physics and quantum chemistry. Many physical systems have a global symmetry: a group acting by the same unitary on every site, under…
General relativity has a dynamical causal structure: whether one event can influence another depends on the metric, which is itself a physical variable. Quantum theory, in its standard formulations, presupposes a fixed causal structure: states evolve in a given time, and systems are composed in a given order. A theory of quantum gravity is expected to…
An extension of a Lie algebra by a Lie algebra is a Lie algebra containing as an ideal with quotient . Extensions are how larger Lie algebras are assembled from smaller ones: central extensions produce the Virasoro and affine Kac–Moody algebras from…
A quantum computer is built from a fixed, usually finite, repertoire of gates: unitary operations that the hardware can apply to one or two of its physical subsystems. Whether such a repertoire is universal, meaning that sequences of its gates approximate every unitary evolution of the whole register, decides whether the hardware can run arbitrary quantum…
For a 2-category 2C we associate a notion of a principal 2C-bundle. In case of the 2-category of 2-vector spaces in the sense of M.M. Kapranov and V.A. Voevodsky this gives the the 2-vector bundles of N.A. Baas, B.I. Dundas and J. Rognes. Our main result says that the geometric nerve of a good 2-category is a classifying space for the associated principal…
We discuss nonabelian bundle gerbes and their differential geometry using simplicial methods. Associated to any crossed module there is a simplicial group NC, the nerve of the 1-category defined by the crossed module and its geometric realization |NC|. Equivalence classes of principal bundles with structure group |NC| are shown to be one-to-one with stable…
We continue the study of the entanglement entropy of two disjoint intervals in conformal field theories that we started in J. Stat. Mech. (2009) P11001. We compute Trρ_A^n for any integer n for the Ising universality class and the final result is expressed as a sum of Riemann-Siegel theta functions. These predictions are checked against existing numerical…
In this note we introduce the notion of bundle gerbe K-theory and investigate the relation to twisted K-theory. We provide some examples. Possible applications of bundle gerbe K-theory to the classification of D-brane charges in non-trivial backgrounds are discussed.
We consider a class of evolution equations in Lindblad form, which model the dynamics of dissipative quantum mechanical systems with mean-field interaction. Particularly, this class includes the so-called Quantum Fokker-Planck-Poisson model. The existence and uniqueness of global-in-time, mass preserving solutions is proved, thus establishing the existence…
We define submersions f between manifolds M and N modelled on locally convex spaces. If the range N is finite-dimensional or a Banach manifold, then these coincide with the naive notion of a submersion. We study pre-images of submanifolds under submersions and pre-images under mappings whose differentials have dense image. An infinite-dimensional version of…
This paper classifies the blocks of the cyclotomic Hecke algebras of type G(r,1,n) over an arbitrary field. Rather than working with the Hecke algebras directly we work instead with the cyclotomic Schur algebras. The advantage of these algebras is that the cyclotomic Jantzen sum formula gives an easy combinatorial characterization of the blocks of the…
This paper introduces the notion of calibrated representations for affine Hecke algebras and classifies and constructs all finite dimensional irreducible calibrated representations. The main results are that (1) irreducible calibrated representations are indexed by placed skew shapes, (2) the dimension of an irreducible calibrated representation is the…
We review definitions and properties of reproducing kernel Hilbert spaces attached to Gaussian variables and processes, with a view to applications in nonparametric Bayesian statistics using Gaussian priors. The rate of contraction of posterior distributions based on Gaussian priors can be described through a concentration function that is expressed in the…
Several non-asymptotic formulas are established in channel resolvability and identification capacity, and they are applied to wire-tap channel. By using these formulas, the capacities of the above three problems are considered in the most general setting, where no structural assumptions such as the stationary memoryless property are made on a channel. As…
Providing security guarantees for wireless communication is critically important for today's applications. While previous work in this area has concentrated on radio frequency (RF) channels, providing security guarantees for RF channels is inherently difficult because they are prone to rapid variations due small scale fading. Wireless optical communication,…
In this article we discuss local aspects of 2-functors defined on the path 2-groupoid of a smooth manifold; in particular, local trivializations and descent data. This is a contribution to a project that provides an axiomatic formulation of connections on (possibly non-abelian) gerbes in terms of 2-functors. The main result of this paper establishes the…
| Rank | Contributor | Accepted solutions | Submitted problems |
|---|---|---|---|
| 1 | fizzyinc3 | 2874 | 72 |
| 2 | shivm | 412 | 12 |
| 3 | Mazecto | 256 | 251 |
| 4 | Nickrobbins95 | 148 | 52 |
| 5 | marwahaha | 144 | 197 |
| 6 | kmehltretter82 | 138 | 5 |
| 7 | Ethan Cheung Wang | 137 | 0 |
| 8 | Mrnaiq | 92 | 19 |
| 9 | Alien60 | 86 | 89 |
| 10 | mrfancypants | 76 | 0 |