8

This answer won't actually give you a bound, but will provide some information that may help you in your search. You may be able to find an answer in the random matrix theory literature if you translate the question into different terms, as I will describe. First, suppose that $\Phi_0(X) = U_0 X U_0^{\dagger}$ and $\Phi_1(X) = U_1 X U_1^{\dagger}$ are any ...


5

Since the Haar-measure is unitarily invariant, the $\mathbf{D}_\psi$ that we obtain will be independent of $\psi$. In fact, the $\mathbf{D}_\psi$ obtained from measuring $\psi$ with respect to any basis becomes $\psi$- and basis-independent. As an example, let $\mathbb{B} = \{ \Pi_{j} = | j \rangle \langle j | \}_{j=1}^{d}$ be an orthonormal basis of $\...


4

The result you're looking for is effectively Proposition 19 of the paper: Almost all quantum channels are equidistant; which I'm rewriting here for convenience: Let $U, V \in \mathcal{U}(d)$ be two independent random variables, at least one of them being Haar-distributed. Then, with overwhelming probability as $d \rightarrow \infty$, the quantum channels $\...


4

With the chosen structure of $ U $, i think it's even possible to prove the stronger statement: $$ \langle z| \rho|z \rangle = \langle z| \sigma_\rho|z \rangle, \hspace{0.2em} \text{where} \hspace{0.2em} \sigma_\rho = \mathbb{E}_U \big[U\rho U^\dagger\big] \text{and} \hspace{0.3em} |z\rangle \hspace{0.3em} \text{a computational basis vector.}$$ You may ...


4

I will answer this question in a more general context. You might know that Haar's theorem tells you that on any locally compact group $G$, there is a unique left-invariant (Borel) measure $\mu$, up to a positive constant. Left-invariance means that $\mu(g A)=\mu(A)$ for any $g\in G$ and (measurable) set $A\subset G$. This is the (left-) Haar measure on $G$. ...


4

Suppose that was not the case. Then taking the first column of a uniformly random unitary matrix gives you a nonuniformly random state. That means that there is some state, call it $|\psi\rangle$, that is relatively more likely to be found when sampling states with such procedure. But that would mean that the unitaries whose first column is $|\psi\rangle$ ...


4

Yes. A uniformly (Haar random) sampled state vector $|\psi\rangle$ is characterized by the fact that the probability measure is invariant under any $U$, i.e., colloquially, $U|\psi\rangle$ is just as likely as $|\psi\rangle$ for any unitary $U$. On the other hand, a Haar random unitary $V$ is defined the same way: "$UV$ is just as likely as $V$, for any ...


3

The issue that easily leads to confusion is the dual role played by output bitstring probability. It enters the computation of the average in two ways. On one hand, it determines how often one sees different bitstrings. On the other hand, it determines the contribution that each bitstring makes towards the average. In mathematical terms, the output bitstring ...


3

I'm writing an alternate proof because it uses some interesting tools, computes the value of these expressions, and gives some insights into how we can interpret the quantities in consideration. The first term is $\mathbb{E}_{\mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right] $, where $\rho := U | \psi_{0} \rangle \langle \psi_{0} | U^{\...


3

The paper does not specify the exact algorithm or class of distributions $\mathcal{D}$ for which such algorithm fails to refute XQUATH, and some classes of distributions $\mathcal{D}$ do not satisfy XQUATH, so some additional assumptions about $\mathcal{D}$ are needed. In this answer we will try to follow the idea of the paper and try to show that it fails ...


3

Maybe think of it this way - a quantum computer, executing a small enough random circuit $C$ acting on a state initially prepared as $\vert 0^n\rangle$ and sampling therefrom, will get an $n$-bit string as output, say $0110\cdots10$. We know, merely from the fact that this was sampled, that the squared amplitude of $\vert 0110\cdots10\rangle$ is large and ...


3

First of all, that does not imply anything for shorter (constant/logarithmic) depths. Moreover, the 2-design property does not imply that the outcome distribution is the same as for Haar-random unitaries, but only the first and second moment is. In the mentioned paper, they consider anti-concentration of the outcome distribution. To show this feature, a ...


2

The two facts are connected in that they both arise as a result of rotational invariance of the Haar measure. We will derive them in the case of large $n$ since this is when the Porter-Thomas distribution takes the exponential form given in the question. Also, this case admits an intuitive proof backed by a geometric picture. For small $n$, Porter-Thomas ...


2

$U-I$ is a normal matrix so $||U-I||_{op}$ is its eigenvalue with the largest magnitude. The eigenvalue equation for this matrix is $$(U-I)|\psi\rangle=\lambda|\psi\rangle,$$ so $$|\lambda|^2=(\cos\phi-1)^2+\sin^2\phi=4\sin^2\frac{\phi}{2}\Rightarrow |\lambda|=2\left|\sin\frac{\phi}{2}\right|,$$ where $e^{i\phi}$ is some eigenvalue of $U$. Now, the ...


1

All you need are simple tools from measure concentration. The setup is as follows (repeated from the question above for completeness): $| \psi \rangle$ is an $n$-qubit state and $| \alpha \rangle := | \alpha_{1} \rangle \otimes | \alpha_{2} \rangle \otimes \cdots \otimes | \alpha_{n} \rangle$ is an $n$-qubit product state where each $| \alpha_{j} \rangle$ is ...


Only top voted, non community-wiki answers of a minimum length are eligible