New answers tagged complexity-theory
1
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 ...
1
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 ...
Top 50 recent answers are included
