Schedule for: 24w5307 - Quantum Circuit Design Automation

Beginning on Sunday, June 2 and ending Friday June 7, 2024

All times in UBC Okanagan, Canada time, PDT (UTC-7).

Sunday, June 2
16:00 - 23:00 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk Nechako Residence)
20:00 - 22:00 Informal gathering (Lounge)
Monday, June 3
08:00 - 08:45 Breakfast
Please use the meal card and get the breakfast items from Comma(or any food merchants)
(UBC Okanagan - Food services)
08:45 - 09:00 Introduction and Welcome by BIRS-UBCO Staff (Main Meeting Room - ARTS 110)
09:00 - 09:15 Opening remarks (Main Meeting Room - ARTS 110)
09:15 - 09:45 Frank Fu: Modalities in Proto-Quipper
Quantum circuit description languages usually provide language constructs to enable programmers to perform certain operations on a given circuit. For example, controlling a circuit, reverse a circuit, or boxing a circuit. When these operations fail, e.g., controlling an uncontrollable circuit, runtime errors are thrown. In this talk, I will report on how Proto-Quipper uses a notion of modality in type system to incorporate these operations. As a result, failures can be detected at compile time via type checking.
(Main Meeting Room - ARTS 110)
09:45 - 10:15 Eddie Schoute: Minimal entanglement for injecting diagonal gates
Non-Clifford gates are frequently exclusively implemented on fault-tolerant architectures by first distilling magic states in specialised magic-state factories. In the rest of the architecture, the computational space, magic states can then be consumed by a stabilizer circuit to implement non-Clifford operations. We show that the connectivity between the computational space and magic state factories forms a fundamental bottleneck on the rate at which non-Clifford operations can be implemented. We show that the nullity of the magic state, $\nu(|D\rangle)$ for diagonal gate $D$, characterizes the non-local resources required to implement $D$ in the computational space. As part of our proof, we construct local stabilizer circuits that use only $\nu(|D\rangle)$ ebits to implement $D$ in the computational space that may be useful to reduce the non-local resources required to inject non-Clifford gates. Another consequence is that the edge-disjoint path compilation algorithm [arXiv:2110.11493] produces minimum-depth circuits for implementing single-qubit diagonal gates.
(Main Meeting Room - ARTS 110)
10:15 - 10:45 Coffee Break (ARTS 112)
10:30 - 11:30 Open problems 1 (Main Meeting Room - ARTS 110)
11:30 - 13:00 Lunch (ARTS 112)
13:00 - 15:00 Discussion session 1 (Main Meeting Room - ARTS 110)
15:00 - 15:30 Coffee Break (ARTS 112)
15:30 - 17:30 Discussion session 2 (Main Meeting Room - ARTS 110)
17:30 - 18:00 Shuttle bus : UBCO Eme building - Parking lot
Please meet up at the parking lot.
(Other - See Description)
18:00 - 20:00 Dinner (Four Points Hotel)
Tuesday, June 4
08:00 - 09:00 Breakfast
Please use the meal card and get the breakfast items from Comma(or any food merchants)
(UBC Okanagan - Food services)
09:00 - 09:30 Adam Sawicki: Efficiency of quantum gate-sets and random t-designs
Approximate t-design are ensembles of unitaries that (approximately) recover Haar averages of polynomials in entries of unitaries up to the order t. As such, they find numerous applications throughout quantum information, including randomized benchmarking and efficient estimation of properties of quantum states. The epsilon-efficiency of a universal set of quantum gates is typically measured by the length of a circuit needed to approximate any quantum transformation with an epsilon precision. In this talk I will discuss efficiency of random gate sets relating it to the notion of t-designs. The talk will be based on: P. Dulian, A. Sawicki, A random matrix model for random approximate t-designs, IEEE Transactions on Information Theory, vol. 70, no. 4, pp. 2637-2654, (2024) and P. Dulian, A. Sawicki, Matrix concentration inequalities and efficiency of random universal sets of quantum gates, Quantum 7, 983 (2023)
(Main Meeting Room - ARTS 110)
09:30 - 10:00 Lucas Stinchcombe: Polynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algorithm
We show that Roetteler’s shifted bent function algorithm is polynomial-time simulable when implemented by the construction of Bravyi and Gosset. We do this by giving a classical simulation procedure based on symbolic rewriting of a circuit’s sum-over-paths and show that every sequence of rewrites terminates with the hidden the shift in time polynomial in the volume of the circuit.
(Main Meeting Room - ARTS 110)
10:00 - 10:30 Coffee Break (ARTS 112)
10:30 - 11:00 Simon Perdrix: Quantum circuit completeness
I will present an equational theory for quantum circuits that we have proven to be both complete—meaning any true equation can be derived using the rules of the language—and minimal, as no rule can be derived from the others.
(Main Meeting Room - ARTS 110)
11:00 - 11:30 Greg Kuperberg: Breaking the cubic barrier in the Solovay-Kitaev algorithm
The topic of quantum circuit compilation began with the Solovay-Kitaev theorem and algorithm. Given a target element g in SU(d) and an arbitrary universal gate set A, the foundational result says that there is a word w in A that ε-approximates g that has length polylog(1/ε) and can be found in polynomial time. Kitaev, Shen, and Vyalyi later established an O(log(1/ε)3+δ) word length bound for every d and for every δ > 0. For certain special gate sets such as Clifford+T, there are number-theoretic algorithms with an O(log(1/ε)) word length bound, but the exponent for general gate sets remains interesting. In this talk, I will discuss a new algorithm for general gate sets with an O(log(1/ε)α) word length bound, where α = logϕ(2)+δ = 1.44042...+δ and ϕ = (1+√5)/2 is the golden ratio.
(Online - UBCO)
11:30 - 13:00 Lunch (ARTS 112)
13:00 - 13:15 Group photo (Main Meeting Room - ARTS 110)
13:15 - 15:00 Discussion session 3 (Main Meeting Room - ARTS 110)
15:00 - 15:30 Coffee Break (ARTS 112)
15:30 - 17:30 Discussion session 4 (Main Meeting Room - ARTS 110)
17:30 - 18:00 Shuttle bus : UBCO Eme building - Parking lot
Please meet up at the parking lot.
(Other - See Description)
18:00 - 20:00 Dinner (Four Points Hotel)
Wednesday, June 5
08:00 - 09:00 Breakfast
Please use the meal card and get the breakfast items from Comma(or any food merchants)
(UBC Okanagan - Food services)
09:00 - 09:30 Day 2 Discussion Summary (Main Meeting Room - ARTS 110)
09:30 - 10:00 Nadish de Silva: Efficiently achieving fault-tolerant qudit quantum computation via gate teleportation
Quantum computers operate by manipulating quantum systems that are particularly susceptible to noise. Classical redundancy-based error correction schemes cannot be applied as quantum data cannot be copied. These challenges can be overcome by using a variation of the quantum teleportation protocol to implement those operations which cannot be easily done fault-tolerantly. This process consumes expensive resources called 'magic states'. The vast quantity of these resources states required for achieving fault-tolerance is a significant bottleneck for experimental implementations of universal quantum computers. I will discuss a program of finding and classifying those quantum operations which can be performed with efficient use of magic state resources. I will focus on the understanding of not just qubits but also the higher-dimensional 'qudit' case. This is motivated by both practical reasons and for the resulting theoretical insights into the ultimate origin of quantum computational advantages. Research into these quantum operations has remained active from their discovery twenty-five years ago to the present. Our approach introduces the novel use of tools from algebraic geometry.
(Main Meeting Room - ARTS 110)
10:00 - 10:30 Coffee Break (ARTS 112)
10:30 - 11:00 Robert Rand: Verifying Graphical Quantum Calculi in a Proof Assistant
We aim to verify the ZX-calculus, a powerful tool for representing and reasoning about quantum computation. ZX-diagrams are typically represented as adjacency-based graphs, reflecting the guiding principle that “only connectivity matters”. In the context of formal theorem provers like Coq, however, such graphs are difficult to reason about, especially when we seek to give them semantics. To address this gap, we introduce VyZX, a verified library for reasoning about the ZX-calculus, using inductive constructs that arise naturally from category theoretic definitions. We extend VyZX to reason about a variety of monoidal categories, provided they satisfy an appropriate set of coherence conditions.
(Main Meeting Room - ARTS 110)
11:00 - 11:30 Andrew Glaudell: Catalytic Embeddings (Main Meeting Room - ARTS 110)
11:30 - 13:00 Lunch (ARTS 112)
13:00 - 17:30 Free Afternoon (Kelowna)
17:30 - 19:00 Dinner (ARTS 112)
Thursday, June 6
08:00 - 09:00 Breakfast
Please use the meal card and get the breakfast items from Comma(or any food merchants)
(UBC Okanagan - Food services)
09:00 - 09:30 Nils Quetschlich: The Munich Quantum Toolkit (MQT) - A Summary of Design Automation Tools and Software for Quantum Computing
Quantum computers are becoming a reality and numerous quantum computing applications with a near-term perspective (e.g., for finance, chemistry, machine learning, and optimization) and with a long-term perspective (e.g., for cryptography or unstructured search) are currently being investigated. However, designing and realizing potential applications for these devices in a scalable fashion requires automated, efficient, and user-friendly software tools that cater to the needs of end users, engineers, and physicists at every level of the entire quantum software stack. Many of the problems to be tackled in that regard are similar to design problems from the classical realm for which sophisticated design automation tools have been developed in the previous decades. The Munich Quantum Toolkit (MQT) is a collection of software tools for quantum computing developed by the Chair for Design Automation at the Technical University of Munich which explicitly utilizes this design automation expertise. Our overarching objective is to provide solutions for design tasks across the entire quantum software stack. This entails high-level support for end users in realizing their applications, efficient methods for the classical simulation, compilation, and verification of quantum circuits, tools for quantum error correction, support for physical design, and more. These methods are supported by corresponding data structures (such as decision diagrams) and core methods (such as SAT encodings/solvers). All of the developed tools are available as open-source implementations and are hosted on github.com/cda-tum.
(Main Meeting Room - ARTS 110)
09:30 - 10:00 Sarah Meng Li: Improving the Fidelity of CNOT Circuits on NISQ Hardware
We introduce an improved CNOT synthesis algorithm that considers nearest-neighbour interactions and CNOT gate error rates in noisy intermediate-scale quantum (NISQ) hardware. Our contribution is twofold. First, we define a cost function $c$ by approximating the average gate fidelity $F_{avg}$. According to the simulation results, $c$ fits the error probability of a noisy CNOT circuit, $P = 1 - F_{avg}$, much tighter than the commonly used cost functions. On IBM's fake Nairobi backend, it fits $P$ with an error at most $10^{-3}$. On other backends, it fits $P$ with an error at most $10^{-1}$. $c$ accounts for the machine calibration data and accurately quantifies the dynamic error characteristics of a NISQ-executable CNOT circuit. It circumvents the computation complexity of calculating $F_{avg}$ and shows remarkable scalability. Second, we propose an architecture-aware CNOT synthesis algorithm, NAPermRowCol, by adapting the leading Steiner-tree-based connectivity-aware CNOT synthesis algorithms. A weighted edge is used to encode a CNOT gate error rate and $c$-instructed heuristics are applied to each reduction step. Compared to IBM's Qiskit compiler, it reduces $c$ by a factor of 2 on average (up to a factor of 8.8). It lowers the synthesized CNOT count by a factor of 13 on average (up to a factor of 162). Compared with algorithms that are noise-agnostic, NAPermRowCol improves the fidelity of a synthesized CNOT circuit across varied NISQ hardware. Depending on the benchmark circuit and the IBM backend selected, it lowers the synthesized CNOT count up to $56.95\%$ compared to ROWCOL and up to $21.62\%$ compared to PermRowCol. It reduces the synthesis $c$ up to $25.71\%$ compared to ROWCOL and up to $9.12\%$ compared to PermRowCol. NAPermRowCol does not use ancillary qubits and is not restricted to certain initial qubit maps. It could be generalized to route a more complicated quantum circuit, and eventually boost the overall efficiency and accuracy of quantum computing on NISQ devices. Joint-work With: Dohun Kim, Minyoung Kim, and Michele Mosca
(Main Meeting Room - ARTS 110)
10:00 - 10:30 Coffee Break (ARTS 112)
10:30 - 11:30 Open problems 2 (Main Meeting Room - ARTS 110)
11:30 - 13:00 Lunch (ARTS 112)
13:00 - 15:00 Discussion session 5 (Main Meeting Room - ARTS 110)
15:00 - 15:30 Coffee Break (ARTS 112)
15:30 - 17:30 Discussion session 6 (Main Meeting Room - ARTS 110)
17:30 - 18:00 Shuttle bus : UBCO Eme building - Parking lot
Please meet up at the parking lot.
(Other - See Description)
18:00 - 20:00 Dinner (Four Points Hotel)
Friday, June 7
08:00 - 09:00 Breakfast
Please use the meal card and get the breakfast items from Comma(or any food merchants)
(UBC Okanagan - Food services)
09:00 - 10:00 Benchmarking (Main Meeting Room - ARTS 110)
10:00 - 10:30 Coffee Break (ARTS 112)
10:30 - 11:30 Closing session (Main Meeting Room - ARTS 110)
10:30 - 11:00 Checkout by 11AM (Front Desk Nechako Residence)
11:30 - 13:00 Lunch (ARTS 112)