# Pseudomagic quantum states

Andi Gu<EMAIL_ADDRESS>Department of Physics, Harvard University, 17
Oxford Street, Cambridge, MA 02138, USA  Lorenzo Leone  lorenzo.leone@fu-
berlin.de Department of Physics, University of Massachusetts Boston, 100
Morrissey Boulevard, Boston, MA 02125, USA  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany  Soumik Ghosh
Department of Computer Science, University of Chicago, Chicago, Illinois
60637, USA  Jens Eisert  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany  Helmholtz-Zentrum Berlin für
Materialien und Energie, 14109 Berlin, Germany  Fraunhofer Heinrich Hertz
Institute, 10587 Berlin, Germany  Susanne F. Yelin  Department of Physics,
Harvard University, 17 Oxford Street, Cambridge, MA 02138, USA  Yihui Quek
Department of Physics, Harvard University, 17 Oxford Street, Cambridge, MA
02138, USA  Department of Computer Science, Harvard John A. Paulson School Of
Engineering And Applied Sciences, 150 Western Ave, Boston, MA 02134

###### Abstract

Notions of nonstabilizerness, or “magic”, quantify how non-classical quantum
states are in a precise sense: states exhibiting low nonstabilizerness
preclude quantum advantage. We introduce ‘pseudomagic’ ensembles of quantum
states that, despite low nonstabilizerness, are computationally
indistinguishable from those with high nonstabilizerness. Previously, such
computational indistinguishability has been studied with respect to
entanglement, introducing the concept of pseudoentanglement. However, we
demonstrate that pseudomagic neither follows from pseudoentanglement nor
implies it. In terms of applications, the study of pseudomagic offers fresh
insights into the theory of quantum scrambling: it uncovers states that, even
though they originate from non-scrambling unitaries, remain indistinguishable
from scrambled states to any physical observer. Additional applications
include new lower bounds on state synthesis problems, property testing
protocols, and implications for quantum cryptography. Our work is driven by
the observation that only quantities measurable by a computationally bounded
observer – intrinsically limited by finite-time computational constraints –
hold physical significance. Ultimately, our findings suggest that
nonstabilizerness is a ‘hide-able’ characteristic of quantum states: some
states are much more magical than is apparent to a computationally bounded
observer.

The boundary between quantum and classical computation is a central question
in current research, with a focus on identifying uniquely quantum resources
that contribute to a quantum advantage. One such resource is nonstabilizerness
(“magic”), which is a measure of the non-Clifford resources needed to prepare
a quantum state [1, 2, 3]. Nonstabilizerness is directly connected to the
hardness of classically simulating a quantum state [4, 5, 6, 7, 8, 9, 10, 11,
12], the yield of magic state distillation protocols [13, 14, 1, 15, 16, 17,
18, 19, 20, 21, 22], the overhead required for fault-tolerant quantum
computation [23, 24, 25, 26], and the degree of chaos in a system [27, 28, 29,
30]. Given these connections, one might expect that quantum states with high
nonstabilizerness are inherently different, and more non-classical, than
states with low values.

In this work, we challenge this intuition by constructing ensembles of states
that are poor in magic resources but, nonetheless, are _computationally
indistinguishable_ from an ensemble of states that are rich in magic
resources. Because they masquerade as highly magical ensembles, we call the
former “pseudomagic” ensembles. Moreover, their nonstabilizerness can also be
_tuned_ : for any value of nonstabilizerness strictly greater than $\log(n)$
and up to $n$, there is a pseudomagic ensemble with that amount of
nonstabilizerness. While the ‘pseudoentangled’ ensembles introduced in Ref.
[31] happen to also display the above ‘pseudomagic’ properties, we prove that
the amount of each resource in them (i.e., entanglement and magic) can be
_tuned independently_ : the existence of pseudoentangled ensembles does not
imply their pseudomagic counterparts, nor vice versa. While we quantify
nonstabilizerness in the rest of this work with the measure of stabilizer
Rényi entropy [27], we explain how to generalize our construction to many
other popular magic measures, such as robustness of magic [13], stabilizer
fidelity and extent [8], max relative entropy of magic [32].

As physically motivated applications, we discuss the implication of
pseudomagic for quantum chaos theory. Our results imply, counterintuitively,
that some states generated by non-scrambling unitaries are computationally
indistinguishable from states generated by scrambling unitaries. Furthermore,
we show that the existence of pseudomagic states immediately implies the
existence of a quantum cryptographic primitive known as EFI pairs [33].
Finally, we employ our findings to obtain lower bounds for black-box magic
state distillation and property testing protocols.

_The computationally bounded observer._ The central claim of this work is that
an idea from computer science – namely, computational indistinguishability –
has significant ramifications for the ways in which we understand physics. Say
we have two $n$-particle systems $S_{1}$ and $S_{2}$ that differ in some
physical characteristic $C$, and we aim to distinguish between the two
systems. What if the time needed for _any_ distinguishing method is on par
with the age of the universe? If so, we then have two systems which
purportedly differ in some physical attribute $C$, yet nevertheless can never
be distinguished in any reasonable amount of time – so in what sense can we
say $C$ is a genuine physical attribute? In the language of computer science,
a distinguishing algorithm is efficient if its requisite computational time
(i.e., number of elementary operations) scales polynomially with the number of
particles, denoted by $\operatorname{poly}(n)$, and inefficient if it scales
exponentially as $\exp(n)$. This (fuzzy) distinction delineates between a
feasible distinguishing scheme and an impractical one. Indeed, if every
possible distinguishing algorithm scales exponentially with the number of
particles $n$, we say the two systems $S_{1}$ and $S_{2}$ are ‘computationally
indistinguishable’, as for even a modest system size $n\sim 120$, an
exponential distinguisher’s runtime will surpass the age of the universe $\sim
10^{18}\,$s, impossible to execute in practice. This idea motivates us to
introduce the notion of the Computationally Bounded Observer (CBO), an
observer constrained to measurement schemes that operate within polynomial
time. The results presented in this work demonstrate that the (many-body)
physics observed by a CBO differs profoundly compared to an unconstrained
observer. This introduces a unique perspective into quantum many-body systems,
transforming the laboratory from a mere verifier of quantum theories into an
integral part of the theory itself, where the limitations of observers assume
a central role.

_Pseudomagic._ First, we review some useful definitions associated with
nonstabilizerness. Let $\mathbb{P}_{n}$ be the Pauli group on $n$ qubits,
$\mathcal{C}_{n}$ be the Clifford group, and let $\Sigma$ be the set of pure
stabilizer states. A stabilizer operation $\mathcal{S}$ is a quantum channel
obeying $\mathcal{S}(\Sigma)=\Sigma$, which is to say that $\mathcal{S}$
preserves the set of stabilizer states [11]. There are many ways to quantify
nonstabilizerness [13, 8, 27, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43], but
we limit our attention to the magic measures introduced in Table 1. The second
key concept in this work is the notion of “computational indistinguishability”
for two ensembles of states, which means that no CBO (i.e., polynomially-
bounded algorithm) can tell the difference between the two ensembles. We refer
the reader to Ref. [44] for a detailed treatment of this concept and its
relevance for quantum cryptography. Having established the two notions of
magic and computational indistinguishability, we now introduce pseudomagic.

Magic measure | Definition
---|---
Stabilizer entropy [27] | $M_{\alpha}({\psi})=\frac{1}{1-\alpha}\log\frac{1}{d}\sum_{P}\tr^{2\alpha}(P\psi)$
Robustness of magic [13] | $\mathcal{R}(\psi)=\log\min\\{\norm{c}_{1}\mid\psi=\sum_{i}c_{i}\outerproduct{\sigma_{i}}{\sigma_{i}}\\}$
Stabilizer fidelity [8] | $\mathcal{F}_{\textrm{stab}}(\psi)=-\log\max_{\sigma\in\Sigma}\absolutevalue{\innerproduct{\psi}{\sigma}}^{2}$
Stabilizer extent [8] | $\xi(\psi)=\log\min(\sum_{\phi}\absolutevalue{c_{\phi}})^{2}$
Max-relative entropy [32] | $D_{\max}(\psi)=\log\min\\{\lambda\mid\lambda\sigma-\psi\geq 0\\}$

Table 1:  Magic measures and their definitions. Figure 1: The ‘pseudomagic’
state ensembles discussed in this work are computationally indistinguishable
from highly magical states produced by scrambling dynamics (e.g., Haar random
states).

######  Definition 1 (Pseudomagic).

Let $\mathcal{M}$ be a magic measure. A pseudomagic pair with gap $f(n)$ vs.
$g(n)$ (where $f(n)>g(n)$) consists of two state ensembles:

  1. (a)

a ‘high magic’ ensemble of $n$-qubit quantum states
$\\{|\psi_{k_{1}}\rangle\\}$ such that $\mathcal{M}({\psi_{k_{1}}})=f(n)$ with
high probability over $k_{1}$, and

  2. (b)

a ‘low magic’ ensemble of $n$-qubit quantum states
$\\{|\phi_{k_{2}}\rangle\\}$ such that $\mathcal{M}({\phi_{k_{2}}})=g(n)$ with
high probability over $k_{2}$,

such that the two ensembles are computationally indistinguishable, even when
given polynomially many copies.

Qualitatively, states from the ensemble $\\{\ket{\phi_{k_{2}}}\\}$ mimic much
more ‘magical’ states to all CBOs, even though they themselves are ‘low
magic’. In the rest of this work we use stabilizer Rényi entropy as our magic
measure, given by

$M_{\alpha}({\psi})=\frac{1}{1-\alpha}\log\frac{1}{2^{n}}\sum_{P\in\mathbb{P}_{n}}\tr^{2\alpha}(P\psi),$
(1)

which is a magic monotone for $\alpha\geq 2$ [45]; see SM I for a detailed
discussion 111Moreover, the stabilizer entropy possesses two desirable traits:
it is experimentally measurable, and serves as a lower bound for all other
magic monotones listed in Table 1. These feautures enable us to demonstrate
the existence of states with a significant and precise pseudomagic gap of
$\log n$ versus $n$. See Supplemental Material for an in-depth discussion
about the role of $M_{\alpha}$ in defining pseudomagic.. Combining the
‘computational indistinguishability’ property with the properties of
stabilizer Rényi entropy, we show that $g(n)$, the nonstabilizerness of the
low-magic ensemble, can be no smaller than $\omega(\log n)$ 222To remind the
reader, $f=o(g(n))\implies\lim{f(n)}/{g(n)}=0$,
$f=\omega(g(n))\implies\lim{f(n)}/{g(n)}=\infty$, and finally
$f=\Theta(g(n))\implies\exists C_{1},C_{2}>0$ such that
$C_{1}\leq\lim{f(n)}/{g(n)}\leq C_{2}$.:

######  Lemma 1 (Bound to stabilizer entropies).

Let $\mathcal{E}$ be the low magic ensemble of a pseudomagic pair. Then the
$\alpha$-Rényi stabilizer entropies obey $M_{\alpha}({\psi})=\omega(\log n)$,
with high probability over the choice of $\ket{\psi}\in\mathcal{E}$.

In the next section, we turn to the construction of pseudomagic pair with
maximal gap, i.e. $\omega(\log n)$ vs. $O(n)$.

_Construction of pseudomagic ensembles._ For any function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and subset $S\subseteq\\{0,1\\}^{n}$, we define
the associated subset phase state as [31]

$\ket{\psi_{f,S}}=\frac{1}{\sqrt{|S|}}\sum_{x\in S}(-1)^{f(x)}\ket{x}.$ (2)

In Ref. [31], it was shown the ensemble $\mathcal{E}=\\{\ket{\psi_{f,S}}\\}$
of subset phase states (for pseudorandom functions $f$ and subsets $S$) is
both efficiently preparable, and computationally indistinguishable from Haar
random states. In this section, we show that $\mathcal{E}$ also saturates the
nonstabilizerness lower bound in Lemma 1. Since the ensemble of Haar-random
states $\mathcal{E}_{\operatorname{Haar}}$ have stabilizer entropy $\Theta(n)$
with overwhelming probability SM II.2,
$(\mathcal{E},\mathcal{E}_{\operatorname{Haar}})$ form a pseudomagic pair with
gap $\omega(\log n)$ vs. $O(n)$. We then show that applying a polynomial depth
quantum circuit $U$ to $\mathcal{E}$ results in a high-magic ensemble
$\mathcal{E}_{U}$ that, thanks to the transitivity of computational
indistinguishability, is computationally indistinguishable from the low-magic
ensemble $\mathcal{E}$, thus forming another pseudomagic pair
$(\mathcal{E},\mathcal{E}_{U})$ (see Fig. 2).

######  Theorem 1 (Subset phase states display pseudomagic).

For any $k\in[\omega(\log n),n]$, there exists an ensemble
$\mathcal{E}=\\{\ket{\psi_{f,S}}\\}$ for $|S|=2^{k}$ that has
$M_{\alpha}({\psi_{f,S}})=O(k)$. For $\alpha\leq 2$, this bound is tight:
$M_{\alpha}({\psi_{f,S}})=\Theta(k)$. Furthermore,

  1. (a)

$\mathcal{E}$ is computationally indistinguishable the ensemble of Haar random
states $\mathcal{E}_{\operatorname{Haar}}$. Therefore,
$(\mathcal{E},\mathcal{E}_{\operatorname{Haar}})$ forms a pseudomagic pair
with gap $\omega(\log n)$ vs. $O(n)$.

  2. (b)

There exists a quantum circuit $U$ composed solely of single-qubit gates
(i.e., it has depth 1) such that $(\mathcal{E}$, $\mathcal{E}_{U})$, where
$\mathcal{E}_{U}=\\{U\ket{\psi_{f,S}}\\}$, also forms a pseudomagic pair with
maximal gap $\omega(\log n)$ vs. $O(n)$.

It is natural to ask if, besides the stabilizer Rényi entropy, other magic
measures (see Table 1) can be used to define pseudomagic. In SM II.4, we show
that both the $\alpha$-stabilizer entropies $M_{\alpha}(\psi)$ and the log-
robustness of magic $\mathcal{R}(\psi)$ are measures of pseudomagic with gap
$\Theta(n)$ vs. $\Theta(\operatorname{poly}\log n)$. As a corollary, we have a
sufficient condition for a magic measure to be a good measure for defining
pseudomagic. For any magic monotone $\mathcal{M}$, if there exists an $\alpha$
such that $\Omega(M_{\alpha}(\psi))\leq\mathcal{M}(\psi)\leq
O(\mathcal{R}(\psi))$ for pure states $\psi$, then $\mathcal{M}$ is also a
measure of pseudomagic with gap $\Theta(n)$ vs.
$\Theta(\operatorname{poly}\log n)$. In SM II.5, we use this fact to show that
the magic monotones
$\mathcal{M}=\mathcal{F}_{\textrm{stab}}(\psi),\xi(\psi),D_{\max}(\psi)$, as
defined in Table 1, are also measures of pseudomagic with gap $\Theta(n)$ vs.
$\Theta(\operatorname{poly}\log n)$. Notably, these measures serve as genuine
magic monotones even in the context of mixed-state magic resource theory.

_Implications to quantum scrambling._ Having defined the notion of
pseudomagic, we now use it to address some important aspects of quantum
information scrambling, and explore how CBOs challenge its foundational
principles. One way of defining a scrambling unitary evolution $U$ is to say
that it is scrambling if it attains the Haar value for its $2k$-point _out-of-
time-order correlators_ (OTOCs) [48, 49]. These OTOCs are denoted by $C_{2k}$
and are defined as

$C_{2k}(U)\coloneqq\frac{1}{d}\tr(\tilde{P}_{1}Q_{1}\tilde{P}_{2}Q_{2}\cdots\tilde{P}_{k}Q_{k}),$
(3)

where $P_{i}$ and $Q_{i}$ are non-identity Pauli operators for $i=1,\ldots,k$
and $\tilde{P}_{i}\coloneqq U^{{\dagger}}P_{i}U$. To be precise, $U$ is
scrambling if $C_{2k}(U)=\tilde{O}(C_{2k}(U_{\operatorname{Haar}}))$, where
$\tilde{O}$ stands for an irrelevant polynomial overhead. Indeed, typically
$C_{2k}(U_{\operatorname{Haar}})=O(\exp(-\gamma n))$ with $\gamma$ depending
on the particular choice of the correlator $C_{2k}$ [48].

Magic resource theory is linked to quantum information scrambling [50, 51,
52]. Clifford unitaries can be scramblers, but they scramble information in a
relatively simple way [53]. Any unitary exhibiting complex information
scrambling for its OTOCs must contain $\Omega(n)$ non-Clifford gates [54, 55].
Information scrambled by a unitary evolution with less than $n$ non-Clifford
gates can be unscrambled and reconstructed [53, 56]. Consequently, the mere
existence of pseudomagic states that are also pseudorandom (i.e., subset phase
states), suggests the existence of non-complex scramblers that nonetheless
generate states indistinguishable from states generated by maximal scramblers.
More precisely, we establish that such states must be generated by a unitary
evolution that exhibits exponentially separated OTOCs from the typical Haar
value.

######  Theorem 2 (Hidden quantum scrambling).

Let $\mathcal{E}$ be an ensemble of pseudomagic states that is also
pseudorandom. Let $\ket{\psi}\in\mathcal{E}$ and let $U$ such that
$\ket{\psi}=U\ket{0}^{\otimes n}$. The $2k$-point OTOCs of $U$ (for $k\geq 4$)
are exponentially separated from the Haar value,

$C_{2k}(U)=\Omega(\exp(n)C_{2k}(U_{\operatorname{Haar}})).$ (4)

Therefore, although it generates a state that is on-average computationally
indistinguishable from Haar-random, $U$ is not fully scrambling.

The proof of this can be found in SM IV. The curious implication of Theorem 2
is this: any physical observer, inherently constrained by computational limits
(i.e., a CBO), cannot differentiate between a maximally scrambling evolution
and non-scrambling one solely based on the observed resultant state (see Fig.
1). As a result, a CBO interprets quantum scrambling evolutions differently
from an unrestricted observer, exposing a significant conceptual challenge in
characterizing quantum information scrambling. Additionally, our findings
could potentially also lead to implications for the theory of quantum chaos.
Indeed, by defining quantum chaotic evolution as maximally scrambling unitary
operators, then Theorem 2 would imply the impossibility for a CBO to
distinguish between a chaotic quantum evolution from a non-chaotic one.
However, while some authors [48] are inclined to think about quantum chaotic
evolution precisely as maximal scramblers [48], this concept has been
challenged in Ref. [57], where it has been proven that scrambling (when
restricted to $k=2$) does not imply chaos. The question of whether maximal
scrambling, as probed by higher order OTOCS, implies chaos remains an exciting
venue for future research.

_Implications to quantum cryptography._ An essential primitive for classical
cryptography is the concept of a _one-way function_ (OWF), which is a function
that is efficient to evaluate but hard to invert. However, the story is much
different in the _quantum_ world: OWFs are unnecessary for some quantum
cryptographic constructions to hold [58, 59]. This leads naturally to a
question of whether there is an indespensible primitive for quantum
cryptography that serves a similar role to OWFs for classical cryptography. In
Ref. [33], the authors introduce EFI pairs as this quantum analogue and show
that it is necessary for many secure quantum cryptographic schemes, including
bit commitment [60, 61], oblivious transfer [62, 63], multiparty quantum
computation [64], and zero knowledge proofs [65]. EFI pairs are state
ensembles generated by efficient circuits that are statistically far but
computationally indistinguishable. In light of the proposed significance of
EFIs, we show the following.

######  Theorem 3 (Cryptographic implications).

Consider an ensemble of efficiently preparable pseudomagic states that have
stabilizer entropy $M_{1}=\Theta(g(n))$ with high probability, where $g(n)$ is
tunable in the range $\omega(\log n)$ and $O(n)$. Then, the pseudomagic
ensemble, along with the high nonstabilizerness ensemble, forms an EFI pair.

For a proof, see SM V. Crucially, Theorem 3 holds even in a world without
quantum-secure OWFs: it says that the bare existence of pseudomagic states
with tunable stabilizer entropy implies the existence of EFI pairs and the
world of cryptographic applications they unlock. This strengthens the case
that EFI pairs are a more fundamental primitive for quantum cryptography than
OWFs.

_No efficient black-box magic-state distillation._ Several architectures for
universal fault-tolerant quantum computing rely on applying stabilizer
operations to carefully prepare resource states called magic states [66, 25,
67, 68]. An example is the canonical magic state vector
$\ket{T}=\ket{0}+e^{i\pi/4}\ket{1}$, which when provided as an input to
auxiliary qubits, enables $T$-gate implementation using only stabilizer
operations. However, not all nonstabilizer states are useful for implementing
non-Clifford gates [69], especially noisy ones. This motivates the question,
can we develop efficient (i.e., polynomial-sized circuit description)
stabilizer protocols that can transform generic nonstabilizer states $\rho$
into useful nonstabilizer states, such as $\ket{T}$? In line with the spirit
of analogous tasks for entanglement resource theory [70, 71], we term this
task _black-box magic-state distillation_.

######  Theorem 4 (Black-box magic state distillation).

Given a magic monotone $\mathcal{M}$ such that
$\Omega(M_{\alpha}(\psi))\leq\mathcal{M}(\psi)\leq O(\mathcal{R}(\psi))$ for
all pure states $\psi$, any efficient stabilizer protocol that synthesizes a
state vector $\ket{B}\bra{B}$ from an arbitrary (potentially mixed) input
state $\rho$ requires

$\Omega\left(\frac{\mathcal{M}(\ket{B}\bra{B})}{\log^{1+c}\mathcal{M}(\rho)}\right)$
(5)

copies of $\rho$, for any constant $c>0$. Remarkably the above is valid for
$\mathcal{M}=\mathcal{F}_{\mathrm{stab}},\xi,D_{\max}$ in Table 1.

The proof of this can be found in SM VI. This theorem shows how pseudomagic
provides a complementary perspective to magic resource theory in determining
the limits of magic state distillation protocols. If we have a target magic
state $\ket{B}\bra{B}$ and a generic input state $\rho$, naive lower bounds
from resource theory say that we require
$\Omega({\mathcal{M}(\ket{B}\bra{B})}/{\mathcal{M}(\rho)})$ copies of $\rho$
to synthesize $\ket{B}\bra{B}$. This assumes that we can freely convert from
nonstabilizerness in the input state to nonstabilizerness in the output state.
However, once we take into account the computational efficiency of our
synthesization protocol, Theorem 4 intuitively means that if we do not know
what the input state is, the ‘value’ of the nonstabilizerness in the input
state is reduced logarithmically. For instance, assume we have a generic
resource state vector $\ket{\psi}$ with $\mathcal{M}({\psi})=O(n)$. Naive
bounds tell us that we can distill at most $r=O(n)$ canonical magic states
$\ket{T}$, since $\mathcal{M}(\ket{T}\bra{T}^{\otimes r})\propto r$. However,
Theorem 4 imposes a _much stricter_ bound; if our synthesis protocol is
efficient, it can synthesize at most $r=O(\log^{1+c}n)$ copies of $\ket{T}$.

_Independence of pseudomagic and pseudoentanglement: tighter distillation
bounds._ The astute reader may notice that pseudomagic states are the _same_
states that display pseudoentanglement [31]. Given the long history of
resource theories centered on these two quantities, it is natural to wonder if
the existence of pseudomagical ensembles is in some way implied by the
existence of pseudoentangled ensembles. We answer this question in the
negative by showing that the entanglement and magic of a pseudorandom
ensembles can be independently tuned. These findings suggest that neither
pseudomagic nor pseudoentanglement is a generic feature of pseudorandom
ensembles.

Figure 2: The pseudorandom ensemble of states $\mathcal{E}$ (subset phase
states) we consider in this work exhibit both pseudomagic and
pseudoentanglement. However, we show that we can _independently_ tune the
entanglement and nonstabilizerness of these pseudorandom states via local and
Clifford unitaries, respectively.

######  Theorem 5 (Pseudomagic and pseudoentanglement are independent
properties).

Given any two functions $f(n),g(n)\in[\omega(\log n),O(n)]$, there exists a
pseudorandom ensemble whose states have entanglement $\Theta(f(n))$ and magic
$\Theta(g(n))$ up to negligible failure probability. Moreover, there exists a
pseudomagic pair with maximal gap and fixed entanglement $\Theta(f(n))$.
Conversely, there exists a pseudoentangled pair with maximal gap and fixed
magic $\Theta(g(n))$ (for any magic measure in Table 1).

We study the implications of this theorem in the context of distillation
protocols. Theorem 4 and Proposition 3.1 of Ref. [31] are similar in spirit:
they demonstrate that resource-theoretic distillability limits for EPR
pairs/magic states are a gross overestimate of what is achievable by any
computationally efficient algorithm _that is agnostic to its input state_.
However, many magic state or entanglement distillation protocols are hand-
crafted to work on particular classes of input states [1, 72]. Do our lower
bounds still hold up, then, if we knew something about the state we started
with? For example, Ref. [73] asks whether one can distill magic from highly
entangled states. We use Theorem 5 to show that prior knowledge of the
nonstabilizerness of input states does not lead to increased efficiency in
entanglement distillation.

######  Theorem 6 (Prior knowledge of magic does not help entanglement
distillation).

Consider an entanglement distillation protocol that distills EPR pairs from
states drawn from an ensemble $\\{\psi_{k}\\}$. Even if we are guaranteed that
the states $\psi_{k}$ have magic $\Theta(g(n))$ for $g(n)\in[\omega(\log
n),O(n)]$ with high probability, the protocol can distill at most
$O(\log^{1+c}S(\rho))$ Bell pairs with high probability, where $S(\rho)$ is
the von Neumann entanglement entropy of an input state $\rho$ and $c>0$.

An identical strengthening of the black-box magic state distillation protocol
in Theorem 4 is also possible, using a similar proof technique (see the
Supplemental Material). Our results say that for states with super-logarithmic
entanglement (i.e., beyond MPS), magic distillation must be highly
inefficient. Beyond strengthening distillation results, Theorem 5 allows us to
significantly strengthen a wide array of no-go results for any entanglement
(resp., nonstabilizerness) manipulation or detection task to cases where we
even have a priori knowledge about states’ nonstabilizerness (resp.,
entanglement).

Conclusions and outlook. In this work, we introduced the concept of
pseudomagic states, providing an insightful expansion of the magic resource
theory. We first established the theoretical foundation for pseudomagic
states. The core of this framework is the stabilizer entropy, which is unique
among various magic measures (see Table 1) as it does not require an
impractical minimization procedure to be evaluated either theoretically or
experimentally, and lower bounds all the other magic measures. These features
allowed us to demonstrate the existence of pseudomagic ensembles with a large
magic gap $\log n$ vs. $n$, with respect to all the genuine magic monotones in
Table 1. We refer to the Supplemental Material for a technical discussion
regarding the role of the stabilizer entropy in pseudomagic.

We investigated the implications of pseudomagic for quantum scramblers,
quantum cryptography, and magic state distillation. We proved the existence of
states, preparable with a non-scrambling unitary, that appear to have been
generated by a scrambling one, concluding that a computationally bound
observer cannot determine whether a process is scrambling solely by the
generated states. More general questions concerning the existence of
pseudorandom unitaries [74] and its consequence for quantum chaos theory will
be the subject of future research. Another exciting avenue to explore is the
implication that pseudomagic has for many-body physics, particularly in light
of the recent studies of magic-state resource theory [75, 76, 77, 78, 79, 80,
81, 82] and quantum complexity in many-body systems [83]. Finally, our
exploration of Computationally Bounded Observers has revealed the subtleties
of quantum phenomena under computational constraints. This perspective, guided
by computational limitations, deepens our understanding of quantum systems and
underscores the necessity of considering computational constraints in quantum
research, opening avenues for future investigations at the intersection of
quantum information and computation.

_Acknowledgements._ The authors thank Anurag Anshu, J. Pablo Bonilla, Matthias
Caro, Bill Fefferman, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Nazlı
Uğur Köylüoğlu, Salvatore F. E. Oliviero, Kunal Sharma, Ryan Sweke for
insightful discussions, We also thank William Kretschmer for suggesting the
proof of Theorem 3, and Joseph Slote for first using the term “pseudomagic”
and discussing different magic measures. We thank the DFG (CRC 183, FOR 2724),
the BMBF (Hybrid, RealistiQ, QSolid), the ERC (DebuQC), and the Munich Quantum
Valley (K-8) for funding. SFY would like to thank the NSF for funding via the
Cornell HDR institute and the CUA PFC.

## References

  * Bravyi and Kitaev [2005a] S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005a).
  * Howard and Campbell [2017a] M. Howard and E. Campbell, Phys. Rev. Lett. 118, 090501 (2017a).
  * Bartlett [2014] S. D. Bartlett, Nature 510, 345 (2014).
  * Gottesman [1997] D. Gottesman, Stabilizer codes and quantum error correction (1997), quant-ph/9705052 .
  * Aaronson and Gottesman [2004a] S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004a).
  * Bravyi and Gosset [2016] S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016).
  * Bravyi  _et al._ [2016] S. Bravyi, G. Smith, and J. A. Smolin, Phys. Rev. X 6, 021043 (2016).
  * Bravyi  _et al._ [2019] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Quantum 3, 181 (2019).
  * Seddon  _et al._ [2021a] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, PRX Quantum 2, 010345 (2021a).
  * Mari and Eisert [2012] A. Mari and J. Eisert, Phys. Rev. Lett. 109, 230503 (2012).
  * Veitch  _et al._ [2014] V. Veitch, S. A. H. Mousavian, D. Gottesman, and J. Emerson, New J. Phys. 16, 013009 (2014).
  * Veitch  _et al._ [2012] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New J. Phys. 14, 113011 (2012).
  * Howard and Campbell [2017b] M. Howard and E. T. Campbell, Phys. Rev. Lett. 118, 090501 (2017b).
  * O'Gorman and Campbell [2017] J. O'Gorman and E. T. Campbell, Phys. Rev. A 95, 032338 (2017).
  * Bravyi and Haah [2012a] S. Bravyi and J. Haah, Phys. Rev. A 86, 052329 (2012a).
  * Campbell and Howard [2017a] E. T. Campbell and M. Howard, Phys. Rev. A 95, 022316 (2017a).
  * Campbell and Howard [2017b] E. T. Campbell and M. Howard, Phys. Rev. Lett. 118, 060501 (2017b).
  * Campbell [2011] E. T. Campbell, Phys. Rev. A 83, 032317 (2011).
  * Dawkins and Howard [2015] H. Dawkins and M. Howard, Phys. Rev. Lett. 115, 030501 (2015).
  * Campbell and Browne [2010a] E. T. Campbell and D. E. Browne, Phys. Rev. Lett. 104, 030503 (2010a).
  * Anwar  _et al._ [2012] H. Anwar, E. T. Campbell, and D. E. Browne, New J. Phys. 14, 063006 (2012).
  * Krishna and Tillich [2019] A. Krishna and J.-P. Tillich, Phys. Rev. Lett. 123, 070507 (2019).
  * Kitaev [2003] A. Y. Kitaev, Ann. Phys. 303, 2 (2003).
  * Campbell and Browne [2010b] E. T. Campbell and D. E. Browne, Phys. Rev. Lett. 104, 030503 (2010b).
  * Campbell  _et al._ [2017] E. T. Campbell, B. M. Terhal, and C. Vuillot, Nature 549, 172–179 (2017).
  * Xu  _et al._ [2023] Q. Xu, J. P. B. Ataides, C. A. Pattison, N. Raveendran, D. Bluvstein, J. Wurtz, B. Vasic, M. D. Lukin, L. Jiang, and H. Zhou, Constant-overhead fault-tolerant quantum computation with reconfigurable atom arrays (2023), arXiv:2308.08648 .
  * Leone  _et al._ [2022] L. Leone, S. F. E. Oliviero, and A. Hamma, Phys. Rev. Lett. 128, 050402 (2022).
  * Leone  _et al._ [2023a] L. Leone, S. F. E. Oliviero, and A. Hamma, Phys. Rev. A 107, 022429 (2023a).
  * Goto  _et al._ [2022a] K. Goto, T. Nosaka, and M. Nozaki, Phys. Rev. D 106, 126009 (2022a).
  * Garcia  _et al._ [2023] R. J. Garcia, K. Bu, and A. Jaffe, Proc. Natl. Ac. Sc. 120, e2217031120 (2023).
  * Aaronson  _et al._ [2023] S. Aaronson, A. Bouland, B. Fefferman, S. Ghosh, U. Vazirani, C. Zhang, and Z. Zhou, Quantum pseudoentanglement (2023), arXiv:2211.00747 .
  * Liu and Winter [2022a] Z.-W. Liu and A. Winter, PRX Quantum 3, 020333 (2022a).
  * Brakerski  _et al._ [2022] Z. Brakerski, R. Canetti, and L. Qian, On the computational hardness needed for quantum cryptography (2022), arXiv:2209.04101 .
  * Tirrito  _et al._ [2023] E. Tirrito, P. S. Tarabunga, G. Lami, T. Chanda, L. Leone, S. F. E. Oliviero, M. Dalmonte, M. Collura, and A. Hamma, Quantifying non-stabilizerness through entanglement spectrum flatness (2023), 2304.01175 .
  * Haug and Piroli [2023a] T. Haug and L. Piroli, Stabilizer entropies and nonstabilizerness monotones (2023a), arXiv:2303.10152 .
  * Haug  _et al._ [2023a] T. Haug, S. Lee, and M. S. Kim, Efficient stabilizer entropies for quantum computers (2023a), arXiv:2305.19152 .
  * Haug and Kim [2023] T. Haug and M. Kim, PRX Quantum 4, 010301 (2023).
  * Bu  _et al._ [2023a] K. Bu, W. Gu, and A. Jaffe, PNAS 120, e2304589120 (2023a).
  * Bu  _et al._ [2023b] K. Bu, W. Gu, and A. Jaffe, Stabilizer testing and magic entropy (2023b), arXiv:2306.09292 .
  * Chamon  _et al._ [2022] C. Chamon, E. R. Mucciolo, and A. E. Ruckenstein, Ann. Phys. 446, 169086 (2022).
  * Turkeshi  _et al._ [2023] X. Turkeshi, M. Schirò, and P. Sierant, Measuring magic via multifractal flatness (2023), arXiv:2305.11797 .
  * Saxena and Gour [2022] G. Saxena and G. Gour, Phys. Rev. A 106, 042422 (2022).
  * Koukoulekidis and Jennings [pril] N. Koukoulekidis and D. Jennings, npj Quant. Inf. 8, 1 (2022/april).
  * Ji  _et al._ [2018] Z. Ji, Y.-K. Liu, and F. Song, in  _Advances in Cryptology – CRYPTO 2018_ , edited by H. Shacham and A. Boldyreva (Springer International Publishing, Cham, 2018) pp. 126–152.
  * Leone and Bittel [2024] L. Leone and L. Bittel, Stabilizer entropies are monotones for magic-state resource theory (2024), arXiv:2404.11652 [quant-ph] .
  * Note [1] Moreover, the stabilizer entropy possesses two desirable traits: it is experimentally measurable, and serves as a lower bound for all other magic monotones listed in Table 1. These feautures enable us to demonstrate the existence of states with a significant and precise pseudomagic gap of $\log n$ versus $n$. See Supplemental Material for an in-depth discussion about the role of $M_{\alpha}$ in defining pseudomagic.
  * Note [2] To remind the reader, $f=o(g(n))\tmspace+{.2777em}\Relbar\joinrel\Rightarrow\tmspace+{.2777em}\lim{f(n)}/{g(n)}=0$, $f=\omega(g(n))\tmspace+{.2777em}\Relbar\joinrel\Rightarrow\tmspace+{.2777em}\lim{f(n)}/{g(n)}=\infty$, and finally $f=\Theta(g(n))\tmspace+{.2777em}\Relbar\joinrel\Rightarrow\tmspace+{.2777em}\exists C_{1},C_{2}>0$ such that $C_{1}\leq\lim{f(n)}/{g(n)}\leq C_{2}$.
  * Roberts and Yoshida [2017] D. A. Roberts and B. Yoshida, JHEP 2017 (4), 121.
  * Hosur  _et al._ [2016] P. Hosur, X.-L. Qi, D. A. Roberts, and B. Yoshida, JHEP 2016 (2), 4.
  * Leone  _et al._ [2021a] L. Leone, S. F. E. Oliviero, and A. Hamma, Entropy 23, 1073 (2021a).
  * Oliviero  _et al._ [2021a] S. F. E. Oliviero, L. Leone, F. Caravelli, and A. Hamma, SciPost Physics 10, 76 (2021a).
  * Goto  _et al._ [2022b] K. Goto, T. Nosaka, and M. Nozaki, Phys. Rev. D 106, 126009 (2022b).
  * Oliviero  _et al._ [2024] S. F. E. Oliviero, L. Leone, S. Lloyd, and A. Hamma, Phys. Rev. Lett. 132, 080402 (2024).
  * Leone  _et al._ [2021b] L. Leone, S. F. E. Oliviero, Y. Zhou, and A. Hamma, Quantum 5, 453 (2021b).
  * Oliviero  _et al._ [2021b] S. F. E. Oliviero, L. Leone, and A. Hamma, Phys. Lett. A 418, 127721 (2021b).
  * Leone  _et al._ [2024] L. Leone, S. F. E. Oliviero, S. Lloyd, and A. Hamma, Phys. Rev. A 109, 022429 (2024).
  * Dowling  _et al._ [2023] N. Dowling, P. Kos, and K. Modi, Phys. Rev. Lett. 131, 180403 (2023).
  * Kretschmer [2021] W. Kretschmer (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021).
  * Morimae and Yamakawa [2022] T. Morimae and T. Yamakawa, in  _Advances in Cryptology – CRYPTO 2022_ (Springer Nature Switzerland, 2022) pp. 269–295.
  * Lin  _et al._ [2014] D. Lin, Y. Quan, J. Weng, and J. Yan, Quantum bit commitment with application in quantum zero-knowledge proof, Cryptology ePrint Archive, Paper 2014/791 (2014).
  * Yan [2020] J. Yan, General properties of quantum bit commitments, Cryptology ePrint Archive, Paper 2020/1488 (2020).
  * Bartusek  _et al._ [2021] J. Bartusek, A. Coladangelo, D. Khurana, and F. Ma, in  _Advances in Cryptology – CRYPTO 2021_ , edited by T. Malkin and C. Peikert (Springer International Publishing, Cham, 2021) pp. 467–496.
  * Grilo  _et al._ [2021] A. B. Grilo, H. Lin, F. Song, and V. Vaikuntanathan, in  _Advances in Cryptology – EUROCRYPT 2021_ , edited by A. Canteaut and F.-X. Standaert (Springer International Publishing, Cham, 2021) pp. 531–561.
  * Ananth  _et al._ [2022] P. Ananth, L. Qian, and H. Yuen, in  _Advances in Cryptology – CRYPTO 2022_ , edited by Y. Dodis and T. Shrimpton (Springer Nature Switzerland, Cham, 2022) pp. 208–236.
  * Ananth  _et al._ [2021] P. Ananth, K.-M. Chung, and R. L. L. Placa, in  _Advances in Cryptology – CRYPTO 2021_ , edited by T. Malkin and C. Peikert (Springer International Publishing, Cham, 2021) pp. 346–374.
  * Bravyi and Kitaev [2005b] S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005b).
  * Knill [2005] E. Knill, Nature 434, 39 (2005).
  * Bravyi and Haah [2012b] S. Bravyi and J. Haah, Phys. Rev. A 86, 052329 (2012b).
  * Beverland  _et al._ [2020] M. Beverland, E. Campbell, M. Howard, and V. Kliuchnikov, Quant. Sc. Tech. 5, 035009 (2020).
  * Harrow [2005] A. Harrow,  _Applications of coherent classical communication and the Schur transform to quantum information theory_ , Ph.D. thesis, Massachusetts Institute of Technology (2005).
  * Hayashi and Matsumoto [2002] M. Hayashi and K. Matsumoto, Universal distortion-free entanglement concentration (2002), quant-ph/0209030 .
  * Bennett  _et al._ [1996] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, Phys. Rev. Lett. 76, 722–725 (1996).
  * Bao  _et al._ [2022] N. Bao, C. Cao, and V. P. Su, Phys. Rev. A 105, 10.1103/physreva.105.022602 (2022).
  * Haug  _et al._ [2023b] T. Haug, K. Bharti, and D. E. Koh, Pseudorandom unitaries are neither real nor sparse nor noise-robust (2023b), arXiv:2306.11677 .
  * Oliviero  _et al._ [2022a] S. F. E. Oliviero, L. Leone, and A. Hamma, Phys. Rev. A 106, 042426 (2022a).
  * Lami and Collura [2023] G. Lami and M. Collura, Quantum magic via perfect Pauli sampling of matrix product states (2023), arXiv:2303.05536 .
  * Haug and Piroli [2023b] T. Haug and L. Piroli, Phys. Rev. B 107, 035148 (2023b).
  * Chen  _et al._ [2022] L. Chen, R. J. Garcia, K. Bu, and A. Jaffe, Magic of random matrix product states (2022), arXiv:2211.10350 .
  * Odavić  _et al._ [2022] J. Odavić, T. Haug, G. Torre, A. Hamma, F. Franchini, and S. M. Giampaolo, Complexity of frustration: A new source of non-local non-stabilizerness (2022), arXiv:2209.10541 .
  * Rattacaso  _et al._ [2023] D. Rattacaso, L. Leone, S. F. E. Oliviero, and A. Hamma, Stabilizer entropy dynamics after a quantum quench (2023), arXiv:2304.13768 .
  * Tarabunga  _et al._ [2023] P. S. Tarabunga, E. Tirrito, T. Chanda, and M. Dalmonte, Many-body magic via Pauli-Markov chains – from criticality to gauge theories (2023), arXiv:2305.18541 .
  * Chen  _et al._ [2023] J. Chen, Y. Yan, and Y. Zhou, Magic of quantum hypergraph states (2023), arXiv:2308.01886 .
  * Halpern  _et al._ [2022] N. Y. Halpern, N. B. T. Kothakonda, J. Haferkamp, A. Munson, J. Eisert, and P. Faist, Phys. Rev. A 106, 062417 (2022).
  * Note [3] More precisely, the robustness of magic [13] is upper bounded by $\mathcal{R}\leq n+O(2^{-n})$ as proven in Ref. [32].
  * Heinrich and Gross [2019] M. Heinrich and D. Gross, Quantum 3, 132 (2019).
  * Oliviero  _et al._ [2022b] S. F. E. Oliviero, L. Leone, A. Hamma, and S. Lloyd, npj Quant. Inf. 8, 1 (2022b).
  * Liu and Winter [2022b] Z.-W. Liu and A. Winter, PRX Quantum 3, 020333 (2022b).
  * Levine  _et al._ [2019] H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, M. Greiner, V. Vuletić , H. Pichler, and M. D. Lukin, Phys. Rev. Lett. 123, 170503 (2019).
  * Leone [2023] L. Leone,  _Clifford Group and Beyond: Theory and Applications in Quantum Information_ , Ph.D. thesis, University of Massachusetts Boston (2023).
  * Jiang and Wang [2021] J. Jiang and X. Wang, Lower bound the T-count via unitary stabilizer nullity (2021), 2103.09999 .
  * Leone  _et al._ [2023b] L. Leone, S. F. E. Oliviero, and A. Hamma, Learning t-doped stabilizer states (2023b), arXiv:2305.15398 .
  * Grewal  _et al._ [2023] S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Improved stabilizer estimation via bell difference sampling (2023), arXiv:2304.13915 .
  * Hanson and Datta [2019] E. P. Hanson and N. Datta, Universal proofs of entropic continuity bounds via majorization flow (2019), arXiv:1909.06981 .
  * Seddon  _et al._ [2021b] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, PRX Quantum 2, 010345 (2021b).
  * Fang and Liu [2020] K. Fang and Z.-W. Liu, Phys. Rev. Lett. 125, 060405 (2020).
  * Bae and Kwek [2015] J. Bae and L.-C. Kwek, J. Phys. A 48, 083001 (2015).
  * Aaronson and Gottesman [2004b] S. Aaronson and D. Gottesman, Phys. Rev. A 70, 052328 (2004b).

Supplemental Material

In this supplemental material, we provide proofs, additional details
supporting the claims in the main text, as well as additional applications of
pseudomagic.

## Supplemental Material I: Preliminaries

There are many ways to quantify magic. In this work, we consider only
_monotones_ ; that is, those measures that satisfy the following properties:

######  Definition S1 (Magic monotone).

A magic monotone is a scalar function on quantum states, that has the
following properties:

  * •

$\mathcal{M}(\sigma)=0$ if and only if $\ket{\sigma}\in\Sigma$,

  * •

$\mathcal{M}(\mathcal{S}(\psi))\leq\mathcal{M}(\psi)$ for every stabilizer
operation $\mathcal{S}$.

The magic measures $\mathcal{M}$ we consider in our study obey $(i)$ sub-
additivity
$\mathcal{M}({\psi}\otimes{\phi})\leq\mathcal{M}({\psi})+\mathcal{M}({\phi})$,
$(ii)$ are bounded $0\leq\mathcal{M}\leq n+o(1)$ 333More precisely, the
robustness of magic [13] is upper bounded by $\mathcal{R}\leq n+O(2^{-n})$ as
proven in Ref. [32]., which will be assumed throughout this work.

###  I.1 Properties of stabilizer Rényi entropies

In this work we will focus on the measure of $\alpha$-stabilizer entropies.
Let us now introduce this family of measures formally. We observe that given a
$n$-qubit (pure or mixed) state $\psi$, we can define the probability
distribution

$\Xi_{\psi}\coloneqq\\{d^{-1}\tr^{2}(P\psi)\operatorname{Pur}^{-1}(\psi)\mid
P\in\mathbb{P}_{n}\\},$ (S1)

where $\mathbb{P}_{n}$ is the Pauli group on $n$ qubits and
$\operatorname{Pur}(\psi)\coloneqq\tr(\psi^{2})$ its purity. The stabilizer
entropy $M_{\alpha}$ is defined as (for every $0\leq\alpha<\infty$)

$M_{\alpha}(\psi)\coloneqq S_{\alpha}(\Xi_{\psi})+S_{2}(\psi)-\log d,$ (S2)

where $S_{\alpha}(\Xi_{\psi})$ is the classical $\alpha$-Rényi entropy of the
probability distribution in Eq. S1, while
$S_{2}(\psi)\coloneqq-\log\operatorname{Pur}(\psi)$ is the log-purity of
$\psi$. To be concrete, we list three explicit expressions for $M_{\alpha}$
for common choices of $\alpha$ (we also assume $\psi$ is pure for simplicity),

$M_{\alpha}(\psi)=\begin{cases}\log(\absolutevalue{\\{P\in\mathbb{P}_{n}\mid\tr(P\psi)\neq
0\\}})-\log d&\text{for $\alpha=0$},\\\
-\sum_{P}\frac{\tr^{2}(P\psi)}{d}\log\tr^{2}(P\psi)&\text{for $\alpha=1$},\\\
-\log(\sum_{P}\frac{\tr^{4}(P\psi)}{d})&\text{for $\alpha=2$.}\end{cases}$
(S3)

The first two cases of $\alpha=0$ and $1$ are manifestly different from the
definition
$M_{\alpha}({\psi})=\frac{1}{1-\alpha}\log\frac{1}{d}\sum_{P}\tr^{2\alpha}(P\psi)$
presented in Equation (1) of the main text. Despite the formal difference, the
$\alpha=0$ and $1$ cases are not discontinuous exceptions to the definition in
Equation (1). Rather, they follow from the definition of the classical Rényi
entropies: $\lim_{\alpha\to
0}S_{\alpha}(\Xi_{\psi})=\log\absolutevalue{\text{supp}\ \Xi_{\psi}}$, where
$\text{supp}\ \Xi_{\psi}$ is the support of the distribution $\Xi_{\psi}$.
Similarly, $\lim_{\alpha\to
1}S_{\alpha}(\Xi_{\psi})=-\sum_{P}\Xi_{\psi}(P)\log(\Xi_{\psi}(P))$ (i.e., the
Shannon entropy of $\Xi_{\psi}$). Therefore, despite the fact that the cases
$\alpha=0$ and $\alpha=1$ may superficially seem to be special exceptions, in
what follows (unless otherwise specified), we will be studying $M_{\alpha}$
for any $\alpha$.

Let us list important properties of the $\alpha$-stabilizer entropies.

  * •

$M_{\alpha}(\sigma)=0$ if and only if $\psi=\sum_{P\in G_{\sigma}}\phi_{P}P$,
where $G_{\sigma}$ is a commuting subgroup of $\mathbb{P}$ and
$\phi_{P}\in\\{\pm 1\\}$. Notice that $\sigma$ is pure if and only if
$\absolutevalue{G_{\sigma}}=2^{n}$. The zeros of the stabilizer entropy (i.e.,
the states $\psi$ for which $M_{\alpha}(\psi)=0$) coincides with the set of
pure stabilizer state plus mixed stabilizer states defined above. However,
$M_{\alpha}(\psi)>0$ when $\psi$ is a convex combination of stabilizer states:
$\psi=\sum_{\sigma\in\Sigma}p_{\sigma}\outerproduct{\sigma}{\sigma}$, where
$p_{\sigma}\geq 0$. Notice that the zeros of the stabilizer entropy do not
coincide with the zeros of other magic measures for mixed states.

  * •

For every Clifford unitary operator $C$, then $M_{\alpha}(C^{{\dagger}}\psi
C)=M_{\alpha}(\psi)$;

  * •

$0\leq M_{\alpha}(\psi)<n$, where the upper bound is a strict inequality.

  * •

They feature a hierarchy: $M_{\alpha}(\psi)<M_{\alpha^{\prime}}(\psi)$ for any
$\psi$ if $\alpha>\alpha^{\prime}$.

  * •

They are additive:
$M_{\alpha}(\psi\otimes\phi)=M_{\alpha}(\psi)+M_{\alpha}(\phi)$.

  * •

For pure states ${\psi}$, they lower bound the stabilizer nullity:
$M_{\alpha}({\psi})\leq\nu({\psi})$.

  * •

For pure states and $\alpha>1/2$, they lower bound the robustness of magic
$M_{\alpha}({\psi})<2\mathcal{R}({\psi})$ [85].

  * •

For pure states and $\alpha>1$, they lower bound the stabilizer fidelity:
$M_{\alpha}({\psi})<\frac{2\alpha}{\alpha-1}\mathcal{F}_{\textrm{stab}}({\psi})$
[35].

  * •

Defining $T$-count as smallest number $t(\psi)$ of $T$-gates used to prepare
the state vector $\ket{\psi}$ from a stabilizer state, the stabilizer
entropies lower bound the $T$-count: $M_{\alpha}({\psi})\leq t(\psi)$.

  * •

Using the swap trick, when $\alpha$ is an integer greater than 1, we can also
write $M_{\alpha}$ as follows:

$M_{\alpha}({\psi})=\frac{1}{1-\alpha}\log\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha}),$ (S4)

with $\Pi^{(2\alpha)}\coloneqq d^{-1}\sum_{P\in\mathbb{P}_{n}}P^{\otimes
2\alpha}$ being a Hermitian operator. Thanks to this property, stabilizer
entropies can be measured on quantum computers with both single copy protocols
such as randomized measurements [86], as well as multi-copy protocols [37,
35].

###  I.2 A remark on the role of stabilizer entropy in defining pseudomagic

Stabilizer entropies serve as pure-state magic monotones for every integer
$\alpha\geq 2$, while they demonstrably violate the monotonicity condition for
$\alpha<2$, see [45]. A pure-magic monotone implies that, for deterministic
stabilizer protocols—those mapping pure states to pure states—the quantity
remains nonincreasing. Given that stabilizer entropies are inherently defined
for pure states, this property is the natural one to consider. Furthermore, in
Ref. [45], an extension of stabilizer entropy to mixed states, which adheres
to monotonicity under general stabilizer protocols, is also presented.

Besides the prominent role of stabilizer entropies among magic measures (being
analytically computable and experimentally measurable), the stabilizer entropy
has proven to be a fundamental tool for defining and exploring pseudomagic.
For instance, a key property we make frequent use of, especially when
developing a general framework for pseudomagic, was that several other popular
magic monotones are lower bounded by the stabilizer entropy, hence qualified
as useful pseudomagic measures.

The use of stabilizer entropy for pseudomagic is of utmost importance for
quantum highlights in the context of quantum scrambling theory (given its
strict relationship to OTOCs) and in quantum cryptographic implications
(thanks to the Fannes inequality for $M_{1}$).

Moreover, stabilizer entropies play a key role in defining pseudomagic. To be
more concrete, all the other monotones, except for stabilizer entropy, involve
a minimization procedure that renders them computationally and experimentally
intractable to measure. Consequently, they are unsuitable for proving a
pseudomagic gap, which asks for measurement using multiple copies to provide
the lower bound $\omega(\log n)$ for pseudomagic ensembles. Thanks to the fact
that stabilizer entropy $(i)$ provides a lower bound for all the other magic
monotones and $(ii)$ can be experimentally measured, we are able to
demonstrate the existence of states with an extensive and tight gap of $\log
n$ versus $n$ in magic, which holds true for all the monotones discussed in
this paper. This fact is reflected by 3.

###  I.3 Pseudorandom states

The other key idea we use throughout this work is the notion of pseudorandom
states, which are ensembles of states that are disguised as Haar random.

######  Definition S2 (Pseudorandom states [44]).

An ensemble of $n$-qubit quantum states $\left\\{\ket{\psi_{k}}\mid
k=1,\ldots,2^{m}\right\\}$ (where $m\in\mathbb{N}$) is said to be
pseudorandom, if:

  * •

Given $k$, the corresponding $\ket{\psi_{k}}$ is preparable in polynomial
time.

  * •

For any efficient quantum algorithm $\mathcal{A}$,

$\absolutevalue{{\mathsf{Pr}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes\operatorname{poly}(n)}\big{)}=1]-{\mathsf{Pr}}[\mathcal{A}\big{(}\ket{\phi}^{\otimes\operatorname{poly}(n)}\big{)}=1]}={\mathsf{negl}}(n),$
(S5)

with high probability for $k\sim\textnormal{Uniform}(2^{m})$ and
$\phi\sim\operatorname{Haar}$. In other words, polynomially many copies of
$\ket{\psi_{k}}$ are computationally indistinguishable from polynomially many
copies of a Haar random state.

The subset phase states are a class of states that are capable of satisfying 2
under certain settings. Specifically, they are ensembles of states

$\ket{\psi_{f,S}}=\frac{1}{\sqrt{\absolutevalue{S}}}\sum_{x\in
S}(-1)^{f(x)}\ket{x}.$ (S6)

indexed by a function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and subsets
$S\subseteq\\{0,1\\}^{n}$. If $\absolutevalue{S}=2^{\omega(\log n)}$ and $f$
is a truly random function, then the subset phase states are statistically
indistinguishable from the Haar random states (i.e., polynomially many copies
of $\ket{\psi_{f,S}}$ are close in trace distance to polynomially many copies
of a Haar random state) [31]. However, if $f$ is randomly chosen, the
corresponding subset phase states are not efficiently preparable. If, on the
other hand, $f$ and $S$ are chosen pseudorandomly (using quantum-secure
pseudorandom functions and subsets), $\ket{\psi_{f,S}}$ _are_ efficiently
preparable. Furthermore, although the resulting ensemble of states are
statistically distinguishable from Haar random states, they are
_computationally indistinguishable_. That is, when $f$ and $S$ are chosen
pseudorandomly and $\absolutevalue{S}=2^{\omega(\log n)}$, $\ket{\psi_{f,S}}$
qualify as pseudorandom states under 2 [31].

#### Experimental feasibility

We propose a potential method that uses Rydberg arrays to realize the subset
phase states $\ket{\psi_{f,S}}$. This illustrates that pseudomagic is not
merely an artificial theoretical construction: it can be implemented in the
laboratory. The first step of our construction provides a concrete
implementation for the black-box oracles $f$ described in Ref. [31]. Assuming
$\absolutevalue{S}=2^{k}$ ($k\leq n$), for any function
$f:\\{0,1\\}^{k}\to\\{0,1\\}$, one can associate a hypergraph over $k$ sites
with hyperedges $E$ such that $f(x)=\sum_{\\{i_{1},\ldots,i_{m}\\}\in
E}\prod_{\alpha=1}^{m}x_{i_{\alpha}}$. One can attach the appropriate phases
to the bit string states by simply applying multi-qubit CZ gates on sites are
connected by hyperedges [87] as

$\prod_{\\{i_{1},\ldots,i_{m}\\}\in E}C^{m-1}Z_{i_{1}\ldots
i_{m}}\ket{+}^{\otimes k}=\sum_{x\in\\{0,1\\}^{k}}(-1)^{f(x)}\ket{x}.$ (S7)

Finally, by concatenating $\ket{0}^{\otimes(n-k)}$ and applying a pseudorandom
permutation of computational basis states [31], we arrive at the desired
$\ket{\psi_{f,S}}$. This protocol has quasipolynomial time complexity, as the
hypergraph representation of $f$ can have a quasipolynomial number of edges,
so we anticipate that for near-term qubit counts $n$, the construction of
these states will be feasible. In particular, neutral-atom platforms such as
Rydberg arrays, are very well-suited for implementing this construction for
two key reasons. First, these platforms offer the advantage of being able to
quickly move qubits around, allowing for the realization of the required
hypergraph connectivity. Secondly, these platforms natively support the
implementation of multi-qubit CZ gates [88]. This streamlines the creation of
subset phase states $\ket{\psi_{f,S}}$ using a native set of gates, making the
implementation straightforward and noise-resilient.

###  I.4 A remark about the need for computational assumptions

Having defined the subset phase states that have been introduced in Ref. [31],
we are in position to highlight the computational assumptions made in this
paper and their implications in the various theorems presented herein. While
Ref. [31] showed that subset phase states can be prepared efficiently assuming
the existence of quantum-secure pseudorandom functions, we observe most of our
applications (except for cryptography) do not require efficient preparability
of pseudomagic states. For all such applications, we can instantiate them with
pseudomagic states that exist unconditionally (i.e. without need for
computational complexity assumptions): simply pick $f$ and $S$ to be a truly
random function and subset, respectively, in which case the subset phase
states are statistically indistinguishable from Haar random states (Theorem
2.1 of Ref. [31]).

## Supplemental Material II: Bounds to pseudomagic

###  II.1 Proof of Lemma 1

First, we will state a result that lower bounds the magic of any state
ensemble that is computationally indistinguishable from Haar random states.
This can be of independent interest to the reader. This implies a lower bound
on the magic of any state ensemble that is computationally indistinguishable
from a high magic ensemble, as we remark after the proof. This is because the
only property we need of Haar random states, for the distinguisher to work, is
that they have high magic.

######  Lemma S1 (Bounds to Rényi entropies (Lemma 1, repeated)).

Let $\mathcal{E}$ be an ensemble of pseudorandom states (i.e., computationally
indistinguishable from Haar random states, which is an ensemble with high
magic). For $\ket{\psi}\sim\mathcal{E}$, one has that with high probability

$M_{\alpha}({\psi})=\begin{cases}\omega\left(\frac{\log n}{\alpha-1}\right)\
&\text{for odd $\alpha$},\\\ \omega\left(\frac{\log n}{\alpha}\right)\
&\text{for even $\alpha$},\end{cases}$ (S8)

for any $\alpha=O(\operatorname{poly}n)$.

###### Proof.

It follows from the definition of Rényi entropies that for any $\ket{\psi}$,
the exponential of the Rényi entropy is the expectation value

$\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})=2^{(1-\alpha)M_{\alpha}({\psi})}$
(S9)

of the Hermitian unitary operator $\Pi^{(2\alpha)}=d^{-1}\sum_{P}P^{\otimes
2\alpha}$. From 3, we see on the one hand that

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}[M_{\alpha}({\psi})\geq
n\beta/\alpha]\approx{\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}[\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})\leq 2^{-n\beta}]\geq 1-2^{-C_{1}/\alpha^{2}2^{(1-2\beta)n}}.$ (S10)

On the other hand, for $\ket{\psi}\sim\mathcal{E}$, assume towards
contradiction that with high probability

$\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})=\Omega\left(\frac{1}{\operatorname{poly}(n)}\right).$ (S11)

The difference in the values of $\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})$
depending on whether $\psi$ is Haar-random or from $\mathcal{E}$ provides a
route to proving our lower bound on $M_{\alpha}$ for pseudorandom states.

Let us set $\alpha$ to be odd first. Then we will show there exists an
efficient distinguisher $\mathcal{A}$ that, given
$O(\alpha\operatorname{poly}(n))$ copies, distinguishes whether an unknown
$\ket{\psi}$ is drawn Haar-randomly or from $\mathcal{E}$. This distinguisher
builds on an observation of Ref. [36], where the authors show that to measure
$\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})$ (with odd $\alpha$), one simply
needs to run a Hadamard test with the unitary $\Pi^{(2\alpha)}$ and estimate
the acceptance probability. However, we don’t even need to estimate
$\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})$; our efficient distinguisher
$\mathcal{A}$ simply runs the above-mentioned Hadamard test with $k=2\alpha$
copies of $\psi$ and outputs 1 if the test outputs 1, which happens with
probability

$\frac{1+\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})}{2}.$ (S12)

Then from Eqs. S10 and S11,

$\begin{gathered}\absolutevalue{{\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}}[\mathcal{A}(\ket{\psi}^{\otimes
k})=1]-{\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}[\mathcal{A}(\ket{\psi}^{\otimes
k})=1]}\\\
>\frac{1+\Omega\left(\frac{1}{\operatorname{poly}(n)}\right)}{2}-\left(1-2^{-C_{1}/\alpha^{2}2^{(1-2\beta)n}}\right)\left(\frac{1+2^{-n\beta}}{2}\right)-O\left(2^{-2^{n}}\right)\\\
=\Omega\left(\frac{1}{\operatorname{poly}(n)}\right),\end{gathered}$ (S13)

thus contradicting the definition of pseudorandom quantum states. Therefore,
we conclude that for odd $\alpha$,

$\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})=o\left(\frac{1}{\operatorname{poly}(n)}\right)$ (S14)

and from Eq. S9 and Eq. S11 one has that for a state drawn from $\mathcal{E}$
and odd $\alpha$,

$M_{\alpha}({\psi})=\omega((\alpha-1)^{-1}\log n)$ (S15)

For the case of even $\alpha$, it is sufficient to employ the hierarchy of
stabilizer entropies $M_{\alpha}\geq M_{\alpha+1}$ to conclude that

$M_{\alpha}({\psi_{f,S}})=\omega(\alpha^{-1}\log n).$ (S16)

∎

######  Remark 1.

The only property we needed of Haar random states in the proof of Lemma 1 was
that they have stabilizer Rényi entropy $\Omega(n)$ (see Eq. S10). Hence, the
same distinguisher, as sketched in Lemma 1, works to distinguish _any_ states
with stabilizer Rényi entropy $\Omega(n)$ from states with stabilizer Rényi
entropy $O(\log n)$. Therefore, Lemma 1, in full generality, follows the same
proof as Lemma 1.

###  II.2 Stabilizer Rényi entropy as a pseudomagic measure

A key result of this work is that the stabilizer entropy is a good candidate
for defining the notion of pseudomagic.

######  Remark 2 (Bounds to non-integer stabilizer entropies).

All our conclusions and theorems presented below apply only to integer values
of $\alpha$ where $\alpha\geq 2$. The reason behind this limitation is that
for non-integer $\alpha$ or $\alpha=0,1$, we are unable to utilize the swap
trick for computing Haar averages. Consequently, the proofs provided below do
not hold in such cases. However, using the hierarchy of stabilizer entropies

$M_{\alpha}({\psi})\geq
M_{\alpha^{\prime}}({\psi})\quad\forall\alpha^{\prime}>\alpha,$ (S17)

we can bound every non-integer $\alpha$ from both above and below if we wish.

The following lemmas characterize the stabilizer entropies attained by Haar
random states and pseudorandom states.

######  Lemma S2 (Stabilizer entropies for Haar random states).

For every integer $\alpha\geq 2$ and for $d=2^{n}$, the Haar average
$\alpha$-stabilizer entropy is lower bounded as

${\mathbb{E}}_{\ket{\psi}\sim\operatorname{Haar}}[M_{\alpha}(\psi)]\geq\begin{cases}n-2+O(d^{-1})&\text{for
$\alpha=2$},\\\ \frac{n}{\alpha-1}+O(d^{-1})&\text{for $\alpha\geq
3$}.\end{cases}$ (S18)

###### Proof.

The proof can be found in Ref. [89]. ∎

Notice that since we are considering integer $\alpha\geq 2$,
$\frac{1}{\alpha-1}>0$, so one has due to Jensen inequality

${\mathbb{E}}_{\ket{\psi}\sim\operatorname{Haar}}[M_{\alpha}(\psi)]\geq-\frac{1}{\alpha-1}\log{\mathbb{E}}_{\ket{\psi}\sim\operatorname{Haar}}\left[\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})\right].$ (S19)

Levy’s lemma then allows us to convert this statement about expectated
stabilizer entropies to a statement in probability.

######  Lemma S3 (Typicality).

Let $\alpha$ be an integer such that $\alpha\geq 2$, and let $\beta<1/2$. If
$\ket{\psi}$ is a random Haar state, then

$M_{\alpha}({\psi})\geq\begin{cases}\frac{n\beta}{\alpha-1}&\text{for odd
$\alpha$}\\\ \frac{n\beta}{\alpha}&\text{for even $\alpha$}\end{cases}$ (S20)

with probability $\geq 1-2^{-\frac{Cd^{1-2\beta}}{4(\alpha+1)^{2}}}$, where
$C=O(1)$.

###### Proof.

Consider the $\alpha$-stabilizer entropy for odd integer $\alpha$. Let us
compute an upper bound for the Lipschitz constant of the function
$\tr(\Pi^{(2\alpha)}\psi^{\otimes 2\alpha})$ as

$\absolutevalue{\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})-\tr(\Pi^{(2\alpha)}\phi^{\otimes
2\alpha})}\leq\norm{\Pi^{(2\alpha)}}_{\infty}\norm{\psi^{\otimes
2\alpha}-\phi^{\otimes 2\alpha}}_{1}\leq 2\alpha\norm{\ket{\psi}-\ket{\phi}}$
(S21)

where we have used the fact that $\Pi^{(2\alpha)}$ is unitary and thus
$\norm{\Pi^{(2\alpha)}}_{\infty}=1$. We have also made use of the following
identity multiple times

$\displaystyle\norm{\psi^{\otimes 2\alpha}-\phi^{\otimes 2\alpha}}_{1}$
$\displaystyle=\norm{\psi^{\otimes 2\alpha}-\psi\otimes\phi^{\otimes
2\alpha-1}+\psi\otimes\phi^{\otimes 2\alpha-1}-\phi^{\otimes 2\alpha}}_{1}$
(S22) $\displaystyle\leq\norm{\psi}_{1}\norm{\psi^{\otimes
2\alpha-1}-\phi^{\otimes
2\alpha-1}}+\norm{\ket{\psi}-\ket{\phi}}\norm{\phi^{\otimes 2\alpha-1}}_{1}$
$\displaystyle=\norm{\psi^{\otimes 2\alpha-1}-\phi^{\otimes
2\alpha-1}}+\norm{\ket{\psi}-\ket{\phi}}.$

Note that

$\norm{\psi-\phi}_{1}^{2}=\norm{\ket{\psi}-\ket{\phi}}^{2}={1-\absolutevalue{\innerproduct{\psi}{\phi}}^{2}}.$
(S23)

Therefore, using Levy’s lemma, we can write

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[\absolutevalue{\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})-d^{-1}+O(d^{-2})}\geq\epsilon\right]\leq
2^{-\frac{Cd\epsilon^{2}}{4\alpha^{2}}}.$ (S24)

Choosing $\epsilon\coloneqq d^{-\beta}$ with $\beta<1/2$, we can write

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[\tr(\Pi^{(2\alpha)}\psi^{\otimes
2\alpha})\leq d^{-\beta}+O(d^{-1})\right]\geq
1-2^{-\frac{Cd^{1-2\beta}}{4\alpha^{2}}}.$ (S25)

Therefore, using Eq. S4 and exploiting the fact that $d\coloneqq 2^{n}$, we
arrive at

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[M_{\alpha}({\psi})\geq\frac{\beta
n}{\alpha-1}+O(d^{-1})\right]\geq 1-2^{-\frac{Cd^{1-2\beta}}{4\alpha^{2}}},$
(S26)

which proves the statement for odd integer $\alpha\geq 3$. For even $\alpha$,
is sufficient to note that the stabilizer entropies follow the hierarchy

$M_{\alpha}({\psi})\geq M_{\alpha+1}({\psi}).$ (S27)

Therefore, with probability greater than
$1-2^{-\frac{Cd^{1-2\beta}}{4(\alpha+1)^{2}}}$, one has

$M_{\alpha}({\psi})\geq M_{\alpha+1}({\psi})\geq\frac{\beta
n}{(\alpha+1)-1}=\frac{\beta n}{\alpha}.$ (S28)

∎

We now upper bound the stabilizer entropy of subset phase states in
particular, by upper-bounding $M_{0}$, as shown in the following lemma.

######  Lemma S4 (Upper bound to $M_{0}$ for subset phase states).

Any subset phase state vector $\ket{\psi_{f,S}}$ satisfies

$M_{0}({\psi_{f,S}})\leq 2\log\absolutevalue{S}.$ (S29)

###### Proof.

Recall the definition of $M_{0}$ as

$M_{0}(\psi)=\log(\absolutevalue{\\{P\in\mathbb{P}_{n}\mid\tr(P\psi)\neq
0\\}})-\log d.$ (S30)

In order to derive the bound, we need to upper bound the number of Pauli
operators that can have component on $\ket{\psi_{f,S}}$, i.e., the cardinality
of the set $\text{supp}\
\Xi_{\psi}\coloneqq\\{P\in\mathbb{P}_{n}\mid\tr(P\psi)\neq 0\\}$. First of
all, note that every Pauli operator $P$ can be written as a product $P=\phi
P_{X}P_{Z}$, where $\phi\in\\{\pm 1,\pm i\\}$, $P_{X}\in\mathbb{X}_{n}$,
$P_{Z}\in\mathbb{Z}_{n}$, and $\mathbb{X}_{n},\mathbb{Z}_{n}$ are the
commuting groups generated by the single qubit $X$ and $Z$s, respectively.
Consider the expectation value

$\matrixelement{\psi_{f,S}}{P_{X}}{\psi_{f,S}}=\frac{1}{\absolutevalue{S}}\sum_{x,x^{\prime}\in
S}(-1)^{f(x)+f(x^{\prime})}\matrixelement{x}{P_{X}}{x^{\prime}}$ (S31)

of $P_{X}\in\mathbb{X}_{n}$ over $\ket{\psi_{f,S}}$. Now, let us consider
fixing the sum over $x^{\prime}$. Since $P_{X}\ket{x^{\prime}}$ corresponds to
a computational basis state, it follows that at most $\absolutevalue{S}$ of
these states can belong to the set $S$, allowing them to potentially have a
non-zero overlap $\matrixelement{x}{P_{X}}{x^{\prime}}$. Given that there are
$\absolutevalue{S}$ possible $\ket{x^{\prime}}$ states on which $P_{X}$ can
act, a (loose) upper bound on the number $N_{X}$ of Pauli operators belonging
to the subgroup $\mathbb{X}_{n}$ with a non-zero expectation value is
$N_{X}\leq\absolutevalue{S}^{2}$. Now, consider a product some $P_{X}$ with a
non-zero expectation value and any element $P_{Z}\in\mathbb{Z}_{n}$. Since
$\absolutevalue{\matrixelement{x}{P_{X}P_{Z}}{x^{\prime}}}=\absolutevalue{\matrixelement{x}{P_{X}}{x^{\prime}}}$,
it is possible that every $P_{Z}\in\mathbb{Z}_{n}$ could contribute to a non-
zero expectation value. Therefore, the cardinality of the set $\text{supp}\
\Xi_{\psi}$ is upper bounded by

$\absolutevalue{\text{supp}\ \Xi_{\psi}}\leq
N_{X}\absolutevalue{\mathbb{Z}_{n}}\leq\absolutevalue{S}^{2}d.$ (S32)

Therefore, we conclude that $M_{0}({\psi_{f,S}})\leq 2\log\absolutevalue{S}$.
∎

######  Theorem S1 (Stabilizer entropies of pseudorandom subset phase states).

The $\alpha$-stabilizer entropy of pseudorandom subset phase states with
size-$\absolutevalue{S}$ subsets satisfies

$\omega(\alpha^{-1}\log n)<M_{\alpha}(\psi_{f,S})\leq
O(\log\absolutevalue{S}).$ (S33)

###### Proof.

The lower bound follows from Lemma 1. The upper bound follows from the bound
$M_{0}({\psi_{f,S}})\leq 2\log\absolutevalue{S}$ proven in 4, and from the
fact that $M_{\alpha}\leq M_{0}$ for every $\alpha>0$. Specifically, for
pseudorandom subset phase states with
$\absolutevalue{S}=\Theta(\exp\operatorname{poly}\log n)$,
$M_{\alpha}(\ket{\psi_{f,S}})=O(\operatorname{poly}\log n)$. ∎

######  Corollary S1 (Stabilizer entropies as a pseudomagic measure).

As a corollary, we have that every stabilizer entropy $M_{\alpha}({\psi})$
with $\alpha=O(\operatorname{poly}\log n)$ is a suitable magic measure to
provide a notion of pseudomagic.

###### Proof.

Subset phase states are pseudorandom for $\absolutevalue{S}=2^{\omega(\log
n)}$ and $\absolutevalue{S}=2^{O(\operatorname{poly}\log n)}$, therefore, with
non-negligible probability one has
$M_{\alpha}({\psi_{f,S}})=O(\operatorname{poly}\log n)$, while from 2, Haar
random states have $M_{\alpha}({\psi_{\operatorname{Haar}}})=O(n/\alpha)$ with
high probability. ∎

###  II.3 Tight magic bounds for subset phase states

Below, we prove a useful bound on $M_{2}({\psi_{f}})$ for random phase states.
A phase state vector, where the phases are given by the function $f$, is the
state vector

$\ket{\psi_{f}}=\frac{1}{\sqrt{2^{n}}}\sum_{x\in\\{0,1\\}^{n}}(-1)^{f(x)}\ket{x}.$
(S34)

This is equivalent to setting $S=\\{0,1\\}^{n}$ for the subset phase states
(and so from now on we drop the subscript $S$ in the notation). We anticipate
its usefulness for proving various concentration inequalities relating to
$M_{2}$. The techniques used in the following proof will also be used for
later results (i.e., 2 and 11) that improve upon 1 by finding _tight_ magic
bounds for subset phase states.

######  Lemma S5 (Average on Rényi-2 stabilizer entropies).

If $f$ is sampled uniformly at random from all possible binary functions
$f:\\{0,1\\}^{n}\to\\{0,1\\}$, then

${\mathbb{E}}_{f}\left[2^{-M_{2}({\psi_{f}})}\right]\leq\frac{20}{2^{n}}.$
(S35)

###### Proof.

By definition of $M_{2}$, we have

$\displaystyle{\mathbb{E}}_{f}\left[2^{-M_{2}({\psi_{f}})}\right]$
$\displaystyle=\frac{1}{2^{n}}\sum_{i}\tr\left(P_{i}^{\otimes
4}{\mathbb{E}}_{f}\left[\outerproduct{\psi_{f}}{\psi_{f}}^{\otimes
4}\right]\right)$ (S36)
$\displaystyle=\frac{1}{32^{n}}\sum_{i,\\{x_{j}\\},\\{y_{j}\\}}{\mathbb{E}}_{f}\left[(-1)^{\sum_{j}f(x_{j})+f(y_{j})}\right]\tr(P_{i}^{\otimes
4}\ket{x_{1},x_{2},x_{3},x_{4}}\bra{y_{1},y_{2},y_{3},y_{4}}),$

where $\\{x_{j}\\}$ denotes the fact that we are summing over all possible
sets of four length-$n$ bitstrings $x_{1},x_{2},x_{3},x_{4}$ (similarly for
$\\{y_{j}\\}$). Now, observe that there are two constraints that must be
simultaneously satisfied in order for the summand to be nonzero.

  1. (a)

${\mathbb{E}}_{f}\left[(-1)^{\sum_{j}f(x_{j})+f(y_{j})}\right]=1$ only when
all the $\\{x_{j}\\}$ and $\\{y_{j}\\}$ can be ‘paired up’. That is, any given
bitstring can only appear an even number of times in
$\\{x_{j}\\}\cup\\{y_{j}\\}$.

  2. (b)

For every $P_{i}$, we must have $P_{i}\ket{x_{j}}\propto\ket{y_{j}}$ for
$j=1,\ldots,4$.

To upper bound the sum Eq. S36, we consider six cases for the summands. We
simply need to count the number of nonzero summands, since the magnitude of
each of the summands is at most 1.

  1. I.

$P_{i}\in\mathbb{Z}_{n}$, where $\mathbb{Z}_{n}$ is the group generated by the
Pauli $\sigma^{z}$s. Then Constraint (b) amounts to $x_{j}=y_{j}$, and then
Constraint (a) is automatically satisfied. The sum then reads

$\sum_{P\in\mathbb{Z}_{n}}\sum_{\\{x_{j}\\}}\tr(P^{\otimes
4}\outerproduct{x_{1},x_{2},x_{3},x_{4}}{x_{1},x_{2},x_{3},x_{4}})=\sum_{P\in\mathbb{Z}_{n}}\tr(P^{\otimes
4})=1$ (S37)

(the only nonzero term is from the identity). For the remaining cases, we can
then assume $P_{i}\not\in\mathbb{Z}_{n}$, which amounts to assuming $x_{j}\neq
y_{j}$.

  2. II.

The $x_{j}$ are all the same ($x_{1}=x_{2}=x_{3}=x_{4}$). There are at most
$2^{n}$ choices for $\\{x_{j}\\}$ and $4^{n}$ choices for $P_{i}$, so $\leq
8^{n}$ summands that fall under this case.

  3. III.

Three of the $x_{j}$ are the same, and one is different. There are
$\binom{4}{3}=4$ ways to choose this triplet, and $4^{n}$ choices for
$\\{x_{j}\\}$ (with $4^{n}$ choices for $P_{i}$), amounting to at most $\leq
4\cdot 16^{n}$ nonzero summands.

  4. IV.

There are two distinct pairs amongst $x_{j}$ (for instance,
$(x_{1}=x_{3})\neq(x_{2}=x_{4})$). There are at most $\binom{4}{2}=6$ ways to
choose these pairings, and $4^{n}$ choices for $\\{x_{j}\\}$ after these
pairings are chosen (and at most $4^{n}$ choices for $P_{i}$). This case
represents $\leq 6\cdot 16^{n}$ nonzero summands.

  5. V.

Two of the $x_{j}$ are the same, and two are different. For concreteness, say
$x_{1}=x_{2}\neq x_{3}\neq x_{4}$. To satisfy Constraint (a), we must have
$(x_{3},x_{4})=(y_{3},y_{4})$ or $(x_{3},x_{4})=(y_{4},y_{3})$ (note we
automatically have $y_{1}=y_{2}$ by Constraint (b)). However, recalling that
$P_{i}\not\in\mathbb{Z}_{n}$ (hence $\ket{x_{j}}\perp\ket{y_{j}}$), we cannot
have $(x_{3},x_{4})=(y_{3},y_{4})$, and must, therefore, have
$(x_{3},x_{4})=(y_{4},y_{3})$. Combining this with Constraint (b), we get
$P_{i}\ket{x_{3}}\propto\ket{y_{3}}=\ket{x_{4}}$. Therefore, we only have
freedom in choosing one of $x_{1}$ or $x_{2}$, and in choosing $x_{3}$.
Generalizing this, we find a total of $\binom{4}{2}$ choices of pairings in
the $\\{x_{j}\\}$, $4^{n}$ choices for $\\{x_{j}\\}$, and $4^{n}$ choices for
$P_{i}$. This represents at most $6\cdot 16^{n}$ summands.

  6. VI.

All of the $x_{j}$ are unique. In this case, to satisfy Constraint (a), the
sum must look like

$\sum_{i,\\{x_{j}\\},\sigma\in\mathbb{S}_{4}}\tr(P_{i}^{\otimes
4}\ket{x_{1},x_{2},x_{3},x_{4}}\bra{x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)},x_{\sigma(4)}}),$
(S38)

where $\mathbb{S}_{4}$ is the group of permutations over $1,\ldots,4$.
Constraint (b) then reads $P_{i}\ket{x_{j}}=\ket{x_{\sigma(j)}}$. Applying
this twice, we have
$\ket{x_{j}}=P_{i}^{2}\ket{x_{j}}=\ket{x_{\sigma(\sigma(j))}}$, and since the
$\\{x_{j}\\}$ are unique, this implies $\sigma(\sigma(j))=j$ (i.e., $\sigma$
is an involution). Furthermore, since $\ket{x_{j}}\perp\ket{x_{\sigma(j)}}$
(by assumption that $P_{i}\not\in\mathbb{Z}_{n}$), $\sigma$ must act
nontrivially on each of $1,\ldots,4$. These two facts imply that $\sigma$ must
be a product of two disjoint two-cycles (e.g., it swaps $1\leftrightarrow 3$
and $2\leftrightarrow 4$). Therefore, we only have freedom in choosing two of
the $\\{x_{j}\\}$ (one for each of the two-cycles), and then the other two are
uniquely determined. To count the number of nonzero terms here, there are only
$3$ permutations $\sigma$ that are a product of disjoint two-cycles, at most
$4^{n}$ choices for $\\{x_{j}\\}$, and at most $4^{n}$ choices for $P_{i}$.
This amounts to $\leq 3\cdot 16^{n}$ nonzero summands.

In summary, we have at most $1+8^{n}+(3+6+4+6)\cdot 16^{n}\leq 20\cdot 16^{n}$
summands. Therefore,

${\mathbb{E}}_{f}\left[2^{-M_{2}({\psi_{f}})}\right]\leq\frac{20}{2^{n}}.$
(S39)

∎

Note that in the proof of 5, the only property of $f$ that we have used has
been in Constraint (a). This constraint holds so long as $f$ is 8-wise
independent, and does not require $f$ to be completely random. We can
construct pseudorandom 8-wise independent functions as follows. We randomly
choose $h$ from the 8-wise independent family

$H=\\{h\mid\\{0,1\\}^{n}\to\\{0,1\\}\\},$ (S40)

and $q$ from a family of quantum-secure permutations

$Q=\\{q\mid\\{0,1\\}^{n}\to\\{0,1\\}^{n}\\}.$ (S41)

Then, defining $f\coloneqq h\circ q$, $f$ is both pseudorandom and 8-wise
independent. This has been proven in full detail in Ref. [31]. This gives us
the following theorem.

######  Theorem S2 (Tight bounds on the stabilizer entropies of subset phase
states).

Let $\omega(\log n)\leq k\leq n$ and $\absolutevalue{S}=2^{k}$. If $f$ is
sampled from the ensemble of 8-wise independent pseudorandom functions, then
the associated subset phase states satisfy

$M_{\alpha}({\psi_{f,S}})=\Theta(k)$ (S42)

with high probability for any $\alpha\in[0,2]$.

###### Proof.

The upper bound follows from 1. For the lower bound, we focus on the case
$\alpha=2$, and define

$Z_{f}\coloneqq-\log(M_{2}(\ket{\psi_{f,S}}))=\frac{1}{2^{n}}\sum_{P\in\mathbb{P}_{n}}\tr(P^{\otimes
4}\outerproduct{\psi_{f,S}}{\psi_{f,S}}^{\otimes 4}),$ (S43)

for an arbitrary fixed subset $S$ (with $\absolutevalue{S}=2^{k}$). Our goal
will be to show that

$\mathbb{E}_{f}[Z_{f}]=O(\absolutevalue{S}^{-1}),$ (S44)

regardless of the choice of subset $S$. In general, do this by mirroring the
techniques of 5. However, handling Constraint I. requires some special care.
We will show that

$\frac{1}{\absolutevalue{S}^{4}2^{n}}\sum_{P_{Z}\in\mathbb{Z}_{n}}\left(\sum_{x\in
S}\tr(P\outerproduct{x}{x})\right)^{4}=O(\absolutevalue{S}^{-1})$ (S45)

We represent $P_{Z}\in\mathbb{Z}_{n}$ as a bitstring $z$, where $z_{i}=1$ if
$P$ has a $Z$ on the $i$th position, so the sum over $P_{Z}\in\mathbb{Z}_{n}$
then turns into a sum over all $z\in\\{0,1\\}^{n}$ We also then have
$g_{z}(x)\coloneqq\tr(P\outerproduct{x}{x})=(-1)^{x\cdot z}$, where $x\cdot z$
is shorthand for $\sum x_{i}z_{i}$. By expanding out the fourth power of the
sum over $x\in S$, we will get a collection of terms
$g_{z}(x_{i})g_{z}(x_{j})g_{z}(x_{k})g_{z}(x_{l})$, which can be simplified to
simply $g_{z}(x_{i}+x_{j}+x_{k}+x_{l})$, where the addition is mod 2. Then, we
note that when we take the sum over all $z\in\\{0,1\\}^{n}$, this term
averages to zero, unless $x_{i}+x_{j}+x_{k}+x_{l}=0^{n}$ (i.e., a string of
all zeros). In order for this requirement to hold, we see that we have at most
$O(\absolutevalue{S}^{3})$ choices for $x_{i},x_{j},x_{k}$, after which
$x_{l}$ is uniquely determined. In summary, there are at most
$O(\absolutevalue{S}^{3})$ terms that do not sum to zero, and so we have shown
Eq. S45.

The remaining cases are simple. Since Constraints (a) and (b) still hold, we
can run through Constraints II. to VI. of 5 making adjustments as needed. The
main adjustment is that instead of $4^{n}$ choices for $P_{i}$, there are
$2^{n}\absolutevalue{S}$ choices. The reasoning for this follows that of 4:
picking a $P_{i}$, is equivalent to picking a $P_{X}\in\mathbb{X}_{n}$ and a
$P_{Z}\in\mathbb{Z}_{n}$. There are at most $2^{n}$ choices for $P_{Z}$, and
only $\absolutevalue{S}$ choices for $P_{X}$, since there are at most
$\absolutevalue{S}$ different bitstrings to which we can flip to when we are
working with subset phase states. For Constraint II., there are
$\absolutevalue{S}$ choices for $\\{x_{j}\\}$, and for each of these choices,
there are at most $\absolutevalue{S}2^{n}$ choices of $P_{i}$ so that all of
the corresponding $\\{y_{i}\\}$ belongs to $S$. For Constraints III. to VI.,
there are $\absolutevalue{S}^{2}$ choices for $\\{x_{j}\\}$ and
$\absolutevalue{S}2^{n}$ choices for $P_{i}$. Therefore, we have that

$Z=\frac{1}{2^{n}}\sum_{i}\left(P_{i}^{\otimes
4}{\mathbb{E}}\left[\outerproduct{\psi_{f,S}}{\psi_{f,S}}^{\otimes
4}\right]\right)\leq\underbrace{O\left(\frac{1}{\absolutevalue{S}}\right)}_{\textrm{\lx@cref{creftypecap~refnum}{itm:sum1}}}+\underbrace{\frac{\absolutevalue{S}^{2}2^{n}+(3+6+4+6)\cdot\absolutevalue{S}^{3}2^{n}}{2^{n}\absolutevalue{S}^{4}}}_{\textrm{\lx@cref{creftypepluralcap~{}refnum}{itm:sum2}
to~\ref{itm:sum6}}}\leq O\left(\frac{1}{\absolutevalue{S}}\right).$ (S46)

For this reason, there must be some $N_{0}$ for which $N\geq N_{0}\implies
Z\leq\frac{1}{\sqrt{\absolutevalue{S}}}=2^{-k/2}$. By virtue of Markov’s
inequality, we find

${\mathsf{Pr}}_{f}\left[Z_{f}\geq 2^{-k/4}\right]\leq 2^{-k/4},$ (S47)

and it follows that

${\mathsf{Pr}}_{\ket{\psi}_{f,S}}\left[M_{2}({\psi_{f,S}})\leq\frac{k}{4}\right]\leq
2^{-k/4}.$ (S48)

As an immediate corollary, when $f$ is sampled from the ensemble of $8$-wise
independent pseudorandom functions, $M_{\alpha}({\psi_{f,S}})=\Theta(k)$ with
high probability for any $\alpha\in[0,2]$. ∎

###  II.4 Robustness of magic as a pseudomagic measure

Recall the definition of the log-robustness of magic $\mathcal{R}({\rho})$ as

$\mathcal{R}({\rho})\coloneqq\log\min\left\\{\norm{c}_{1}\big{|}\
\rho=\sum_{\ket{\sigma}\in\Sigma}c_{\sigma}\outerproduct{\sigma}{\sigma}\right\\}.$
(S49)

Note that this definition of $\mathcal{R}({\rho})$ is the logarithm of the
conventional definition given in Ref. [85].

######  Theorem S3 (Robustness of subset phase states).

The robustness of subset phase states satisfies, with high probability over
the ensemble

$\mathcal{R}({\psi_{f,S}})=\Theta(\log\absolutevalue{S}).$ (S50)

Moreover, we can state a more precise upper bound
$\mathcal{R}(\psi_{f,S})\leq\log\absolutevalue{S}$.

###### Proof.

The lower bound follows from combining 2 with the fact that the robustness of
magic is lower bounded by $M_{2}$ to get $\mathcal{R}({\psi_{k}})\geq
M_{2}(\psi_{k})=\Theta(\log\absolutevalue{S})$. We will now prove the upper
bound by bounding the robustness of $\outerproduct{\psi_{f,S}}{\psi_{f,S}}$.
First, note that

$\outerproduct{\psi_{f,S}}{\psi_{f,S}}=\frac{1}{\absolutevalue{S}}\sum_{i,j}(-1)^{f(x_{i})+f(x_{j})}\outerproduct{x_{i}}{x_{j}}=\frac{1}{\absolutevalue{S}}\sum_{i}\outerproduct{x_{i}}{x_{i}}+\frac{1}{\absolutevalue{S}}\sum_{i=1}^{\absolutevalue{S}}\sum_{j=i+1}^{\absolutevalue{S}}(-1)^{f(x_{i})+f(x_{j})}(\outerproduct{x_{i}}{x_{j}}+c.c.).$
(S51)

Now, we have that $\outerproduct{x_{i}}{x_{i}}$ are stabilizer states for
every $x_{i}\in S$ and that

$\outerproduct{x_{i}}{x_{j}}+c.c=\left(\frac{\ket{x_{i}}+\ket{x_{j}}}{\sqrt{2}}\right)\left(\frac{\bra{x_{i}}+\bra{x_{j}}}{\sqrt{2}}\right)-\left(\frac{\ket{x_{i}}-\ket{x_{j}}}{\sqrt{2}}\right)\left(\frac{\bra{x_{i}}-\bra{x_{j}}}{\sqrt{2}}\right)\eqqcolon\sigma_{i,j}^{+}-\sigma_{i,j}^{-},$
(S52)

where $\sigma_{i,j}^{\pm}$ are stabilizer states. Therefore, we can express
the density matrix for phase states

$\outerproduct{\psi_{f,S}}{\psi_{f,S}}=\frac{1}{\absolutevalue{S}}\sum_{i}\outerproduct{x_{i}}{x_{i}}+\frac{1}{\absolutevalue{S}}\sum_{i=1}^{\absolutevalue{S}}\sum_{j=i+1}^{\absolutevalue{S}}(-1)^{f(x_{i})+f(x_{j})}(\sigma_{i,j}^{+}-\sigma_{i,j}^{-}).$
(S53)

From the above expression we can easily upper bound the robustness of magic as

$\mathcal{R}(\psi_{f,S})\leq\log\left(\frac{\absolutevalue{S}}{\absolutevalue{S}}+\frac{2}{\absolutevalue{S}}\sum_{i=1}^{\absolutevalue{S}}\sum_{j=i+1}^{\absolutevalue{S}}1\right)=\log\left(1+\frac{2}{\absolutevalue{S}}\frac{\absolutevalue{S}(\absolutevalue{S}-1)}{2}\right)=\log\absolutevalue{S}.$
(S54)

∎

######  Corollary S2 (Robustness of magic as a pseudomagic measure).

The robustness of magic is a good candidate for defining the notion of
pseudomagic.

###  II.5 Sufficient conditions for pseudomagic measures

We first show that a sufficient criterion for a magic measure $\mathcal{M}$ to
be a good pseudomagic measure is that $\mathcal{M}$ is lower bounded by a
stabilizer entropy and upper bounded by the robustness of magic.

######  Theorem S4 (Sufficient conditions for bounded good pseudomagic
measures).

Let $\mathcal{M}({\psi})$ be a magic monotone for pure states. Then, if
$\mathcal{M}({\psi})$ is bounded as
$\Omega(M_{\alpha}({\psi}))\leq\mathcal{M}({\psi})\leq O(\mathcal{R}({\psi}))$
for some constant $\alpha$, then $(i)$ $\mathcal{M}=\omega(\log n)$ for any
ensemble of pseudorandom states; $(ii)$ $\mathcal{M}$ is a measure of
pseudomagic with maximum gap $\Omega(n)$ vs. $O(\operatorname{poly}\log n)$.

###### Proof.

From Lemma 1, we have that for every ensemble of pseudorandom states
$\mathcal{E}$, $\mathcal{M}({\psi_{k}})=\omega(\log n)$ with high probability
over the choice of $\ket{\psi_{k}}\in\mathcal{E}$. From 3, we have that for
pseudorandom subset phase states
$\mathcal{M}({\psi_{k}})=O(\log\absolutevalue{S})$ and thus for
$\absolutevalue{S}=2^{O(\operatorname{poly}\log n)}$,
$\mathcal{M}({\psi_{k}})=O(\operatorname{poly}\log n)$, satisfying the
definition of pseudomagic. ∎

Then, we have the following two corollaries that readily follow from 4.

######  Corollary S3 (Stabilizer fidelity, stabilizer extent, and max-relative
entropy).

Each of the following magic measures fulfill the conditions in the definition
of pseudomagic, hence they can be considered good pseudomagic measures with
gap $\Theta(n)$ vs. $\Theta(\operatorname{poly}\log n)$.

  1. (i)

the stabilizer fidelity
$\mathcal{F}_{\mathrm{stab}}({\psi})\coloneqq-\log\max_{\ket{\sigma}\in\Sigma}\absolutevalue{\innerproduct{\sigma}{\psi}}^{2}$,

  2. (ii)

stabilizer extent
$\xi({\psi})\coloneqq\log\min\left\\{\sum_{\phi}\absolutevalue{c_{\phi}}^{2}\mid\ket{\psi}=\sum_{\ket{\phi}\in\Sigma}c_{\phi}\ket{\phi}\right\\}$,
and

  3. (iii)

the max relative entropy of magic
$D_{\max}(\ket{\psi})=\log\min\\{\lambda\mid\lambda\sigma-\psi\geq 0\\}$,
where $A\geq 0$ means $A$ is positive semidefinite (when $A$ is a matrix).

###### Proof.

These magic measures obey bounds with respect to the stabilizer Rényi entropy
$M_{2}$ and the robustness of magic $\mathcal{R}$ that have already been
established.

$\frac{1}{4}M_{2}(\psi)<\mathcal{F}_{\textrm{stab}}(\psi)\leq\xi(\psi),D_{\textrm{max}}(\psi)\leq\mathcal{R}(\psi),$
(S55)

where the first inequality was shown in Ref. [35] and the last two were shown
in Ref. [87]. The tightness of the gap $\Theta(n)$ vs.
$\Theta(\operatorname{poly}\log n)$ (as opposed to $\Omega(n)$ vs.
$O(\operatorname{poly}\log n)$) is due to the fact that when $\psi$ is a
pseudorandom subset phase state, we have already shown that
$M_{2}(\psi)=\Theta(\log\absolutevalue{S})$ in 2 and
$\mathcal{R}(\psi)=\Theta(\log\absolutevalue{S})$ in 3. Furthermore, we know
$M_{2}(\psi)=\Omega(n)$ and $\mathcal{R}(\psi)=\Omega(n)$ for Haar random
states, but since both of these measures are upper bounded by $n+o(1)$
anyways, they can trivially be rewritten $M_{2}(\psi)=\Theta(n)$ and
$\mathcal{R}(\psi)=\Theta(n)$. ∎

###  II.6 Stabilizer nullity is a poor candidate to define pseudomagic

In this section, we show that the stabilizer nullity is a poor candidate to
define pseudomagic. More precisely, we show that pseudorandom states must
necessarily have maximal stabilizer nullity, mirroring the behavior observed
in Haar-random states. To start, we formally define stabilizer nullity, first
introduced in Ref. [69] (see also Ref. [90]). Following the notation of Ref.
[91], for any $\ket{\psi}$, one can associate a subset $G_{\psi}$ of the Pauli
group $\mathbb{P}_{n}$ comprised of Pauli operators that have unit expectation
value on $\psi$:

$G_{\psi}\coloneqq\\{P\in\mathbb{P}_{n}\mid\tr(P\psi)=\pm 1\\}.$ (S56)

It is easy to show that $G_{\psi}$ is a group [90], so we say $G_{\psi}$ is
the _stabilizer group_ associated with the state $\psi$. For stabilizer states
$\sigma$, the cardinality of $G_{\sigma}$ is maximal: $|G_{\sigma}|=d$.
Conversely, for non stabilizer states $\psi$ one has $|G_{\psi}|<d$.
Therefore, one can define a magic measure called the _stabilizer nullity_

$\nu(\psi)\coloneqq n-\log\absolutevalue{G_{\psi}}.$ (S57)

We are now ready to present the outcome of this section, contained in the
following lemma.

######  Lemma S6.

Any ensemble $\mathcal{E}=\\{\ket{\psi_{k}}\\}$ of computationally
pseudorandom quantum states must obey $\nu(\psi_{k})=n$ with high probability
over $k$.

###### Proof.

The proof of this lemma follows easily from the fundamental results of Ref.
[92]: it shows that an ensemble of pseudorandom quantum states $\mathcal{E}$
must feature $|G_{\psi_{k}}|=1$ with high probability over the choice of $k$.
The proof is based on two key facts: $(i)$ Haar random states obey
$\log\absolutevalue{G_{\psi}}=0$ with overwhelming probability; $(ii)$ the
construction of an efficient algorithm that is able to discriminate whether
$\log\absolutevalue{G_{\psi_{k}}}>1$ or $\log\absolutevalue{G_{\psi_{k}}}=1$.
A simple corollary is that the stabilizer nullity for the ensemble
$\mathcal{E}$ of pseudorandom states is $\nu(\psi_{k})=n$ with high
probability over the choice of $k$. ∎

This lemma tells us that the stabilizer nullity is unlikely to be a suitable
magic measure for defining pseudomagic, as no ensemble of pseudorandom quantum
states can exhibit a nonzero gap in stabilizer nullity compared to Haar-random
states. Nevertheless, due to the generality of the definition for psedomagic
compared to pseudorandom states, the possibility remains open that there are
pseudomagic states, which do not meet the criteria of computational
pseudorandomness, yet exhibit a substantial pseudomagic gap. This remains an
open question for future investigations.

Beyond this, 6 has broader implications for the relationship between
stabilizer nullity and other magic measures (particularly, the robustness of
magic). 3 establishes a sufficient condition for magic monotones $\mathcal{M}$
to exhibit a substantial pseudomagic gap, assuming that $\mathcal{M}$ is
bounded by a certain stabilizer entropy $M_{\alpha}$ and the robustness
$\mathcal{R}$. As mentioned in SM I, the stabilizer nullity is lower bounded
by $M_{\alpha}(\psi)\leq\nu(\psi)$ for any $\alpha$. On the other hand, there
exists no known corresponding upper bound involving the robustness of magic.
Notably, simply by combining 3 and 6, we arrive at the following corollary,
which rules out the possibility of having any upper bound on the stabilizer
nullity in terms of the robustness of magic.

######  Corollary S4.

Let $\nu(\psi)$ be the stabilizer nullity and $\mathcal{R}(\psi)$ be the
robustness of magic defined in Table 1 of the main text. Then, there is no
constant $a$ such that $\nu(\psi)\leq a\mathcal{R}(\psi)$ for every state
$\psi$.

## Supplemental Material III: The continuity of pseudorandomness

######  Lemma S7 (Indistinguishability of ensembles).

For any two ensembles of states $\mathcal{E}\coloneqq\\{\psi_{k}\\}$ and
$\mathcal{E}^{\prime}\coloneqq\\{\phi_{k}\\}$, if

${\mathsf{TV}}(\psi_{k},\phi_{k})<o\left(\frac{1}{\operatorname{poly}n}\right)$
(S58)

for all $k$, then $\mathcal{E}$ and $\mathcal{E}^{\prime}$ are statistically
(hence computationally) indistinguishable.

###### Proof.

This follows from the fact that for any $t=O(\operatorname{poly}n)$,
${\mathsf{TV}}(\psi_{k}^{\otimes t},\phi_{k}^{\otimes t})\leq
t\cdot{\mathsf{TV}}(\psi_{k},\phi_{k})<o\left(\frac{1}{\operatorname{poly}n}\right)$.
Then by a simple triangle inequality,

${\mathsf{TV}}\left({\mathbb{E}}_{\psi_{k}\sim\mathcal{E}}[\outerproduct{\psi_{k}}{\psi_{k}}^{\otimes
t}],{\mathbb{E}}_{\phi_{k}\sim\mathcal{E}}[\outerproduct{\phi_{k}}{\phi_{k}}^{\otimes
t}]\right)\leq{\mathbb{E}}\left[{\mathsf{TV}}(\outerproduct{\psi_{k}}{\psi_{k}}^{\otimes
t},\outerproduct{\phi_{k}}{\phi_{k}}^{\otimes
t})\right]<o\left(\frac{1}{\operatorname{poly}n}\right).$ (S59)

∎

######  Lemma S8 (Transitivity of computational indistinguishability).

For any ensembles $\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}$, if
$\mathcal{E}_{1}\cong\mathcal{E}_{2}$ and
$\mathcal{E}_{2}\cong\mathcal{E}_{3}$ (where $\cong$ denotes computational
indistiguishability), then $\mathcal{E}_{1}\cong\mathcal{E}_{3}$.

###### Proof.

This follows from a simple triangle inequality. For any efficient algorithm
$\mathcal{A}$ and any $t=O(\operatorname{poly}n)$,

$\begin{gathered}\absolutevalue{{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{1}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]-{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{3}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]}\\\
\leq\absolutevalue{{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{1}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]-{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{2}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]}+\absolutevalue{{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{2}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]-{\mathsf{Pr}}_{\psi_{k}\sim\mathcal{E}_{3}}[\mathcal{A}\big{(}\ket{\psi_{k}}^{\otimes
t}\big{)}=1]}\\\ \leq{\mathsf{negl}}(n).\end{gathered}$ (S60)

∎

Combining 7 and 8 allows us to conclude that the pseudorandomness of an
ensemble is robust to to small state preparation errors. More precisely, if we
have a target ensemble of pseudorandom states $\mathcal{E}=\\{\psi_{k}\\}$,
but over the course of preparing these states, we make small errors such that
the resulting ensemble $\mathcal{E}^{\prime}=\\{\psi_{k}^{\prime}\\}$
satisfies

${\mathsf{TV}}(\psi_{k},\psi_{k}^{\prime})<o\left(\frac{1}{\operatorname{poly}n}\right),$
(S61)

for all $k$, then $\mathcal{E}^{\prime}$ is still pseudorandom. This is
because 7 guarantees $\mathcal{E}\cong\mathcal{E}^{\prime}$, which, combined
with 8, tells us
$\mathcal{E}\cong\operatorname{Haar}\implies\mathcal{E}^{\prime}\cong\operatorname{Haar}$.

## Supplemental Material IV: Quantum chaos: Proof of Theorem 2

######  Definition S3 (Quantum chaos).

Consider a unitary $U$. Its $2k$-point out-of-time-order correlators (OTOCs)
[48, 49] are

$C_{2k}(U)\coloneqq\frac{1}{d}\tr(\tilde{P}_{1}Q_{1}\tilde{P}_{2}Q_{2}\cdots\tilde{P}_{k}Q_{k}),$
(S62)

where $P_{i}$ and $Q_{i}$ are non-identity Pauli operators for $i=1,\ldots,k$
and $\tilde{P}_{i}\coloneqq U^{{\dagger}}P_{i}U$. We say $U$ is chaotic if

$C_{2k}(U)=\tilde{O}(C_{2k}(U_{\operatorname{Haar}})),$ (S63)

where $\tilde{O}$ stands for an irrelevant _polynomial overhead_ , and
$C_{2k}(U_{\operatorname{Haar}})$ is the average of the $2k$-point OTOCs over
Haar random unitaries.

######  Theorem S5 (Exponential separation from Haar values).

Let $\mathcal{E}$ be an ensemble of pseudomagic states. Let
$\ket{\psi}\in\mathcal{E}$ and let $U$ such that $\ket{\psi}=U\ket{0}^{\otimes
n}$. Then there exists $2k$-point OTOCs that are exponentially separated from
the Haar value as

$C_{2k}(U)=\Omega(\exp(n)C_{2k}(U_{\operatorname{Haar}}))$ (S64)

and thus $U$ cannot be considered chaotic by 3.

###### Proof.

The proof will be constructive. We simply construct a $2k$-point OTOC that
exhibits exponential separation from the Haar average value. Let $U$ and
$\ket{\psi_{U}}$ be unitary and state vector such that
$\ket{\psi_{U}}=U\ket{0}^{\otimes n}$. Consider the $\alpha$-stabilizer
entropy $M_{\alpha}(\psi_{U})$ with integer $\alpha>1$

$M_{\alpha}({\psi_{U}})=\frac{1}{1-\alpha}\log\frac{1}{d}\sum_{P\in\mathbb{P}_{n}}\tr^{2\alpha}(\tilde{P}\outerproduct{0}{0}^{\otimes
n})$ (S65)

where $\tilde{P}\coloneqq U^{{\dagger}}PU$. Let us exploit the fact that
$\outerproduct{0}{0}^{\otimes n}$ is pure to write
$\tr^{2}(\tilde{P}\outerproduct{0}{0}^{\otimes
n})=\tr(\tilde{P}\outerproduct{0}{0}^{\otimes
n}\tilde{P}\outerproduct{0}{0}^{\otimes n})$ multiple times. Expanding
$\outerproduct{0}{0}^{\otimes n}$ in terms of Pauli operators as
$\outerproduct{0}{0}^{\otimes n}=d^{-1}\sum_{Z\in\mathbb{Z}_{n}}Z$ with
$\mathbb{Z}_{n}$ the commuting subgroup of the Pauli group generated by
single-qubit Pauli-$Z$s, we write

$M_{\alpha}({\psi_{U}})=\frac{1}{1-\alpha}\log\frac{1}{d^{2\alpha+1}}\sum_{P,Z_{1},\ldots,Z_{2\alpha}}\tr(\tilde{P}Z_{1}\tilde{P}Z_{2}\cdots\tilde{P}Z_{2\alpha}).$
(S66)

Now, let us denote by brackets
$\langle\cdot\rangle_{\mathbb{P}_{n},\mathbb{Z}_{n}}$ the group average with
respect to the whole Pauli group $\mathbb{P}_{n}$ and the subgroup
$\mathbb{Z}_{n}$. Noting that $C_{4\alpha}(U,P,Z_{i})\coloneqq
d^{-1}\tr(\tilde{P}Z_{1}\tilde{P}Z_{2}\cdots\tilde{P}Z_{2\alpha})$ is a
$4\alpha$-point OTOC, let us define $C_{4\alpha}(U)\coloneqq\langle
C_{4\alpha}(U,P,Z_{i})\rangle_{\mathbb{P}_{n},\mathbb{Z}_{n}}$ the averaged
$4\alpha$ point OTOC. We can thus express the stabilizer entropy in terms of a
single out of time ordered correlation function

$M_{\alpha}({\psi_{U}})=\frac{1}{1-\alpha}\log d^{2}C_{4\alpha}(U).$ (S67)

Now we are finally ready to show the main result. Let $\ket{\psi_{PM}}$ be a
pseudomagic state satisfying $M_{\alpha}({\psi_{PM}})=o(n)$ (the subset phase
states with $\absolutevalue{S}=O(\exp\operatorname{poly}\log n)$ easily
accomplish this). Let $\ket{\psi_{\operatorname{Haar}}}$ be a Haar random
state. With overwhelming probability, one has
$M_{\alpha}({\psi_{\operatorname{Haar}}})=\Omega(n/\alpha)$. Let us consider
the difference

$M_{\alpha}({\psi_{\operatorname{Haar}}})-M_{\alpha}({\psi_{PM}})=\Omega(n/\alpha).$
(S68)

Denoting $U_{PM}$ the unitary that constructs
$\ket{\psi_{PM}}=U_{PM}\ket{0}^{\otimes n}$ and $U_{\operatorname{Haar}}$ the
equivalent for $\ket{\psi_{\operatorname{Haar}}}$, we readily get

$C_{4\alpha}(U_{PM})=\Omega(\exp(n)C_{4\alpha}(U_{\operatorname{Haar}})).$
(S69)

Defining $2k=4\alpha$ proves the statement. ∎

## Supplemental Material V: Fannes inequality for $M_{1}$ and cryptography
from pseudomagic: Proof of Theorem 3

Informally speaking, an EFI pair is a pair of efficient quantum algorithms
whose output states are statistically far but computationally
indistinguishable.

######  Definition S4 (EFI pairs [33]).

We call $\mu\coloneqq\left(\mu_{b,\lambda}\right)$ a pair of EFI states if it
satisfies the following criteria:

  * •

_Efficient generation_ : There exists a uniform QPT quantum algorithm $A$ that
on input $\left(1^{\lambda},b\right)$ for some integer $\lambda$ and
$b\in\\{0,1\\}$, outputs the mixed state $\mu_{b,\lambda}$.

  * •

_Statistically distinguishable_ :
${\mathsf{TV}}\left(\mu_{0,\lambda},\mu_{1,\lambda}\right)\geq\Omega(\frac{1}{\operatorname{poly}\lambda})$.

  * •

_Computational indistinguishability_ :
$\left(\mu_{0,\lambda}\right)_{\lambda}$ is computationally indistinguishable
to $\left(\mu_{1,\lambda}\right)_{\lambda}$.

We will now show that pseudomagic ensembles imply EFI pairs. A critical
ingredient in this proof will be a Fannes-type inequality which establishes
for stabilizer entropy what the Fannes-Audenaert inequality establishes for
entropy – namely its continuity in the space of states over the metric of
trace distance. We now prove such an inequality for $M_{1}$. Since this proof
is of independent interest, we devote a separate section to it before we prove
the implication about EFI pairs.

###  V.1 A Fannes Inequality for the Stabilizer Shannon Entropy

Recall from Eq. S3 that $M_{1}$ can be written

$M_{1}(\psi)=-\sum_{P\in\mathbb{P}_{n}}\frac{\tr^{2}(P\psi)}{d}\log\tr^{2}(P\psi).$
(S70)

######  Theorem S6 (Fannes-like inequality for $M_{1}$ (also to appear in Ref.
[89])).

For any two states $\ket{\psi}$ and $\ket{\phi}$, it holds that

$\absolutevalue{M_{1}(\psi)-M_{1}(\phi)}\leq\begin{cases}\norm{\psi-\phi}_{1}\log(d^{2}-1)+H_{\textrm{bin}}[\norm{\psi-\phi}_{1}]&\text{for
$\norm{\psi-\phi}_{1}\leq 1/2$},\\\
\norm{\psi-\phi}_{1}\log(d^{2}-1)+1&\text{for $\norm{\psi-\phi}_{1}>1/2$.}\\\
\end{cases}$ (S71)

###### Proof.

We make use of two main ingredients

  * •

Consider a state vector $\ket{\psi}$ and its conjugate (in the computational
basis) denoted as $\ket{\psi^{*}}$ and defined as
$\ket{\psi^{*}}=\sum_{i}\innerproduct{i}{\psi}^{*}\ket{i}$. Define
$\ket{P}:=I\otimes P\ket{I}$ where
$\ket{I}=\frac{1}{\sqrt{d}}\sum_{i}\ket{i}\otimes\ket{i}$ the Bell state. Note
that $\\{\ket{P}\\}$ is a basis for the Hilbert space $\mathcal{H}^{\otimes
2}$. The dephased state vector $\ket{\psi}\otimes\ket{\psi^{*}}$ (which we
denote $\ket{\psi\otimes\psi^{*}}$ for short) in the basis $\ket{P}$ equals

$\mathcal{D}_{P}(\psi\otimes\psi^{*}):=\sum_{P}\outerproduct{P}{P}\psi\otimes\psi^{*}\outerproduct{P}{P}=\sum_{P}\frac{\tr^{2}(P\psi)}{d}\outerproduct{P}{P}$
(S72)

indeed
$\matrixelement{P}{\psi\otimes\psi^{*}}{P}=\absolutevalue{\innerproduct{\psi\otimes\psi^{*}}{P}}^{2}$.
And

$\innerproduct{\psi\otimes\psi^{*}}{P}=\frac{1}{\sqrt{d}}\sum_{i}\innerproduct{\psi^{*}}{i}\matrixelement{\psi}{P}{i}=\frac{1}{\sqrt{d}}\sum_{i}\matrixelement{\psi}{P}{i}\innerproduct{i}{\psi}=\frac{\matrixelement{\psi}{P}{\psi}}{\sqrt{d}}.$
(S73)

  * •

Moreover, let us show that
$\norm{\psi\otimes\psi^{*}-\phi\otimes\phi^{*}}_{1}=\norm{\psi^{\otimes
2}-\phi^{\otimes 2}}_{1}$. To see this, note that

$\norm{\psi\otimes\psi^{*}-\phi\otimes\phi^{*}}_{1}=2\sqrt{1-\tr(\psi\otimes\psi^{*}\phi\otimes\phi^{*})}=2\sqrt{1-\tr(\psi\phi)\tr(\psi^{*}\phi^{*})}$
(S74)

then consider
$\tr(\psi^{*}\phi^{*})=\absolutevalue{\innerproduct{\psi^{*}}{\phi^{*}}}^{2}$
and write it in the computational basis

$\innerproduct{\psi^{*}}{\phi^{*}}=\sum_{i}\innerproduct{\psi^{*}}{i}\innerproduct{i}{\phi^{*}}=\sum_{i}\innerproduct{\phi}{i}\innerproduct{i}{\psi}=\innerproduct{\phi}{\psi}$
(S75)

which implies $\tr(\psi^{*}\phi^{*})=\tr(\psi\phi)$. We used the definition of
conjugate state, i.e.
$\ket{\psi^{*}}=\sum_{i}(\innerproduct{i}{\psi})^{*}\ket{i}\equiv\sum_{i}\innerproduct{\psi}{i}\ket{i}$.
Returning to the $1$-norm distance, we have

$\norm{\psi\otimes\psi^{*}-\phi\otimes\phi^{*}}_{1}=2\sqrt{1-\tr(\psi\phi)\tr(\psi^{*}\phi^{*})}=2\sqrt{1-\tr^{2}(\psi\phi)}=\norm{\psi^{\otimes
2}-\phi^{\otimes 2}}_{1}.$ (S76)

Consider now two pure states $\psi,\phi$ and the Shannon entropies
$S(\Xi_{\psi}),S(\Xi_{\phi})$ of the (purely classical) probability
distributions $\Xi_{\psi}(P),\Xi_{\phi}(P)$. The classical _Fannes-Audenaert
inequality_ for the Shannon entropy tells us

$\absolutevalue{S(\Xi_{\psi})-S(\Xi_{\phi})}\leq{\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})\log(d^{2}-1)+H_{\rm
bin}[{\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})],$ (S77)

where
${\mathsf{TV}}(\mathbf{p},\mathbf{q})\coloneqq\frac{1}{2}\sum_{i}\absolutevalue{p_{i}-q_{i}}$
is the total variation distance between two probability distributions, and
$H_{\rm bin}[x]$ is the binary entropy function $H_{\rm
bin}[\epsilon]=-\epsilon\log\epsilon-(1-\epsilon)\log(1-\epsilon)$. Consider
the state in Eq. S72 and notice that

${\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})=\frac{1}{2}\sum_{P}\absolutevalue{\Xi_{\psi}(P)-\Xi_{\phi}(P)}=\frac{1}{2}\norm{\mathcal{D}_{P}(\psi\otimes\psi^{*})-\mathcal{D}_{P}(\phi\otimes\phi^{*})}_{1}$
(S78)

simply represents the distance between the dephased states in the Bell basis.
We can now combine Eq. S76 with the fact that the $1$-norm is non-increasing
under any quantum channel (in this case, $\mathcal{D}_{P}$) to bound

${\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})\leq\frac{1}{2}\norm{\psi^{\otimes
2}-\phi^{\otimes 2}}_{1}\leq\norm{\psi-\phi}_{1}.$ (S79)

Assuming that $\norm{\psi-\phi}_{1}\leq 1/2$ then
${\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})\leq 1/2$ and we have that $H_{\rm bin}$
is monotonic and we can write $H_{\rm
bin}({\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi}))\leq H_{\rm
bin}(\norm{\psi-\phi}_{1})$ and thus we can write

$\absolutevalue{M_{1}(\psi)-M_{1}(\phi)}\leq\norm{\psi-\phi}_{1}\log(d^{2}-1)+H_{\rm
bin}[\norm{\psi-\phi}_{1}].$ (S80)

Otherwise, if $\norm{\psi-\phi}_{1}>1/2$, we can bound $H_{\rm
bin}({\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi}))\leq 1$

$\absolutevalue{M_{1}(\ket{\psi})-M_{1}(\ket{\phi})}\leq\norm{\psi-\phi}_{1}\log(d^{2}-1)+1.$
(S81)

∎

Following an identical technique to the above theorem, we can prove a much
looser bound for higher $\alpha$.

######  Corollary S5 (Fannes-like inequality for $M_{\alpha>1}$).

For any $\alpha>1$ and any two state vectors $\ket{\phi}$ and $\ket{\psi}$,

$\absolutevalue{M_{\alpha}(\psi)-M_{\alpha}(\phi)}\leq\frac{d^{2}\alpha}{\alpha-1}\norm{\psi-\phi}_{1}.$
(S82)

###### Proof.

There are analogies to the Fannes-Audenaert inequality in Eq. S77 for
classical Rényi entropies. In Eq. (20) of Ref. [93], it is shown that

$\absolutevalue{S_{\alpha}(\mathbf{p})-S_{\alpha}(\mathbf{q})}\leq\dim(\mathbf{p})\cdot\frac{\alpha}{\alpha-1}{\mathsf{TV}}(\mathbf{p},\mathbf{q}),$
(S83)

for any $\alpha>1$ and any classical distributions $\mathbf{p},\mathbf{q}$
defined over $\dim(\mathbf{p})$ elements. In our case, this simply means

$\absolutevalue{S_{\alpha}(\Xi_{\psi})-S_{\alpha}(\Xi_{\phi})}\leq\frac{d^{2}\alpha}{\alpha-1}{\mathsf{TV}}(\Xi_{\psi},\Xi_{\phi})\leq\frac{d^{2}\alpha}{\alpha-1}\norm{\psi-\phi}_{1},$
(S84)

where the factor $d^{2}$ is because the classical distributions
$\Xi_{\psi},\Xi_{\phi}$ are defined over all $d^{2}$ Pauli matrices. The
second inequality follows from Eq. S79. ∎

###  V.2 Proof of Theorem 3

######  Theorem S7 (EFI pairs from pseudo-magic ensembles (Theorem 3,
repeated)).

Efficiently-generatable pseudo-magic ensembles with stabilizer 1-entropy that
can be tuned between $\omega(\log n)$ and $n$ imply EFI pairs. Namely, we
consider as the pair an algorithm that generates a random pseudo-magic state
with magic of $\operatorname{poly}\log n$, and one that generates a random
pseudo-magic state with magic of $n$.

###### Proof.

By a triangle inequality (since both ensembles are computationally
indistinguishable from a Haar-random state), the outputs of these two
algorithms are computationally indistinguishable from each other. It remains
to show they are statistically distinguishable.

Let $\ket{\psi}$ be sampled from the first ensemble, which has magic
$\Theta(\operatorname{poly}\log n)$ and $\ket{\phi}$ be sampled from the
second ensemble, which has magic $\Theta(n)$. To show that the two ensembles
are statistically distinguishable, it suffices to show that the two are far in
trace distance, that is,

$\norm{\psi-\phi}_{1}\geq\Omega\left(\frac{1}{\operatorname{poly}n}\right).$
(S85)

The continuity of the stabilizer Shannon entropy tells us that states which
have very different magic must be far in trace distance. More specifically, 6
gives us

$\norm{\psi-\phi}_{1}\log(2^{2n}-1)\geq\Omega(n-\operatorname{poly}\log n),$
(S86)

which is to say that

$\norm{\psi-\phi}_{1}\geq\Omega\left(1-\frac{\operatorname{poly}\log
n}{n}\right)\geq\Omega\left(\frac{1}{\operatorname{poly}n}\right).$ (S87)

∎

## Supplemental Material VI: Implications to magic-state distillation: Proof
of Theorem 4

An immediate application of pseudorandom state ensembles with tunable
stabilizer Rényi entropy is to derive new upper bounds on the problem of magic
state distillation via stabilizer operations.

######  Theorem S8 (Bounds to magic state distillation).

Let $\mathcal{M}$ be a (sub-additive) magic monotone such that
$\Omega(M_{\alpha})\leq\mathcal{M}\leq O(\mathcal{R})$ for some
$\alpha=\Theta(1)$. Then any algorithm that uses stabilizer operations to
synthesize a target quantum state $\ket{B}$ from copies of an arbitrary input
state $\rho$ requires

$\Omega\left(\frac{\mathcal{M}(\ket{B}\bra{B})}{\log^{1+c}(\mathcal{M}(\rho))}\right)$
(S88)

copies of the input to succeed with non-negligible probability, where $c>0$.

###### Proof.

Assume towards contradiction that there is an algorithm that uses only a
number

$o\left(\frac{\mathcal{M}(\ket{B})}{\log^{(1+c)}(\mathcal{M}(\rho))}\right)$
(S89)

of copies of the (here possibly mixed) input $\rho$ to synthesize a single
copy of the state $\ket{B}$, or equivalently, per copy of $\rho$, at least

$\Omega\left(\frac{\log^{(1+c)}(\mathcal{M}(\rho))}{\mathcal{M}(\ket{B}\bra{B})}\right)$
(S90)

copies of $\ket{B}$ may be synthesized.

As detailed in Ref. [27], a necessary condition to be able to synthesize a
target quantum state $\ket{B}$ from an initial quantum state $\rho$ is that
${\cal M}(\rho)>{\cal M}(\ket{B}\bra{B})$ for any measure ${\cal M}$ of
nonstabilizerness. This condition imposes that, per copy of $\rho$, at most

$O\left(\frac{\mathcal{M}(\rho)}{\mathcal{M}(\ket{B}\bra{B})}\right)$ (S91)

copies of $\ket{B}$ can be synthesized, where we have used the assumed sub-
additivity of $\mathcal{M}$, i.e., $\mathcal{M}(\rho^{\otimes r})\leq
r\mathcal{M}(\rho)$.

Recall our assumption that $\Omega(M_{\alpha})\leq\mathcal{M}\leq
O(\mathcal{R})$, which implies that there exists positive constants
$n_{0},s,s^{\prime}$ such that

$sM_{\alpha}(\psi)\leq\mathcal{M}(\psi)\leq s^{\prime}\mathcal{R}(\psi)$ (S92)

for all $n$-qubit states $\psi$ when $n>n_{0}$. For the rest of this proof, we
will assume $n>n_{0}$. To prove our statement on the limitations of a
distillation protocol that works on arbitrary input states $\rho$ (either pure
or mixed), it is sufficient to focus on two special classes of input states,
namely Haar random states and subset phase states. By combining 3 and S92, we
find that

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[\mathcal{M}(\psi)\leq\frac{s\beta
n}{\alpha}\right]\leq 2^{-\frac{Cd^{1-2\beta}}{4(\alpha+1)^{2}}},$ (S93)

for $C,\beta=O(1)$. Then, by our assumption in Eq. S90, the number of copies
of $\ket{B}$ that could be synthesized with high probability per copy of
$\ket{\psi}$ is

$\Omega\left(\frac{\log^{(1+c)}(s\beta
n/\alpha)}{\mathcal{M}(\ket{B}\bra{B})}\right).$ (S94)

On the other hand, if $\ket{\psi_{f,S}}$ were a subset phase state with subset
size $\absolutevalue{S}=2^{\log^{1+c/2}(n)}$, combining 3 with Eq. S92 allows
us to conclude

$\mathcal{M}(\psi_{f,S})\leq s^{\prime}\log^{1+c/2}(n),$ (S95)

then the upper bound in Eq. S91 translates into being able to synthesize no
more than

$O\left(\frac{\log^{(1+c/2)}(n)}{\mathcal{M}(\ket{B}\bra{B})}\right)$ (S96)

copies of $\ket{B}$ per copy of $\ket{\psi}$. Then, a potential distinguisher
handed $\operatorname{poly}(n)$ copies of an unknown $\ket{\psi}$ which is
either one of these two types of states could simply run the black-box state
synthesis protocol, count the number of copies of $\ket{B}$ synthesized with a
SWAP test with a pre-existing copy of $\ket{B}$ – assumed to be a canonical
state such as $\ket{T}$ – and thereby distinguish between these two states
with high probability. Since the subset phase states are indistinguishable
from Haar random states (given polynomially many copies), this is a
contradiction. ∎

The above statement is deliberately agnostic concerning the magic monotone
used, and is applicable for mixed resource states $\rho$ as well. Indeed, the
powerful feature of constructing pseudomagic states is that, as pure states,
no-go results can be proven using pseudomagic pure states and they remain
valid for any state $\rho$ with appropriate extensions of magic monotones to
mixed states. Moreover, it is well-known that while stabilizer entropies serve
as effective magic measures (see SM I for details) for pure states, they fall
short in quantifying the distillable magic for mixed states. This discrepancy
arises because the set of states which have zero stabilizer entropy does not
align with the corresponding set for other magic monotones, particularly those
discussed in Table 1 of the main text. Whereas the set of states for which
stabilizer entropies is zero encompasses stabilizer-mixed states, as detailed
in SM I, the set of zero magic monotones in Table 1 encompasses convex
combinations of stabilizer states, known as the _stabilizer polytope_.
However, the theorem mentioned above remains applicable to any magic monotone
that is only bounded by some $\alpha=\Theta(1)$ stabilizer entropy and the
robustness of magic for pure states. As we discuss below, whether this bound
extends to mixed states as well is unimportant.

To be more specific, let us examine a significant example. Two prominent magic
monotones used for distilling mixed states and for quantifying quantum speed-
ups [94] are the max-relative entropy of magic denoted as $D_{\max}(\rho)$,
and the mixed-state extent denoted as $\Xi(\rho)$. The former has been
introduced in Table 1 of the main text, while the latter is an extension of
the stabilizer extent $\xi(\psi)$ defined for pure states. This extension, as
commonly practiced in quantum resource theories, is achieved through a process
known as _convex-roof_ extension [94]

$\Xi(\rho)\coloneqq\log\inf\left\\{\sum_{j}p_{j}\xi(\psi_{j})\mid\rho=\sum_{j}p_{j}\ket{\psi_{j}}\bra{\psi_{j}}\right\\},$
(S97)

applicable for mixed states, where the infimum is taken over pure state
decompositions of $\rho$, as the convex hull or the convex roof of the
stabilizer extent $\xi$, defined in Table 1. For pure states $\psi$, it holds
that $\Xi(\psi)=D_{\max}(\psi)=\xi(\psi)$, i.e., both the max-relative entropy
and the mixed-state extent reduce to the stabilizer extent $\xi(\psi)$ .

This enables us to further explore the consequences of 8. While for pure
states $\psi$ it holds that

$\Xi(\psi)=D_{\max}(\psi)=\xi(\psi)\leq\mathcal{R}(\psi),$ (S98)

for mixed states $\rho$, the bounds are completely different [94]:

$D_{\max}(\rho)\leq\Xi(\rho),\quad\log\left[2^{D_{\max}(\rho)+1}-1\right]\leq\mathcal{R}(\rho)$
(S99)

whereas no known bound exists between $\Xi(\rho)$ and $\mathcal{R}(\rho)$.
Similarly, no known bound exists between $\Xi$ and $M_{\alpha}$, as well as
between $D_{\max}$ and $M_{\alpha}$ for mixed states. However, by virtue of 8,
the following corollary holds.

######  Corollary S6 (Mixed state magic).

The mixed-state extent $\Xi$ and the max-relative entropy $D_{\max}(\rho)$
satisfy the conditions of 8 for $\alpha=2$ and thus they can be used as a
measure to bound magic state distillation.

The above corollary reflects what was discussed earlier, i.e., the strength of
our pseudomagic construction lies in the ability to leverage established
bounds applicable to pure states, thereby drawing inferences for magic-state
distillation applied to mixed states. Perhaps the most remarkable example of
this is the observation that, despite stabilizer entropies having distinct
null sets in the context of mixed states compared to other magic monotones,
they can still be employed to draw conclusions regarding general magic-state
distillation protocols.

It is also worth mentioning that in practical magic state distillation, one
usually does not require perfect magic states $\ket{B}\bra{B}$ to be
distilled, but this is expected to be possible only approximately with high
probability [94, 95, 2]. This is reminiscent of approximate asymptotic state
transformations in entanglement theory. We here point out that statements of
the above form can be made robust in the appropriate sense to capture such
approximate state transformations. In the situation where $\rho^{\otimes k}$
is not exactly distilled to $\ket{B}\bra{B}^{\otimes m}$, but where this
happens probabilistically with some probability $p\in[0,1]$ in an approximate
fashion, so that there exists an $\epsilon>0$ such that $\rho^{\otimes k}$ is
transformed into $p\tau$ with the property that

$\tr(\tau\outerproduct{B}{B}^{\otimes m})\geq 1-\epsilon,$ (S100)

then it necessarily holds that (see Ref. [94])

$k\geq\frac{\log(p)+\log(1-\epsilon)+m\log
F(\ket{B}\bra{B})^{-1}}{D_{\max}(\rho)},$ (S101)

with $F(\ket{B}\bra{B})$ being the stabilizer fidelity of $\ket{B}\bra{B}$.
This can be used to state a robust version of the above theorem, in the sense
of allowing for approximate state transformations.

## Supplemental Material VII: Implications to nonstabilizer testing

A property test is an algorithm that checks whether a given unknown state has
a particular property or not. We now focus on property testers for non-
stabilizerness and present a theorem that characterizes the requirements for
any such tester.

######  Definition S5 (Non-stabilizer tester).

An algorithm $\mathcal{A}_{\mathcal{M}}$ is a non-stabilizer tester if given
$K$ copies of a state $\ket{\psi}$ and two threshold values $m,M\in[0,n]$ with
$m<M$, obeys the following conditions.

  * •

If $\mathcal{M}({\psi})\geq M$, then $\mathcal{A}_{\mathcal{M}}$ accepts
$\ket{\psi}$ with probability $\geq\frac{2}{3}$.

  * •

If $\mathcal{M}({\psi})<m$, then $\mathcal{A}_{\mathcal{M}}$ accepts
$\ket{\psi}$ with probability $\leq\frac{1}{3}$.

The conditions above are referred to _completness_ and _soundness_ conditions,
respectively.

In this section, we prove the following theorem.

######  Theorem S9 (Copies required for non-stabilizer testers).

Any tester for the stabilizer entropy $M_{\alpha}$ requires
$K=\Omega(2^{\frac{m}{4+c}})$ (for $c>0$) copies for any
$m<M<\frac{n}{4\alpha}$.

###### Proof.

First of all, by plugging $\beta=1/4$ into 3, we see that for a Haar random
state vector $\ket{\psi}$,

${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[M_{\alpha}({\psi})<\frac{n}{4\alpha}\right]<2^{-\Omega(2^{n/2})}.$
(S102)

Consequently, one has that for any $M<n/(4\alpha)$ one can write
${\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[M_{\alpha}({\psi})<M\right]<2^{-\Omega(2^{n/2})}$.
Let us now define the ensembles

$\displaystyle\mathcal{E}_{M_{\alpha}\geq M}$
$\displaystyle\coloneqq\\{\ket{\psi}\mid M_{\alpha}({\psi})\geq M\\},$ (S103)
$\displaystyle\mathcal{E}_{M_{\alpha}<M}$
$\displaystyle\coloneqq\\{\ket{\psi}\mid M_{\alpha}({\psi})<M\\}$

of states with $\alpha$-stabilizer entropy at least $M$ and at most $M$. We
use the notation $\Phi_{\mathcal{E}}^{(K)}$ to denote the ensemble average

$\Phi_{\mathcal{E}}^{(K)}={\mathbb{E}}_{\ket{\psi}\sim\mathcal{E}}\left[\outerproduct{\psi}{\psi}^{\otimes
K}\right],$ (S104)

where $\sim$ denotes the uniform distribution over $\mathcal{E}$. We show that
the ensemble $\mathcal{E}_{M_{\alpha}>M}$ is exponentially close to the
ensemble of Haar random state, i.e.,

$\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\Phi_{\operatorname{Haar}}^{(K)}}_{1}=O(2^{-\Omega(2^{n/2})}).$
(S105)

First of all note that denoting
$\pi_{M}\coloneqq{\mathsf{Pr}}_{\ket{\psi}\sim\operatorname{Haar}}\left[M_{\alpha}({\psi})<M\right]$,
we have $\pi_{M}\leq 2^{-\Omega(2^{n/2})}$. Notice that we can express
$\Phi_{\operatorname{Haar}}^{(K)}$ for every $K$ as

$\Phi_{\operatorname{Haar}}^{(K)}=\pi_{M}\Phi_{\mathcal{E}_{M_{\alpha}<M}}^{(K)}+(1-\pi_{M})\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)},$ (S106)

thus the following chain of equalities and inequality holds,

$\displaystyle\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\Phi_{\operatorname{Haar}}^{(K)}}_{1}$
$\displaystyle=\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\pi_{M}\Phi_{\mathcal{E}_{M_{\alpha}<M}}^{(K)}-(1-\pi_{M})\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}}_{1}$ (S107)
$\displaystyle=\norm{-\pi_{M}\Phi_{\mathcal{E}_{M_{\alpha}<M}}^{(K)}+\pi_{M}\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}}_{1}$
$\displaystyle=\pi_{M}\norm{\Phi_{\mathcal{E}_{M_{\alpha}<M}}^{(K)}-\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}}_{1}\leq\pi_{M}.$

Now, consider the set $\mathcal{E}_{f,S}$ of subset phase states, i.e.,

$\ket{\psi_{f,S}}=\frac{1}{\sqrt{\absolutevalue{S}}}\sum_{x\in
S}(-1)^{f(x)}\ket{x},$ (S108)

where both the Boolean function $x\mapsto f(x)$ and the subset $S$ have been
chosen at random. Then, from Theorem $2.1$ of Ref. [31] we have that for every
$K<\absolutevalue{S}<d$

$\norm{\Phi_{\mathcal{E}_{f,S}}^{(K)}-\Phi_{\operatorname{Haar}}^{(K)}}_{1}=O\left(\frac{K^{2}}{\absolutevalue{S}}\right),$
(S109)

and consequently one has

$\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\Phi_{\mathcal{E}_{f,S}}^{(K)}}_{1}\leq\norm{\Phi_{\mathcal{E}_{f,S}}^{(K)}-\Phi_{\operatorname{Haar}}^{(K)}}_{1}+\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\Phi_{\operatorname{Haar}}^{(K)}}_{1}=O\left(\frac{K^{2}}{\absolutevalue{S}}\right).$
(S110)

The above equation implies that the ensemble of phase states and the ensemble
of states with stabilizer entropy $M_{\alpha}({\psi})\geq M$ (for $M\leq
n/(4\alpha)$) cannot be distinguished by a non-stabilizer tester unless
$K=\Omega(\sqrt{\absolutevalue{S}})$. Indeed, following the arguments of Ref.
[74], by applying the Helstrom bound [96], we know for any state
discrimination protocol between two ensembles
$\mathcal{E},\mathcal{E}^{\prime}$ the discrimination probability given $K$
copies, is upper bounded by
$\frac{1}{2}+\norm{\Phi_{\mathcal{E}}^{(K)}-\Phi_{\mathcal{E}^{\prime}}^{(K)}}_{1}$.
Therefore, for a non-stabilizer tester $\mathcal{A}_{\mathcal{M}}$, to have a
acceptance probability $\geq 2/3$ one should have

$\norm{\Phi_{\mathcal{E}_{M_{\alpha}\geq
M}}^{(K)}-\Phi_{\mathcal{E}_{f,S}}^{(K)}}_{1}\geq\frac{1}{6}.$ (S111)

To conclude the proof, observe that $\ket{\psi}\in\mathcal{E}_{f,S}\implies
M_{\alpha}({\psi})\leq\log\absolutevalue{S}$, so
$K=\Omega\left(2^{\frac{m}{4+c}}\right)$ for $c>0$. Indeed, if we assume that
$K=O\left(2^{\frac{m}{4+c}}\right)$ copies were sufficient, one could take a
random subset phase state $\ket{\psi}\in\mathcal{E}_{f,S}$ with
$\absolutevalue{S}=2^{m/2}$ having $M_{\alpha}({\psi})\leq m$ for $c>0$ and
could distinguish between $\ket{\psi}\in\mathcal{E}_{f,S}$ and
$\ket{\psi}\in\mathcal{E}_{M_{\alpha}\geq M}$ with
$K=O\left(2^{\frac{m}{4+c}}\right)$. However, from Eq. S110 one would need

$K=\Omega\left(\sqrt{\absolutevalue{S}}\right)=\Omega(2^{m/4})$ (S112)

copies to achieve this discrimination, so we have arrived at a contradiction.
∎

######  Corollary S7 (Property testers for magic monotones).

Given any magic monotone $\mathcal{M}$ such that $\mathcal{M}\geq sM_{\alpha}$
for some $\alpha,s$, a property tester for $\mathcal{M}$ requires
$K=\Omega(2^{\frac{m/s}{4+c}})$.

###### Proof.

Consider a magic monotone $\mathcal{M}$ such that $\mathcal{M}\geq
sM_{\alpha}$. Assuming the contrapositive, i.e., that one can use
$O(2^{\frac{m/s}{4+c}})$ to distinguish whether a state vector $\ket{\psi}$
has $\mathcal{M}({\psi})\leq m$. However, if one could do so, one also would
have distinguished $M_{\alpha}({\psi})\leq m/s$ using $O(2^{\frac{m/s}{4+c}})$
copies and this is a contradiction to 9. ∎

Thanks to 11 and 10, 9 can be strengthened to hold against non-stabilizerness
testers designed for classes of input states with bounded entanglement between
$\omega(\log(n))$ and $n$. We may similarly strengthen the property testing
lower bounds in Section 3 of Ref. [31] to hold for input states with bounded
magic.

## Supplemental Material VIII: The independence of pseudomagic and
pseudoentanglement

In this section, we are going to show the following results:

  * •

Given two functions $f(n),g(n)\in[\omega(\log n),O(n)]$ there exists a
pseudorandom ensemble with entanglement entropy $\Theta(f(n))$ over
superpolynomially many cuts and magic $\Theta(g(n))$, for any magic measure
$\mathcal{M}$ obeying $\Omega(M_{2})\leq\mathcal{M}\leq O(\mathcal{R})$ (e.g.,
those listed in Table I of the main text).

  * •

Given any function $f(n)\in[\omega(\log n),O(n)]$, there exists a pseudomagic
pair with gap $\omega(\log n)$ vs. $O(n)$ and fixed entanglement
$\Theta(f(n))$ over superpolynomially many cuts.

  * •

Given any function $g(n)\in[\omega(\log n),O(n)]$, there exists a
pseudoentangled pair with maximal gap $\omega(\log n)$ vs. $O(n)$ and fixed
magic $\Theta(g(n))$.

We use the following notation throughout this section: given any unitary $U$
and any ensemble of states $\mathcal{E}\coloneqq\\{\ket{\psi_{k}}\\}$, we
define the ensemble induced by applying $U$ to every member of $\mathcal{E}$
as $\mathcal{E}_{U}\coloneqq\\{U\ket{\psi_{k}}\\}$.

######  Lemma S9 (Pseudorandomness is preserved under application of efficient
unitaries).

For any unitary $U$ with a $\operatorname{poly}$-depth circuit and any
pseudorandom ensemble $\mathcal{E}$, the ensemble $\mathcal{E}_{U}$ is also a
pseudorandom ensemble.

###### Proof.

Since $U$ is efficient by assumption, the new ensemble automatically has the
two necessary properties of a pseudorandom ensemble:

  * •

_Efficient preparability_ : we can prepare $\mathcal{E}_{U}$ by first
preparing $\ket{\psi_{k}}$ and then applying the unitary $U$.

  * •

_Computational indistinguishability_ : assume for contradiction’s sake that
there exists some efficient distinguisher $\mathcal{A}$ and some
$t=O(\operatorname{poly}n)$ such that

$\absolutevalue{{\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}_{U}}[\mathcal{A}\big{(}\ket{\psi}^{\otimes
t}\big{)}=1]-{\mathsf{Pr}}_{\ket{\phi}\sim\operatorname{Haar}}[\mathcal{A}\big{(}\ket{\phi}^{\otimes
t}\big{)}=1]}>{\mathsf{negl}}(n).$ (S113)

Then, define the (efficient) distinguisher
$\mathcal{A}^{\prime}\coloneqq\mathcal{A}\circ U^{\otimes t}$. Observe that
${\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}}[\mathcal{A}^{\prime}\big{(}\ket{\psi}^{\otimes
t}\big{)}=1]={\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}_{U}}[\mathcal{A}\big{(}\ket{\psi}^{\otimes
t}\big{)}=1]$, and similarly by the invariance of the Haar measure,
${\mathsf{Pr}}_{\ket{\phi}\sim\operatorname{Haar}}[\mathcal{A}^{\prime}\big{(}\ket{\phi}^{\otimes
t}\big{)}=1]={\mathsf{Pr}}_{\ket{\phi}\sim\operatorname{Haar}}[\mathcal{A}\big{(}\ket{\phi}^{\otimes
t}\big{)}=1]$. Therefore,

$\absolutevalue{{\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}}[\mathcal{D}^{\prime}\big{(}\ket{\psi}^{\otimes
t}\big{)}=1]-{\mathsf{Pr}}_{\ket{\phi}\sim\operatorname{Haar}}[\mathcal{D}^{\prime}\big{(}\ket{\phi}^{\otimes
t}\big{)}=1]}>{\mathsf{negl}}(n),$ (S114)

which contradicts the assumption that $\mathcal{E}$ is pseudorandom.

∎

A special case of the above lemma is that $\mathcal{E}_{U}$ is pseudorandom
for any Clifford unitary $U$, since all Clifford unitaries can be implemented
with $O(n^{2})$ gates [97]. This allows us to prove that there exist
pseudomagic pairs where the low magic ensemble has an arbitrary degree of
entanglement. Let us first prove the following lemma.

######  Lemma S10 (Pseudomagic ensembles with tunable entanglement).

Let $\mathcal{E}_{f,S}$ be the ensemble of subset phase state with
$\log|S|=\omega(\log n)$. Given any function $f(n)\in[\Omega(\log|S|),O(n)]$,
there exist a polynomial-depth unitary $U^{*}$ such that the ensemble
$\mathcal{E}_{U^{*}}=\\{U^{*}\ket{\psi_{f,S}}\,|\,\ket{\psi_{f,S}}\in\mathcal{E}_{f,S}\\}$
obeys:

  * •

$\mathcal{M}(\ket{\psi})=\Theta(\log|S|)$ with high probability over
$\ket{\psi}\sim\mathcal{E}_{U^{*}}$, where $\mathcal{M}$ is a magic measure
such that $\Omega(M_{2})\leq\mathcal{M}\leq O(\mathcal{R})$;

  * •

$S(\psi_{A})=\Theta(f(n))$ with probability $\geq 1-\operatorname{negl(n)}$
over $\ket{\psi}\sim\mathcal{E}_{U^{*}}$;

  * •

$\mathcal{E}_{U^{*}}$ is pseudorandom.

###### Proof.

We first show that one can tune entanglement of a pseudorandom ensemble
without changing magic. Therefore, one has that
$\mathcal{M}(\ket{\psi})=\Theta(\log|S|)$ with high probability. We do this by
acting on the states in the ensemble with a Clifford unitary, which does not
change magic. For any $\Omega(\log|S|)\leq f(n)\leq O(n)$, we will let this
Clifford unitary $U$ act on the first $f(n)$ qubits in the system, and leave
the rest untouched.

Consider the cut $A|B$, where $A$ is the first $f(n)/2$ qubits and $B$
contains the rest of the system. The 2-Rényi entanglement of any state
$\ket{\psi}$ across this cut can be written
$-\log\tr(S_{A}\outerproduct{\psi}{\psi}^{\otimes 2})$, where $S_{A}$ is the
swap operator on the $A$ subsystem. Now, letting $\mathcal{C}_{f}$ (resp.
$\operatorname{Haar}_{f}$) be the ensemble of Clifford (resp. Haar) unitaries
over $f(n)$ qubits, for any state $\ket{\psi}$:

$\mathbb{E}_{U\sim\mathcal{C}_{f}}\tr(S_{A}(U\outerproduct{\psi}{\psi}U^{\dagger}))=\mathbb{E}_{U\sim\operatorname{Haar}_{f}}\tr(U^{\otimes
2}S_{A}(U^{\dagger})^{\otimes 2}\outerproduct{\psi}{\psi}^{\otimes 2}),$
(S115)

and using the identity

$\mathbb{E}_{U\sim\operatorname{Haar}_{f}}U^{\otimes 2}O(U^{\dagger})^{\otimes
2}=\frac{\tr
O-2^{-f(n)}\tr(OS)}{4^{f(n)}-1}I+\frac{\tr(OS)-2^{-{f(n)}}\tr(O)}{4^{f(n)}-1}S,$
(S116)

where $S$ is the swap operator over $f(n)$ qubits. Since
$\tr(S_{A})=2^{f(n)/2}\cdot 4^{f(n)/2}=2^{3f(n)/2}$ (recall that we are only
taking the trace of $S_{A}$ over sites where we acted with our Haar random
unitary), and $\tr(S_{A}S)=\tr(S_{B})=2^{3f(n)/2}$, we get

$\mathbb{E}_{U\sim\operatorname{Haar}_{k}}U^{\otimes 2}S_{A}(U^{\otimes
2})^{\dagger}=\frac{2^{f(n)/2}}{2^{f(n)}+1}(I+S),$ (S117)

so
$\mathbb{E}_{U\sim\operatorname{Haar}_{k}}\tr(S_{A}(U\outerproduct{\psi}{\psi}U^{\dagger})^{\otimes
2})\leq\frac{2^{f(n)/2+1}}{2^{f(n)}+1}\leq 2^{-f(n)/2+1}$. Now, consider
$2^{f(n)/4-2}$ different cuts $(A_{i},B_{i})$ such that $A$ is taken to be
$f(n)/2$ of the first $f(n)$ qubits (there are $\binom{f}{f/2}\sim 2^{f}(n)$
cuts like this). By a simple union bound, we find that there must be at least
one $U^{*}\in\mathcal{C}_{f}$ such that

$\mathbb{E}_{\ket{\psi}\sim\mathcal{E}_{U^{*}}}\tr(S_{A}\outerproduct{\psi}{\psi})\leq
2^{-f(n)/4}$ (S118)

for _each_ of the cuts $(A_{i},B_{i})$. Finally, let us show that acting with
a Clifford unitary on $f(n)$ qubits can change the $0$-Rényi entropy of at
most $f(n)$. To see this, let us specialize the discussion to a subset phase
state $\ket{\psi_{f,S}}\propto\sum_{x\in S}(-1)^{f(x)}\ket{x}$ and let us
apply the unitary $U^{*}$ on the first $f(n)$ qubits. It is immediate to see
that we can write

$U^{*}\ket{\psi_{f,S}}\propto\sum_{x\in\tilde{S}}(-1)^{f(x)}\ket{x}$ (S119)

where $|\tilde{S}|\leq|S|2^{f(n)}$. As such, one has that the $0$-Rényi
entropy of entanglement $S_{0}(\psi_{A})\leq\log|S|+k=O(f(n))$, where we used
the fact that $f(n)=\Omega(\log|S|)$. Combining these two facts and using
Markov’s inequality, we immediately have that

${\mathsf{Pr}}_{\ket{\psi}\sim\mathcal{E}_{U^{*}}}\left[S(\psi_{A})=\Theta(f(n))\right]\geq
1-2^{-f(n)/4-1}=1-\operatorname{negl}(n).$ (S120)

Furthermore, this statement holds across
$2^{f(n)/4-2}=\omega(\operatorname{poly}(n))$ (which is superpolynomial) cuts,
as desired.

Finally, since Clifford unitaries can be implemented efficiently, we can
exploit 9 and claim that $\mathcal{E}_{U^{*}}$ is pseudorandom. This concludes
the proof.

∎

Finally, we can construct the pseudomagic pair with gap
$\Theta(\operatorname{poly}\log n)$ vs. $\Theta(n)$ and fixed entanglement.
Consider the ensemble of subset phase states $\mathcal{E}_{f,S}$ with
$|S|=\omega(\operatorname{poly}(n))$ and construct the ensemble
$\mathcal{E}_{U^{*}}$ discussed above. We just showed that
$S(\psi_{A})=\Theta(k(n))$ with high probability over
$\ket{\psi}\sim\mathcal{E}_{U^{*}}$ and, since $U^{*}$ does not change magic,
it holds that