5
$\begingroup$

The past couple of years has seen various groups claim quantum advantage/utility only to have their experiments efficiently simulated with classical methods, notably using tensor networks.

My question is then, is it, in principle possible to know/measure the classical difficulty of simulating a state $|\Psi \rangle$ prepared within a quantum computer without incurring exponential costs?

Some connections to classical difficulty can be made as bounds on the required number of $T$ gates is determined if one measures the stabilizer 2-Renyi entropy $M_2$ (see equation 12 in this paper). You could then quantify the cost of a Clifford + T simulation of the circuit, but, measuring the $M_2$ faithfully requires an exponential amount of measurements.

Another paper introduces the Bell Magic $B$, formally related to $M_2$, but may be measured with low cost. Unfortunately, the same bounds on the number of $T$ gates (or other connections to the difficulty of classical simulation) do not seem to exist (or at least, nobody has determined them).

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Note that magic is just one quantum resource and by itself not enough to render simulations hard. For instance, non-entangling circuits can prepare highly magical states, but are trivial to simulate. You necessarily need a combination of entanglement + magic. That being said, today's experiments use a lot of non-Clifford gates, but shallow circuits, which usually makes tensor network algorithms way cheaper than stabilizer-based simulation algorithms. $\endgroup$
    – Markus Heinrich
    Commented Mar 19 at 13:13
  • $\begingroup$ Thanks Markus. I overlooked this! Is it the case then, that highly entangled (but not so magical) states are best simulated by stabilizer-based methods while highly magical (but not so entangled) are best simulated using tensor-network/MPS methods? Also, in your opinion, what (efficiently computable) measure of entanglement would best characterize the difficulty of simulating a quantum state with Tensor-networks/MPS? $\endgroup$
    – jsbaker
    Commented Mar 19 at 19:41
  • 2
    $\begingroup$ Yes, there should be a crossover point. Not so sure where it exactly is, though. Tensor networks methods perform really well, and are actively developed and maintained. In principle, the effective bond dimension (related to Schmidt rank) should should be the measure you're looking for (although the details depend on the precise method used). $\endgroup$
    – Markus Heinrich
    Commented Mar 20 at 10:49
  • $\begingroup$ Thanks again @MarkusHeinrich. So, we are nearly there. It seems like the effective bond dimension is what we need yes. however, how does one determine this efficiently given a state prepared in a quantum computer? This paper determines the scaling of the bond dimension with the $\alpha$-Renyi entropies but I am not aware of any way one can measure the $\alpha$-Renyi entropies efficiently given a quantum state. $\endgroup$
    – jsbaker
    Commented Mar 21 at 4:43
  • 1
    $\begingroup$ Ah nevermind, it looks like there are several methods for efficiently estimating the $\alpha$-Renyi entropy. Here for example. I was confusing this with the stabilizer Renyi entropy (which measures magic). So in that sense, half of this question (related to entanglement) is now answered; we can bound the computational effort of a MPS simulation knowing the $\alpha$-Renyi entropy which can be efficiently measured. Now, how do we do the same thing with the number of T-gates using an efficiently measurable magic quantifier? After this, we are done! $\endgroup$
    – jsbaker
    Commented Mar 21 at 5:16

0

Reset to default

Browse other questions tagged or ask your own question.