5
$\begingroup$

According to J. Gough, one of the bottlenecks in the current development of large-scale quantum computing may be the lack of our ability to simulate large scale quantum system, which is a NP-hard problem and also requires exponential memory with classical hardware if I understand correctly.

I'm currently developing a certain powerful discrete approximate algorithm. In principle, it can, for example, find an approximate solution for a given quantum Ising model efficiently or optimize the configuration of quantum gates to minimize the error a la U. Las Heras et. al. by replacing its GA with mine.

1) Can we reduce digital/analog quantum simulation to a NP-hard discrete optimization problem (like solving Ising model), so that it can be approximately solved by a classical algorithm using classical device?

2) What are some other crucial bottlenecks? Do they need discrete optimization?

Edit: I guess one of other bottlenecks is quantum error correction, which was already mentioned above.

$\endgroup$
  • $\begingroup$ I'm not sure I understand the question. Yes, it is believed that simulating quantum systems, in the general case, is not efficiently (i.e. polynomially) doable with any classical device. This doesn't mean that better simulation algorithms/methods are not useful, nor that it is not possible to solve specific kinds of simulation problems efficiently $\endgroup$ – glS Jul 25 '18 at 11:00
  • $\begingroup$ I'm not sure whether I could express my statement clearly, so let me ask a slightly different question instead of my Q1. Can we reduce digital/analog quantum simulation to a NP-hard discrete optimization problem (like solving Ising model), so that it can be approximately solved by a classical algorithm using classical device? $\endgroup$ – Math.StackExchange Jul 25 '18 at 12:07

Your Answer

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

Browse other questions tagged or ask your own question.