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/1kc3LOCN4UueGB7ytVKAPNl1YPNeMs3e…
Slides
https://drive.google.com/file/d/1vlizZj0cgFbwZnWoksjSGAJ_PGncshrR/view?u…
Abstract
As Moore’s Law nears its end, developing alternative, nextgeneration 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, generalpurpose 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 controllednot 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 $(4n8)$deep unidirectional map when the interconnect is in reverse direction. The gate depth when the interconnect is reversed is indeed $4n6$. 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 SolovayKitaev theorem. I answered by stating that the SolovayKitaev theorem is limited to the singlequbit case. This answer is unsatisfactory, as the SolovayKitaev theorem also holds for multiqubit cases. The real reason is that the SolovayKitaev 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 multiqubit gate to construct a universal gate set. This claim is correct. However, it should be noted that one can use the threequbit controlled$\mathrm{SWAP}$ gate (also known as the $\mathrm{CSWAP}$ gate or Fredkin gate) with universal singlequbit 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.