yums seminar series
Circuit Mapping & Quantum Compilers (2/2)
Allen Mi
Recording
https://yale.zoom.us/rec/share/aF1aECfgm_RfndDv37YtrxGL173WfLcNvv5qhN1m6…
https://drive.google.com/drive/folders/1kc3LOCN4UueGB7ytVKAPNl1YPNeM-s3e…
Slides
https://drive.google.com/file/d/1vlizZj0cgFbwZnWoksjSGAJ_PGncshrR/view?u…
Abstract
As Moore’s Law nears its end, developing alternative, next-generation computing systems has become increasingly imperative. Quantum computers have emerged as one of the most promising complements to digital electronic computers. However, many challenges remain before scalable, general-purpose quantum computation can be achieved.
Last week, we learned the basics of quantum computing. We discussed how various systems of a quantum computer are organized under hierarchical layers. We defined the interconnect topology and architecture as abstractions of physical implementations. In the end, we highlighted the problem of mapping quantum circuits to concrete architectures.
This week, we start with the example of controlled-not mapping on a line graph. We demonstrate how this process achieves a “compilation” of gate sequences, and showcase a few theoretical and empirical results. Finally, we explore the open problems in circuit mapping and discuss abstractions of quantum algorithms beyond the circuit level.
Errata
Please contact Allen at allen.mi@yale.edu if you spot any error. I will deal with any report promptly.
The following errors are corrected in the updated slides:
-
Page 14: Direction of two $\mathrm{CNOT}$ gates is wrong.
Additionally, I provide the following clarifications:
-
At minute 35, there was some confusion on my part regarding the circuit depth of the $(4n-8)$-deep uni-directional map when the interconnect is in reverse direction. The gate depth when the interconnect is reversed is indeed $4n-6$. The extra two frames consists of the following. Other $H$ gates added for $\mathrm{CNOT}$ reversal can share a frame with existing $\mathrm{CNOT}$ gates, and therefore do not contribute to the circuit depth.
-
$H$ gates on the first and second qubits in the first frame
-
$H$ gates on the second and third qubits in the last frame
-
-
At minute 42, I was asked about whether the conclusion that arbitrary unitary matrices cannot be efficiently decomposed contradicts the Solovay-Kitaev theorem. I answered by stating that the Solovay-Kitaev theorem is limited to the single-qubit case. This answer is unsatisfactory, as the Solovay-Kitaev theorem also holds for multi-qubit cases. The real reason is that the Solovay-Kitaev theorem assumes the number of qubits to be constant, and produces an asymptotic bound with respect to the number of gates present in the circuit. The result regarding inefficient unitary matrix decomposition, however, produces an asymptotic bound with respect to the number of qubits.
- At minute 45, I claimed that one cannot use the $\mathrm{SWAP}$ gate as the only multi-qubit gate to construct a universal gate set. This claim is correct. However, it should be noted that one can use the three-qubit controlled-$\mathrm{SWAP}$ gate (also known as the $\mathrm{CSWAP}$ gate or Fredkin gate) with universal single-qubit gates, along with the use of ancilla qubits, to produce a universal gate set. To see the necessity of ancilla qubits, think about how the Toffoli gate can be simulated by this gate set.