<p>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.</p>

<p>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.</p>

<p>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.</p>

<ol>
<li><a href="http://arxiv.org/abs/quant-ph/0104137">arXiv:quant-ph/0104137 - Quantum Walks on the Hypercube</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0205083">arXiv:quant-ph/0205083 - Quantum random walks hit exponentially faster</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0301182">arXiv:quant-ph/0301182 - Decoherence in Discrete quantum walks</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0304204">arXiv:quant-ph/0304204 - Controlling discrete quantum walks: coins and intitial states</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0411065">arXiv:quant-ph/0411065 - Quantum walk on a line with two entangled particles</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0504042">arXiv:quant-ph/0504042 - Entanglement in coined quantum walks on regular graphs</a></li>
<li><a href="http://arxiv.org/abs/quant-ph/0609204">arXiv:quant-ph/0609204 - Quantum speedup of classical mixing processes</a></li>
<li><a href="http://arxiv.org/abs/0804.4259">arXiv:0804.4259 - Speed-up via quantum sampling</a></li>
<li><a href="http://classic.rsta.royalsocietypublishing.org/content/364/1849/3407.full">A random walk approach to quantum algorithms</a></li>
<li><a href="http://asu.edu.jo/TestWeb/userfiles/file/natural_pdf/Volume-10-2008/Number-1/Discrete%20Quantum%20Walk%20for%20Solving%20NonlinearDiscrete%20Quantum%20Walk%20for%20Solving%20Nonlinear.pdf">Discrete quantum walk for solving nonlinear equations over finite fields</a></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2015-05-17T20:21:29.670Z
Welcome to TCS overflow Greg, it feels you were always been here...
Gil Kalai
CC BY-SA 4.0
2020-04-27T06:20:42.607Z
Here's a 2019 paper that puts the money where the mouth is: https://arxiv.org/abs/1908.03903
smapers
CC BY-SA 3.0
2015-05-17T19:05:30.720Z
2015-05-17T19:05:30.720Z
Greg Kuperberg
<p>Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if <span class="math-container">$f$</span> is a Boolean function (from <span class="math-container">$\{-1,1\}^n$</span> to <span class="math-container">$\{-1,1\}$</span>) 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 <span class="math-container">$f$</span>. (We do not know how to do it with classical computers.) </p>

<blockquote>
  <p>Can we use quantum computers to sample or approximately sample a random point  in a polyhedron described by a system of <span class="math-container">$n$</span> inequalities in <span class="math-container">$d$</span> variables?</p>
</blockquote>

<p>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.</p>

<p>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.)</p>

<p>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 <span class="math-container">$f(x)$</span> sample to find a point <span class="math-container">$y$</span> where <span class="math-container">$f(x)$</span> is typical. Add the constraint <span class="math-container">$\lbrace f(x) \ge f(y)\rbrace$</span> and repeat.   </p>

CC BY-SA 2.5
2010-12-16T21:42:12.280Z
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.
Aram Harrow
CC BY-SA 2.5
2010-12-17T11:31:40.063Z
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.
Gil Kalai
CC BY-SA 2.5
2011-01-10T09:09:15.690Z
Frieze is spelled with a z. The link to the paper is http://dx.doi.org/10.1145/102782.102783
Guilherme D. da Fonseca
CC BY-SA 2.5
2011-01-28T01:39:35.507Z
how about this paper (http://arxiv.org/abs/quant-ph/0606202). It seems that you can use this to sample.
Marcos Villagra
<quantum-computing><cg.comp-geom><optimization>
Approximately sampling from convex polyhedrons with quantum computers
Gil Kalai
# Approximately sampling from convex polyhedrons with quantum computers

(Asked by: username_0 on 2010-12-14)

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.

**Tags:** quantum-computing, cg.comp-geom, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: Frieze is spelled with a z. The link to the paper is http://dx.doi.org/10.1145/102782.102783  
> **username_3**: how about this paper (http://arxiv.org/abs/quant-ph/0606202). It seems that you can use this to sample.  

---

## 1 answers

### Answer by username_4 on 2015-05-17. Score: 5

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](http://arxiv.org/abs/quant-ph/0104137)
2. [arXiv:quant-ph/0205083 - Quantum random walks hit exponentially faster](http://arxiv.org/abs/quant-ph/0205083)
3. [arXiv:quant-ph/0301182 - Decoherence in Discrete quantum walks](http://arxiv.org/abs/quant-ph/0301182)
4. [arXiv:quant-ph/0304204 - Controlling discrete quantum walks: coins and intitial states](http://arxiv.org/abs/quant-ph/0304204)
5. [arXiv:quant-ph/0411065 - Quantum walk on a line with two entangled particles](http://arxiv.org/abs/quant-ph/0411065)
6. [arXiv:quant-ph/0504042 - Entanglement in coined quantum walks on regular graphs](http://arxiv.org/abs/quant-ph/0504042)
7. [arXiv:quant-ph/0609204 - Quantum speedup of classical mixing processes](http://arxiv.org/abs/quant-ph/0609204)
8. [arXiv:0804.4259 - Speed-up via quantum sampling](http://arxiv.org/abs/0804.4259)
9. [A random walk approach to quantum algorithms](http://classic.rsta.royalsocietypublishing.org/content/364/1849/3407.full)
10. [Discrete quantum walk for solving nonlinear equations over finite fields](http://asu.edu.jo/TestWeb/userfiles/file/natural_pdf/Volume-10-2008/Number-1/Discrete%20Quantum%20Walk%20for%20Solving%20NonlinearDiscrete%20Quantum%20Walk%20for%20Solving%20Nonlinear.pdf)

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.

> **Comments:**
> **username_0**: Welcome to TCS overflow Greg, it feels you were always been here...  
> **username_5**: Here's a 2019 paper that puts the money where the mouth is: https://arxiv.org/abs/1908.03903  

---

