23
$\begingroup$

Quantum computers are very good for sampling distributions that we dont 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 dont 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 {f(x)>= f(y)} and repeat.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aram Harrow Dec 16 '10 at 21:42
  • $\begingroup$ 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. $\endgroup$ – Gil Kalai Dec 17 '10 at 11:31
  • $\begingroup$ Frieze is spelled with a z. The link to the paper is dx.doi.org/10.1145/102782.102783 $\endgroup$ – Guilherme D. da Fonseca Jan 10 '11 at 9:09
  • 3
    $\begingroup$ how about this paper (arxiv.org/abs/quant-ph/0606202). It seems that you can use this to sample. $\endgroup$ – Marcos Villagra Jan 28 '11 at 1:39
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to TCS overflow Greg, it feels you were always been here... $\endgroup$ – Gil Kalai May 17 '15 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.