# Tag Info

Suppose we are given the ($n\times n$ adjacency matrix $M_0$ of graph $G_0$ and $M_1$ of graph $G_1$, and we wish to know whether $G_0\simeq G_1$. It is a folklore result that if we can prepare states: $$\vert\alpha_G\rangle=\sum\limits_{\sigma\in S_n}\vert \sigma (G)\rangle,$$ with $S_n$ being the symmetric group on $n$ elements, we can prepare such a ...
CW from self-answer, and also because this is more of an extended comment than an answer. Let $A$ be the adjacency matrix of the Cayley graph of our group $\mathcal{H}$ of order $N$. Notice that $A$ is square-hermitian. Further let $\mathbb{I}_N$ be the $N\times N$ identity matrix. It occurs to me that I am, in a sense, asking to prepare the ground state $... 6 Following Dehaene and de Moor (Theorem 6 in particular), every Clifford unitary can be represented (up to a global scalar factor) by an expression of the form$$U = 2^{-k/2} \!\!\!\!\!\!\sum_{\substack{x_r,x_c \in \{0,1\}^k \\ x_b \in \{0,1\}^{n-k}}}\!\!\!\!\! i^{p(x_b,x_c,x_r)} (-1)^{q(x_b,x_c,x_r)} \bigl\lvert T_1[x_r;x_b] \bigr\rangle\!\bigl\langle T_2[... 7 Here's a simple strategy based on the idea that Clifford operations conjugate Pauli products into other Pauli products. If$U$is a Clifford operation, then$U P U^\dagger$(where$P$is a Pauli operation on one of the qubits) will be a matrix equivalent to a product of Pauli operations. If you check this for each$X_q$and$Z_q$for each qubit$q$, the ... 5 I see maybe four (4) ways to interpret the question. The first asks whether we can use a quantum computer to efficiently solve$\mathsf{NP}$problems. The class of problems efficiently solvable by a quantum computer is called$\mathsf{BQP}$, and so the question would ask whether$\mathsf{NP}\subseteq\mathsf{BQP}\$. As is indicted in the comments, quantum ...