Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2402.05874 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916744712421376 |
|---|---|
| author | Kumabe, Soh Mori, Ryuhei Yoshimura, Yusei |
| author_facet | Kumabe, Soh Mori, Ryuhei Yoshimura, Yusei |
| contents | In this work, we study the complexity of graph-state preparation. We consider general quantum algorithms consisting of Clifford operations acting on at most two qubits for graph-state preparations. We define the CZ-complexity of a graph state $|G\rangle$ as the minimum number of two-qubit Clifford operations (excluding single-qubit Clifford operations) for generating $|G\rangle$ from a trivial state $|0\rangle^{\otimes n}$. We first prove that a graph state $|G\rangle$ is generated by at most $t$ two-qubit Clifford operations if and only if $|G\rangle$ is generated by at most $t$ controlled-Z (CZ) operations. We next prove that a graph state $|G\rangle$ is generated from another graph state $|H\rangle$ by $t$ CZ operations if and only if the graph $G$ is generated from $H$ by some combinatorial graph transformation with cost $t$. As the main results, we show a connection between the CZ-complexity of graph state $|G\rangle$ and the rank-width of the graph $G$. Indeed, we prove that for any graph $G$ with $n$ vertices and rank-width $r$,
1. The CZ-complexity of $|G\rangle$ is $O(rn)$.
2. If $G$ is connected, the CZ-complexity of $|G\rangle$ is at least $n + r - 2$.
We also demonstrate the existence of graph states whose CZ-complexities are close to the upper and lower bounds. Finally, we present quantum algorithms for preparing graph states for three specific graph classes related to intervals: interval graphs, interval containment graphs, and circle graphs. We prove that the CZ-complexity is $O(n)$ for interval graphs, and $O(n\log n)$ for both interval containment graphs and circle graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05874 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of graph-state preparation by Clifford circuits Kumabe, Soh Mori, Ryuhei Yoshimura, Yusei Quantum Physics In this work, we study the complexity of graph-state preparation. We consider general quantum algorithms consisting of Clifford operations acting on at most two qubits for graph-state preparations. We define the CZ-complexity of a graph state $|G\rangle$ as the minimum number of two-qubit Clifford operations (excluding single-qubit Clifford operations) for generating $|G\rangle$ from a trivial state $|0\rangle^{\otimes n}$. We first prove that a graph state $|G\rangle$ is generated by at most $t$ two-qubit Clifford operations if and only if $|G\rangle$ is generated by at most $t$ controlled-Z (CZ) operations. We next prove that a graph state $|G\rangle$ is generated from another graph state $|H\rangle$ by $t$ CZ operations if and only if the graph $G$ is generated from $H$ by some combinatorial graph transformation with cost $t$. As the main results, we show a connection between the CZ-complexity of graph state $|G\rangle$ and the rank-width of the graph $G$. Indeed, we prove that for any graph $G$ with $n$ vertices and rank-width $r$, 1. The CZ-complexity of $|G\rangle$ is $O(rn)$. 2. If $G$ is connected, the CZ-complexity of $|G\rangle$ is at least $n + r - 2$. We also demonstrate the existence of graph states whose CZ-complexities are close to the upper and lower bounds. Finally, we present quantum algorithms for preparing graph states for three specific graph classes related to intervals: interval graphs, interval containment graphs, and circle graphs. We prove that the CZ-complexity is $O(n)$ for interval graphs, and $O(n\log n)$ for both interval containment graphs and circle graphs. |
| title | Complexity of graph-state preparation by Clifford circuits |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2402.05874 |