3 ms·
We do not have efficient general quantum algorithms for quantum simulations. A quantum simulation can be decomposed in 3 steps: 1. a simulation needs to start
by joak 3y ago
We do not have efficient general quantum algorithms for quantum simulations.
A quantum simulation can be decomposed in 3 steps:
1. a simulation needs to start in a given quantum state
2. from there it's possible to quantumly evolve the system (simulate) exponentially faster than classically
3. then the resulting quantum state is read
The problem is that setting and reading a quantum state takes O(2^N) quantum operations where N is the number of quantum bits.
So all in all, taking in account the 3 steps, complexity of the quantum algorithm is O(2^N), no better than the classical algorithm.
Sure, for some specific quantum states setting/reading can have polynomial complexity. But these states are usually trivial (ie non quantum).
So quantum simulation might be possible in some cases, we don't know which cases and we don't if these case could be useful.
In short: so far we do not have (faster than classical) quantum algorithms for quantum simulations.
- joak 3y agoI might add that efficient quantum simulations would be immensely useful. So it's worth pursuing research in this area. Results are however not guaranteed.