A new way of orthogonalizing ensembles of vectors by "lifting" them to higher dimensions is introduced. This method can potentially be utilized for solving quantum decision and computing problems.

arXiv:1606.03873EntropyApr 14, 20187 citations

Symposium on Discrete Algorithms

Solving mixed 0-1programs by a lift-and-project method

Egon Balas, Sabastián Ceria, Gérard Cornuéjols

Published Jan 1, 1993• 16 citations

Publisher

DOI: 10.5555/313559.313757

Related papers

Experiments in quadratic 0–1 programming

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Mathematical ProgrammingMay 1, 1989196 citations

For every quantum walk there is a (classical) lifted Markov chain with faster mixing time

Danial Dervovic

Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with $n^2 D(G)$ vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph $G$ with $n$ vertices, where $D(G)$ is the diameter of $G$ . Moreover, the mixing time of this chain is $D(G)$ timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in $n$ . As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with $n^2 D(G)$ vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph $G$ with $n$ vertices, where $D(G)$ is the diameter of $G$. Moreover, the mixing time of this chain is $D(G)$ timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in $n$. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).

arXiv:1712.02318Dec 6, 20171 citation

A DNA Computation Model to Solve 0-1 Programming Problem

Xiaoli Qiang, Bo Zeng, Zicheng Wang +1 more

Chinese Journal of ComputersOct 16, 20091 citation

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Adam Kurpisz, Lucas Slot, Mikhail S. Zaytsev

We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of $\sum_{i=1}^n x_i$ for 0/1 variables under the constraint $\sum_{i=1}^n x_i \geq q$ , with $q \in \mathbb{R}$ . Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank $n$ to solve them, already when $q=1/2$ is constant. The SOS hierarchy requires only \emph{sublinear} rank $O(\sqrt{n})$ to solve unweighted MK when $q=1/2$ . On the other hand, when $q$ is allowed to vary with~ $n$ , the SOS rank of the problem may become linear. Interestingly, this is known to happen both when $q$ is large, and when $q$ is very small ($0We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of $\sum_{i=1}^n x_i$ for 0/1 variables under the constraint $\sum_{i=1}^n x_i \geq q$, with $q \in \mathbb{R}$. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank $n$ to solve them, already when $q=1/2$ is constant. The SOS hierarchy requires only \emph{sublinear} rank $O(\sqrt{n})$ to solve unweighted MK when $q=1/2$. On the other hand, when $q$ is allowed to vary with~$n$, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when $q$ is large, and when $q$ is very small ($0

arXiv:2605.00594May 1, 20260 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physicsJan 1, 20110 citations

Dimensional Lifting through the Generalized Gram–Schmidt Process

Hans Havlicek, Karl Svozil

A new way of orthogonalizing ensembles of vectors by "lifting" them to higher dimensions is introduced. This method can potentially be utilized for solving quantum decision and computing problems.

arXiv:1606.03873EntropyApr 14, 20187 citations

n^2 D(G)

vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph

G

with

n

vertices, where

D(G)

is the diameter of

G

. Moreover, the mixing time of this chain is

D(G)

timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in

n

. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).

We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of

\sum_{i=1}^n x_i

for 0/1 variables under the constraint

\sum_{i=1}^n x_i \geq q

, with

q \in \mathbb{R}

. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank

n

to solve them, already when

q=1/2

is constant. The SOS hierarchy requires only \emph{sublinear} rank

O(\sqrt{n})

to solve unweighted MK when

q=1/2

. On the other hand, when

q

is allowed to vary with~

n

, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when

q

is large, and when

q

is very small ($0