Tag Info

1

Suppose you have a chain of length $n$. Then the smallest amplitude in that chain is no larger than $2^{-n}$. But this implies the operations you are applying have a maximum error term $\epsilon$ that is smaller than that, since otherwise they would overwhelm that amplitude. And approximating arbitrary rotations to within $\epsilon$ requires $\Omega(\lg(1/\... 2 I wonder if there are explicit examples where the T-count scales stronger with n. [...] maybe superlinear or even exponential. Here's an existence proof of an$n$qubit magic state with a T count of$\Theta(2^{n/4})$, based on caching QROM reads. It takes$\Theta(2^{n/4})$T gates to prepare the cached-QROM state, and also you can consume the cached-QROM ... 2 Liu and Winter (http://arxiv.org/abs/2010.13817) have shown that any "reasonable" magic monotone is asymptotically bounded by$n$. Moreover, Haar-random pure states cluster around that value (deviation is exponentially suppressed in$n$). By a standard argument (as in Beverland et al.),$\Omega(n)$magic implies that we need$\Omega(n)\$ copies of ...

Top 50 recent answers are included