Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0711.0086

Convex and linear models of NP-problems

Gubin, Sergey

Published Nov 1, 2007• 0 citations
arXivHTMLPDF

Abstract

Reducing the NP-problems to the convex/linear analysis on the Birkhoff polytope.
DOI
10.48550/arxiv.0711.0086

Related papers

Birkhoff’s Polytope and Unistochastic Matrices, N = 3 and N = 4

Ingemar Bengtsson, Åsa Ericsson, Marek Kuś +2 more

arXiv:math/0402325•Communications in Mathematical Physics•Jul 15, 2005•70 citations

A simple polynomial-time algorithm for convex quadratic programming

Paul Tseng, Decision Systems.

•Jan 1, 1988•7 citations

Polytope compatibility—From quantum measurements to magic squares

Andreas Blühm, Ion Nechita, Simon Schmidt

Several central problems in quantum information theory (such as measurement compatibility and quantum steering) can be rephrased as membership in the minimal matrix convex set corresponding to special polytopes (such as the hypercube or its dual). In this article, we generalize this idea and introduce the notion of polytope compatibility, by considering arbitrary polytopes. We find that semiclassical magic squares correspond to Birkhoff polytope compatibility. In general, we prove that polytope compatibility is in one-to-one correspondence with measurement compatibility, when the measurements have some elements in common and the post-processing of the joint measurement is restricted. Finally, we consider how much tuples of operators with appropriate joint numerical range have to be scaled in the worst case in order to become polytope compatible and give both analytical sufficient conditions and numerical ones based on linear programming.

arXiv:2304.10920•Journal of Mathematical Physics•Dec 1, 2023•1 citation

Quadratic Convex Reformulations for Integer and Mixed-Integer Quadratic Programs

Baiyi Wu, Rujun Jiang

International series in management science/operations research/International series in operations research & management science•Jan 1, 2017•0 citations

Quantum Walk on the Generalized Birkhoff Polytope Graph

Rafael Cação, Lucas R. C. T. Cortez, Ismael de Farias +3 more

We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where ϵ is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).

Entropy•Sep 23, 2021•1 citation

Bilinear programming methods for nonconvex quadratic problems

Springer eBooks•Oct 5, 2005•1 citation
Several central problems in quantum information theory (such as measurement compatibility and quantum steering) can be rephrased as membership in the minimal matrix convex set corresponding to special polytopes (such as the hypercube or its dual). In this article, we generalize this idea and introduce the notion of polytope compatibility, by considering arbitrary polytopes. We find that semiclassical magic squares correspond to Birkhoff polytope compatibility. In general, we prove that polytope compatibility is in one-to-one correspondence with measurement compatibility, when the measurements have some elements in common and the post-processing of the joint measurement is restricted. Finally, we consider how much tuples of operators with appropriate joint numerical range have to be scaled in the worst case in order to become polytope compatible and give both analytical sufficient conditions and numerical ones based on linear programming.
We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where ϵ is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).