Timeline for Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2023 at 12:35 | history | edited | Mark Spinelli | CC BY-SA 4.0 |
added 116 characters in body
|
| May 2, 2023 at 12:31 | comment | added | Mark Spinelli | Yeah, I think you're right; sorry for my carelessness. $\pi_i(G)$ is meant to be another adjacency matrix having the $i$th permutation applied to $G$. We can't disentangle the permutation from the output of the permutation. I'll edit it again for clarity. | |
| May 2, 2023 at 6:10 | comment | added | Andrew Baker | I just noticed this: in your second equation, shouldn't the state be $\frac{1}{\sqrt{N!}} \sum_{i = 1}^{N!} | \pi_i \rangle | \pi_i (G) \rangle$ ? Because $\pi_i$ is the input, not $G$. | |
| Apr 29, 2023 at 18:29 | vote | accept | Andrew Baker | ||
| Apr 29, 2023 at 18:29 | comment | added | Andrew Baker | Oh, I get it now. We need $N!$ qubit states, and thus need $log(N!)$ qubits. Because $O(N!) = O(N log N)$, this is "efficient." (efficient meaning polynomial number of qubits). | |
| Apr 29, 2023 at 18:08 | comment | added | Mark Spinelli | You’re right, my normalization factor was wrong. If there are N vertices there are up to N! different adjacency matrices. | |
| Apr 29, 2023 at 18:06 | history | edited | Mark Spinelli | CC BY-SA 4.0 |
deleted 12 characters in body
|
| Apr 29, 2023 at 17:29 | comment | added | Andrew Baker | Doesn’t your method require $N!$ qubits though? The $N$ I am referring to is the number of nodes of the graph. Shouldn’t this be disallowed, as $N!$ is not efficient? | |
| Apr 29, 2023 at 16:49 | history | answered | Mark Spinelli | CC BY-SA 4.0 |