Schedule for: 24w5307 - Quantum Circuit Design Automation

Please use the meal card and get the breakfast items from Comma(or any food merchants)

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.

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.

Please meet up at the parking lot.

Please use the meal card and get the breakfast items from Comma(or any food merchants)

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)

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.

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.

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.

Please meet up at the parking lot.

Please use the meal card and get the breakfast items from Comma(or any food merchants)

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.

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.

Please use the meal card and get the breakfast items from Comma(or any food merchants)

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.

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

Please meet up at the parking lot.

Please use the meal card and get the breakfast items from Comma(or any food merchants)