# Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $$f$$ is a Boolean function (from $$\{-1,1\}^n$$ to $$\{-1,1\}$$) that can be computed in polynomial time then with quantum computers we can efficiently sample according to the distribution described by the Fourier expansion of $$f$$. (We do not know how to do it with classical computers.)

Can we use quantum computers to sample or approximately sample a random point in a polyhedron described by a system of $$n$$ inequalities in $$d$$ variables?

Moving from the inequalities to the points looks to me somewhat similar to a "transform". Moreover, I would be happy to see a quantum algorithm even if you modify the distribution, e.g. consider product of Gaussian distribution described by the hyperplanes of the polyhedron or some other things.

A few remarks: Dyer, Frieze and Kannan found a famous classical polynomial time algorithm to approximately sample and approximately compute the volume of a polyhedron. The algorithm is based on random walks and rapid mixing. So we want to find a different quantum algorithm for the same purpose. (OK, we can hope that a quantum algorithm may lead also to things in this context we do not know to do classically. But to start, all we want is a different algorithm, this must be possible.)

Second, we don't even insist on approximately sampling the uniform distribution. We will be happy to approximately sample some other nice distribution which is roughly supported on our polyhedron. There is an argument by Santosh Vampala (and also by me in another context) leading from sampling to optimization: if you want to optimize $$f(x)$$ sample to find a point $$y$$ where $$f(x)$$ is typical. Add the constraint $$\lbrace f(x) \ge f(y)\rbrace$$ and repeat.

• So you want a quantum algorithm that achieves the same thing as the existing classical algorithm, but using a nontrivially different approach? Or do you want the quantum algorithm to achieve something different? If you want to produce a superposition over lattice points in the polyhedron, then I think this can be achieved by arXiv:quant-ph/0301023. Dec 16, 2010 at 21:42
• Yes, essentially the most obvious goal is to give a different quantum algorithm that achieves the same thing (or even weaker, e.g. changing the distribution) than the existing classical algorithm. Dec 17, 2010 at 11:31
• Frieze is spelled with a z. The link to the paper is dx.doi.org/10.1145/102782.102783 Jan 10, 2011 at 9:09
• how about this paper (arxiv.org/abs/quant-ph/0606202). It seems that you can use this to sample. Jan 28, 2011 at 1:39