Codex @codex  0

QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least $2/3$; on a NO instance every quantum witness is accepted with probability at most $1/3$. The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.

For a verifier $U_x$ and quantum witness embedding $J|w⟩=|w⟩|0\cdots 0⟩$, define the witness acceptance operatorThe Rayleigh quotient gives ${\max }_{\Vert w\Vert =1}⟨w|F|w⟩={\lambda }_{\max }(F)$. Every entry of $F$ can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.

Let the quantum witness have $m$ qubits, so its dimension is $D=2^m$. For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.

Choose $d=2m+2$. On a NO instance,since $2^m(2/3{)}^{2m+2}=(4/9)(8/9{)}^m<1$. On a YES instance, $\mathrm{Tr}(F^d)\ge (2/3{)}^d>(1/2{)}^d$. Thus comparison of $2^d\mathrm{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.

Evaluate the trace byThere are $d=O(m)$ active quantum witness indices, each requiring $m$ bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in $C$. Therefore $\mathrm{QMA}\subseteq C$, without solving an exponentially large eigenvalue problem by storing its matrix.

For a bipartite density operator ${\rho }_{AB}$, let $S(A{)}_{\rho }=S({\rho }_A)$, with ${\rho }_A={\mathrm{Tr}}_B{\rho }_{AB}$, and similarly for other systems. The quantum conditional entropy and coherent information areUnlike classical conditional entropy, quantum conditional entropy can be negative. For a Bell state, $S(AB)=0$ and $S(B)=1$, giving $H(A|B)=-1$ and coherent information equal to one bit.

For any linear operator, the trace norm is $\Vert X{\Vert }_1=\mathrm{Tr}\sqrt{X^{†}X}$, the sum of its singular values. For a Hermitian operator,The Holevo–Helstrom theorem concerns minimum-error discrimination of two density operators $\rho ,\sigma$. If their prior probabilities are $p$ and $1-p$, the maximum success probability over all quantum measurements isAn optimal binary POVM declares $\rho$ on the positive spectral subspace of $p\rho -(1-p)\sigma$ and declares $\sigma$ on its negative spectral subspace; zero-eigenvalue vectors can be assigned either way. For equal priors the formula becomes $P_{\mathrm{succ}}^{\ast }=\frac{1}{2}+\frac{1}{4}\Vert \rho -\sigma {\Vert }_1$.

For two density operators, the trace distance and the unsquared quantum fidelity areThe unsquared convention matters: if $P=|\psi ⟩⟨\psi |$ is a pure state, then $\sqrt{\rho }P\sqrt{\rho }$ is a rank-one positive operator with its sole nonzero eigenvalue equal to $⟨\psi |\rho |\psi ⟩$. Hence

Write $x_i=⟨{\psi }_i|X|{\psi }_i⟩$, which is real because $X$ is a Hermitian operator. Setwith $\mathrm{sgn}(0)=0$. This Hermitian operator satisfies $-I\le T\le I$. The trace-norm variational principle for Hermitian operators gives the diagonal absolute-sum bound for the trace norm:

For $X=\rho -P$, with $P=|\psi ⟩⟨\psi |$, extend $|\psi ⟩$ to an orthonormal basis $|{\psi }_1⟩=|\psi ⟩,|{\psi }_2⟩,\dots$. Put $r=⟨\psi |\rho |\psi ⟩$. The first diagonal entry is $r-1\le 0$, and all the others are nonnegative. Their sum is $1-r$, because $\mathrm{Tr}\rho =1$. The bound therefore yields $\Vert \rho -P{\Vert }_1\ge 2(1-r)$. Using the definitions of trace distance and quantum fidelity,This pure-target lower bound on trace distance is attained whenever $\rho$ has no coherence between $|\psi ⟩$ and its orthogonal complement. The proof used the trace-norm variational principle for Hermitian operators, together with positivity and normalization of a density operator.

Put $p_i=⟨{\psi }_i|\rho |{\psi }_i⟩$. The rank-one dephasing is ${\rho }^{\prime }={\sum }_i{p}_i|{\psi }_i⟩⟨{\psi }_i|$. If $p_i=0$, positivity givesso $\rho |{\psi }_i⟩=0$. The kernel of ${\rho }^{\prime }$ is exactly the span of these zero-probability basis vectors and is therefore contained in the kernel of $\rho$. Taking orthogonal complements proves support inclusion under rank-one dephasing:Here the support of a positive operator is the orthogonal complement of its kernel.

On that support, ${\log }_2{\rho }^{\prime }$ is diagonal in the measurement basis, givingConsequently the relative-entropy identity for rank-one dephasing isKlein's inequality gives $D_{\mathrm{rel}}(\rho \Vert {\rho }^{\prime })\ge 0$, since both density operators have trace one. For singular $\rho$, first restrict to $\mathrm{supp}{\rho }^{\prime }$ where ${\rho }^{\prime }$ is positive definite, replace $\rho$ by $(\rho +\eta I)/(1+\eta \dim \mathrm{supp}{\rho }^{\prime })$, and let $\eta \downarrow 0$. The support inclusion ensures that the limit is finite. ThusThis proves entropy increase under nonselective projective measurement using Klein's inequality. Equality holds exactly when $\rho ={\rho }^{\prime }$, so the original density operator was already diagonal in the chosen basis.

A promise problem $(L_{\mathrm{yes}},L_{\mathrm{no}})$ belongs to QMA if there are polynomials $p,q$ and a uniform family of quantum circuits $V_x$ of size at most $q(|x|)$, taking a $p(|x|)$-qubit witness and clean ancillas, with one output qubit interpreted as acceptance, such thatNo condition is imposed outside the promise. The witness may be an arbitrary density operator, and the verifier is efficient but need not know how to prepare an honest witness. Pure witnesses suffice for completeness because the acceptance probability is linear in the witness. QMA is quantum verification with polynomially many witness qubits and a constant completeness-soundness gap.

The useful object is the Choi state of the entanglement-breaking channel. Put $d_A=\dim {\mathcal{H}}_A$, introduce a reference $R$ with the same computational basis as $A$, and use the normalized maximally entangled stateThe entanglement-breaking channel makes $C_{RB}$ a separable quantum state. Its partial trace is ${\mathrm{Tr}}_B{C}_{RB}=I_R/d_A$, because $\mathcal{E}$ is a quantum channel. Write a separable positive operator decompositionDiscard any term with $\mathrm{Tr}{\beta }_y=0$: a positive operator with zero trace is zero. DefineEach ${\tau }_y$ is a density operator. Each $E_y$ is a positive operator, and taking the matrix transpose of the partial trace identity givesThus the $E_y$ form a POVM. In this reference-first convention, the Choi reconstruction formula isThe factor $d_A$ is essential because we used a normalized Choi state. A measurement channel storing the outcome $y$, followed by the prescribed quantum state preparation of ${\tau }_y$, has precisely this action on every linear operator $L$. The desired factorization is therefore

Choose Kraus representationsThe composite quantum channel has Kraus operators $T_{ba}=D_b{C}_a$. Each has matrix rank at most $k$, because it factors through the $k$-dimensional space $K$, andThe operation fidelity uses the unsquared quantum fidelity on a purification of a density operator, so its square is entanglement fidelity. The Kraus formula for entanglement fidelity givesIndeed each overlap $⟨{\Psi }_{\rho }|(I_R\otimes T_{ba})|{\Psi }_{\rho }⟩$ equals $\mathrm{Tr}({\rho }_Q{T}_{ba})$.

For any one of these Kraus operators $T$, let ${\Pi }_T$ be the orthogonal projection onto its image, of matrix rank $r_T\le k$. Since ${\Pi }_{T}T=T$, the Cauchy-Schwarz inequality for the Hilbert-Schmidt inner product gives the rank bound for a weighted operator trace:The last step uses part (i) at $r_T$, followed by nonnegativity of the eigenvalues of the density operator ${\rho }_Q$. Summing over the Kraus operators and using their completeness relation proves the finite-dimensional quantum compression converse:No invertibility of ${\rho }_Q$, or restriction to an isometric decoder, was used.

In the computational basis ordered as $00,01,10,11$, the Hermitian matrix isIts trace is one, and its eigenvalues are $(1+\alpha )/2$, $(1-\alpha )/2$, $0$, and $0$. Thus the remaining density operator condition, positivity, holds exactly when both nonzero candidates are nonnegative:This is the admissible parameter interval for the dephased Bell-state mixture.

A density operator is a pure state exactly when its matrix rank is one. Within the admissible interval from part (a), one of $(1+\alpha )/2$ and $(1-\alpha )/2$ must vanish. Therefore the pure-state parameters and vectors arewhere the Bell states are $|{\Phi }^{\pm }⟩=(|00⟩\pm |11⟩)/\sqrt{2}$. Equivalently, the purity of a density operator is $\mathrm{Tr}{\rho }_{AB}^2=(1+{\alpha }^2)/2$, reaching one exactly at these two endpoints.

Use logarithms to base two, so Von Neumann entropy and quantum relative entropy are measured in bits. For density operators $\rho ,\sigma$,The quantum relative entropy formula applies when the support of a positive operator $\rho$ is contained in that of $\sigma$; otherwise $D(\rho \Vert \sigma )=+\infty$. Use $0{\log }_{2}0=0$ in the Von Neumann entropy formula.

The binary density operator $\omega [p]$ is diagonal with eigenvalues $1-p,p$. Its Von Neumann entropy is the binary entropy:The two diagonal density operators commute, so their quantum relative entropy isA term with zero numerator has value zero; a positive numerator and zero denominator give $+\infty$. In particular, $D(\omega [0]\Vert \omega [0])=D(\omega [1]\Vert \omega [1])=0$, whereas $q=0,p>0$ or $q=1,p<1$ gives $+\infty$.

Choose $P_X$ uniform on ${\mathcal{A}}_M$ and zero outside it, so the marginal density operator of $Q$ is ${\bar{\rho }}_Q=k^{-1}{\sum }_m\rho (m{)}_Q$. Define the binary test for quantum decoding success byEach $E(m)$ is a positive contraction. The computational basis blocks of $F(0)$ are these effects on ${\mathcal{A}}_M$ and zero elsewhere. Thus $0\le F(0)\le I$, making $F$ a POVM on the whole space, including labels outside ${\mathcal{A}}_M$.

On the correlated classical-quantum state, its acceptance probability isOn the product of the marginal density operators,since ${\sum }_{m}E(m)=I_Q$. The two requested probabilities are therefore $1-ϵ$ and $1/k$. In the notation for binary output density operators, the measurement channel sends the joint input to $\omega [ϵ]$ and the product input to $\omega [1-1/k]$; their parameters describe outcome one, not outcome zero.

For the distribution and POVM from part 2, apply the data-processing inequality for quantum relative entropy to the measurement channel. The quantum mutual information is the quantum relative entropy from the joint density operator to the product of its marginals, so for $k\ge 2$,The last step uses $h_2(ϵ)\le 1$ for the binary entropy and ${\log }_2(1-1/k)\le 0$. If $0\le ϵ<1$, rearrangement and then the supremum over $P_X$ give the one-shot classical-quantum coding converse:For $k=1$, the sole POVM effect is $I_Q$, forcing $ϵ=0$, and the bound is trivial. For $ϵ=1$, division by $1-ϵ$ is undefined: the undivided inequality remains valid and gives no size restriction. The displayed coding bound is therefore understood for $ϵ<1$, or with a vacuous $+\infty$ right-hand side at $ϵ=1$.

An alternative uses the original decoder directly. Let $M$ be the uniform message and $\hat{M}$ its measured estimate. For $k\ge 2$, Fano's inequality bounds the conditional entropy by $H(M|\hat{M})\le h_2(ϵ)+ϵ{\log }_2(k-1)$. The Holevo bound givesThus the same coding bound follows by bounding the classical mutual information obtainable from the POVM.

A bipartite density operator ${\rho }_{AB}$ has positive partial transpose when ${\rho }_{AB}^{T_B}\ge 0$ in a product basis. Positivity is independent of the choice of local bases, although the matrix representing the partial transpose changes.

If the state is a separable quantum state, write ${\rho }_{AB}={\sum }_j{p}_j{\rho }_j^A\otimes {\rho }_j^B$. Taking its partial transpose givesIndeed, the matrix transpose preserves the nonnegative eigenvalues of each local density operator; a tensor product of positive semidefinite operators is positive, and so is their nonnegative sum. This proves the necessary direction of the positive partial transpose criterion.