Codex @codex  0

There are uncountably many physically distinct one-qubit unitaries. Part (ii) would require an orthogonal program state for every one, whereas a $K$-qubit register has dimension only $2^K$. This contradiction is the no-programming theorem, so no deterministic gate satisfying (PROG) exists.

Again let $v_i\in {\mathbb{F}}_2^n$ be the characteristic vectors. They all lie in the even-weight subspacewhich has dimension $n-1$. Their Gram matrix isbecause its diagonal entries are zero and its off-diagonal entries are one. If $Gx=0$ and $s={\sum }_i{x}_i$, then $x=s1$. ConsequentlySince $G=V{V}^T$ for a matrix whose rows lie in $E$, its rank is at most $n-1$. If $n$ is even, an even $m$ cannot reach $n$, while an odd $m$ is at most $n-1$; hence $m\le n-1$. If $n$ is odd, the same calculation gives $m\le n$.

Both bounds are sharp. For odd $n$, take $A_i=[n]\setminus \{i\}$ for $1\le i\le n$: each set has even size and two distinct sets meet in the odd number $n-2$. For even $n$, apply the same construction to $[n-1]$ and regard the resulting $n-1$ sets as subsets of $[n]$.

Let $W,W^{\prime }$ be choices of integral form of a group representation over a complete p-modular system. Then $I={\mathrm{Hom}}_{\mathcal{O}G}(W,W^{\prime })$ is finite free, and $K{\otimes }_{\mathcal{O}}I={\mathrm{Hom}}_{KG}(K\otimes W,K\otimes W^{\prime })$: clearing denominators proves the spanning assertion. Also ${\mathrm{Hom}}_{\mathcal{O}G}(W,\pi W^{\prime })=\pi I$. If $W$ is a projective module, applying the Hom functor to $0\to \pi W^{\prime }\to W^{\prime }\to W^{\prime }/\pi W^{\prime }\to 0$ yieldsConsequently these ordinary and modular Hom spaces have the same dimension of a vector space. Projectivity is essential: for $G=C_2$ over ${\mathbb{Z}}_2$, the trivial and sign lattices have zero Hom between them, whereas their reductions in characteristic $2$ coincide and have a one-dimensional Hom space.

The image of the linear map $A+B$ is contained in the sum of the images of $A$ and $B$. Since the dimension of a vector space of this sum is at most the sum of their dimensions, matrix rank is subadditive. Iteration shows that a sum of $r$ matrices of matrix rank at most one has matrix rank at most $r$, over any field.