We present and analyze an architecture for a logical qubit memory that is tolerant of faults in the processing of silicon double quantum dot (DQD) qubits. A highlight of our analysis is an in-depth consideration of the constraints faced when integrating DQDs with classical control electronics.

For a graph ( V , E ), existing compact linear formulations for the minimum cut problem require Θ(| V || E |) variables and constraints and can be interpreted as a composition of | V | − 1 polyhedra for minimum s - t cuts in much the same way as early approaches to finding globally minimum cuts relied on | V | − 1 calls to a minimum s - t cut algorithm. We present the first formulation to beat this bound, one that uses O (| V | 2 ) variables and O (| V | 3 ) constraints. An immediate consequence of our result is a compact linear relaxation with O (| V | 2 ) constraints and O (| V | 3 ) variables for enforcing global connectivity constraints. This relaxation is as strong as standard cut-based relaxations and has applications in solving traveling salesman problems by integer programming as well as finding approximate solutions for survivable network design problems using Jain's iterative rounding method. Another application is a polynomial-time verifiable certificate of size n for for the NP-complete problem of l 1 -embeddability of a rational metric on an n -set (as opposed to a certificate of size n 2 known previously).

Structure comparison is a fundamental problem for structural genomics. A variety of structure comparison methods were proposed and several protein structure classification servers e.g., SCOP, DALI, CATH, were designed based on them, and are extensively used in practice. This area of research continues to be very active, being energized bi-annually by the CASP folding competitions, but despite the extraordinary international research effort devoted to it, progress is slow. A fundamental dimension of this bottleneck is the absence of rigorous algorithmic methods. A recent excellent survey on structure comparison by Taylor et.al. [23] records the state of the art of the area: In structure comparison, we do not even have an algorithm that guarantees an optimal answer for pairs of structures …

Let P be a linear relaxation of an integer polytope Z such that the integrality gap of P with respect to Z is at most r, as verified by a poly-time heuristic A, which on any positive cost function e returns an integer solution (extreme point of Z) whose cost is at most r times the optimal cost over P. Then for any point z" in P (fractional solution), rx" dominates some convex combination of extreme points of Z.A constructive version of this theorem is presented with applications to approximation algorithm% and can be viewed as a generalization of randomized rounding.