En klasse [[Kvantealgoritmer]], relevant både for [[Shors algoritme]] og for [[Kvantesimulering]]/[[Kvantekjemi]]. Fra [[Kvantekjemi]]-tutorial ved [[QIP'24]]: ![[IMG_5432.jpeg]] > The fault-tolerant algorithms, they have this general structure, you prepare the state, you measure the phase (...) there are many types of fault-tolerant algorithms, not just phase estimation, but they always have this type of complexity where you have the polynomial in inverse presision, polynomial in system size, and polynomial in some quantity that looks like the inverse of the fidelity in the beginning[^1]. Just like (for classical heuristics, the former two) should be thought of as the problem of *refinement*, while the (latter) should be thought of as the problem of *preparing the state*. And similar to the classical case, state preparation is where the complexity is hidden. Så man må sammenligne kostnaden av klassiske algoritmer og kvantealgoritmer ved to punkter: Kostnaden å forberede tilstandene, ("in quantum case, as measured by overlap"), og kostnaden å forbedre feilraten ("in quantum case, by phase estimation"). > We find that when we look at problems where it's hard to find good classical states, and while you need to search over many different classical starting points to find a good state for your classical heuristics, it's *also* very hard to find a good starting point for your quantum algorithm[^2]. So if you do adiabatic state preparation, for example, if you start from different points, you have very different state preparation times in these types of hard problems. We have many orders of magnitude different state preparation times depending on your starting point. So, the fact that the classical state preparation problem has this sort of *search problem* associated with it, really disappears in the quantum algorithm, where this adiabatic state preparation time looks like the time you get when you apply the adiabatic algorithm to unstructured search, right, so like [[Grovers algoritme|Grover search]]. So there isn't an obvious advantage, an exponential advantage for example, for the quantum algorithm in preparing the state, although there *could* be some kind of polynomial advantage, the knid that you typically see in this kind of search problems. For energy refinement-delen er dataene litt mer optimistisk, dog fortsatt bare for polynome speedups: ![[IMG_5434.jpeg]] > There is some empirical evidence of polynomial advantage in energy refinement, but not for exponential advantage. :( [^1]: Så, nøyaktigheten av ansatsen du starter med elns.? [^2]: Som adiabatisk utvikler en start-hamilton $H_0$ som er lett å forberede, til målet ditt $H$.