Approximately sampling from convex polyhedrons with quantum computers

Question

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.

Answer 1

As the post acknowledges, the existence of a classical polynomial-time algorithm to estimate the volume of a convex polytope is a game-changer. A quantum algorithm is much less likely to be interesting unless it is competitive with classical algorithms. After all, without that criterion, any classical algorithm could simply be called a quantum algorithm instead.

That said, there is still room for a polynomial speed-up, and the main, known viewpoint for that type of speedup is a quantum walk, especially considering that the classical acceleration in this case is based on a good random walk. (Indeed, any quantum algorithm can be viewed as a quantum walk, but for some algorithms this is not necessarily enlightening.) Various papers in the QC literature have pointed out that the algorithms to estimate the volume of a convex polytope use random walks, and that there could be an acceleration from a quantum walk. So, it appears that researchers know this suggestion, but that no one has tried to work out what polynomial acceleration you might get for this problem. You might not get anything if the best classical algorithm has some sort of spoiler, such as a separate stage which is not a random walk with comparable running time.

Here is a collection of papers that all mention the basic idea in passing; again, Google Scholar seems to suggest that no one has gone further.

1. arXiv:quant-ph/0104137 - Quantum Walks on the Hypercube
2. arXiv:quant-ph/0205083 - Quantum random walks hit exponentially faster
3. arXiv:quant-ph/0301182 - Decoherence in Discrete quantum walks
4. arXiv:quant-ph/0304204 - Controlling discrete quantum walks: coins and intitial states
5. arXiv:quant-ph/0411065 - Quantum walk on a line with two entangled particles
6. arXiv:quant-ph/0504042 - Entanglement in coined quantum walks on regular graphs
7. arXiv:quant-ph/0609204 - Quantum speedup of classical mixing processes
8. arXiv:0804.4259 - Speed-up via quantum sampling
9. A random walk approach to quantum algorithms
10. Discrete quantum walk for solving nonlinear equations over finite fields

The other side of the classical algorithms to estimate the volume of a convex polytope is linear programming. I don't know there has been any progress finding a quantum acceleration for that. It seems difficult to avoid a stage of linear programming in order to put the convex polytope in a favorable position for sampling.