New answers tagged

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