Schedule for: 16w5029 - Quantum Computer Science

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888

Magic state distillation is a critical component in leading proposals for fault-tolerant quantum computation. Relatively little is known, however, about how to construct a magic state distillation routine or, more specifically, which stabilizer codes are suitable for the task. While transversality of a non-Clifford gate within a code often leads to efficient distillation routines, it appears to not be a necessary condition. Here we have examined a number of small stabilizer codes and highlight a handful of which displaying interesting, albeit inefficient, distillation behaviour. Many of these distill noisy states right up to the boundary of the known undististillable region, while some distill toward non-stabilizer states that have not previously been considered. As a consequence of recent results, this implies that there is a family of quantum states that enable universality if and only if they exhibit contextuality with respect to stabilizer measurements.

Discussion of open problems in quantum circuits, quantum programming, quantum codes, fault-tolerant quantum computing, quantum architectures, quantum algorithms. Ideally, each participant would bring 1-2 open problems which can be his/her favorite grand challenge problem, pet peeve, brain teaser, or conjecture. During the week, there will be plenty of opportunity to interact with others to work on open problems.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

While quantum computers will need high-level, scalable programming languages in the upcoming decades, we need abstract, low-level programming languages now for the sophisticated experiments being performed with current quantum systems. Our quantum systems and associated experiments with tens of qubits have outstripped manual specification of the waveforms required to execute these sophisticated experiments. These experiments require sequences of 1000s of gates comprising 10s of waveforms with precise, synchronized execution across the qubits. Further, at the current time, qubit systems are a “sea of gates” over which many architectures are being designed and analyzed and every qubit needs a control signal at every clock cycle. In addition, we do not have the luxury of Von Neumann and other standard architecture concepts that greatly simplify the design of compilers, yet we desire the same abstract programming paradigms. With the QGL programming language, we are tackling this challenge. We are developing, and using, an abstract language with python-like programming constructs that we can compile to existing hardware and execute programs (experiments to physicists) on today’s qubit systems. Further, we can accommodate the “plug and play” of hardware components (e.g., AWGs and digitizers) with standard driver APIs.

When compiling high level programs into reversible circuits in a space efficient way it is desirable to allow for intermediate cleanup and ancilla reuse. We present a cleanup method based on tracking data dependencies and mutation within a program. Tracking is done using a representation that we call a "Mutable Dependency Diagram" (MDD). Using this representation we present an algorithm for intermediate (eager) cleanup. An incremental cleanup strategy related to Bennett's pebble game will also be presented. The MDD representation using the eager cleanup strategy has been implemented as a reversible circuit compiler (REVS). Numerical results based on this implementation will be discussed.

Due to the properties of reversibility, optimum synthesis with respect to the number of lines is a difficult task. For an irreversible Boolean function it is coNP-hard to find an optimum embedding, i.e., a reversible function with the minimum number of additional lines. Synthesis algorithms exists that obtain from an optimum embedding ancilla-free reversible circuits which have as many circuit lines as variables in the reversible function. However, so far all implementations for such synthesis algorithms require exponential time and space since they operate on the truth table representation of the function. In the talk, alternative implementations of the algorithms based on symbolic methods are presented that allow to run the algorithm in less space and time for some functions. It is shown that high quality synthesis results for large circuits can be obtained using these implementations.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Programming is error-prone. It is even worse when programming a quantum computer or designing quantum communication protocols, because human intuition is much better adapted to the classical world than to the quantum world. How can we build automatic tools for verifying correctness of quantum programs? A logic for verification of both partial correctness and total correctness of quantum programs was developed in our TOPLAS'2011 paper. The (relative) completeness of this logic was proved. Recently, a theorem prover for verification of quantum programs was built based on this logic [arXiv: 1601.03835]. To further develop automatic tools, we are working on techniques for invariant generation and synthesis of ranking functions for quantum programs.

Within the last few years improved algorithms, circuits and error bounds have led to substantial reductions in the costs of quantum chemistry simulation. Despite this progress two issues remain. First, the circuits have not been decomposed into a discrete gate set which makes the cost estimates unrealistic for a fault tolerant quantum computer. Second, given the success of classical methods such as DMRG and DFT, it is unclear whether a practical application exists for these simulation algorithms. Here we address both these problems by providing complete cost estimates for simulating the active space of Nitrogenase, which is a catalyst responsible for Nitrogen fixation that cannot be efficiently simulated to within chemical precision using known techniques. We will further show a new family of circuits for simulating quantum chemistry that can dramatically reduce the depth of the simulation.

Quantum++ is a general-purpose multi-threaded quantum computing library written in C++11 and composed solely of header files. The library is not restricted to qubit systems or specific quantum information processing tasks, being capable of simulating arbitrary quantum processes. The main design factors taken in consideration were ease of use, portability, and performance. http://arxiv.org/abs/1412.4704

We are currently engaged in a kickstarter campaign to crowd-source meQuanics, a game for optimising topological quantum circuits. Each puzzle in meQuanics represents a real quantum algorithm, which needs to be optimized for a quantum computer to be realized with real quantum devices. A fewer number of devices and a shorter run time increase our chance to build a real quantum computer. Reducing the resources necessary for a quantum computer is one of the most urgent and important problems to make this technology a reality. https://qis1.ex.nii.ac.jp/mequanics/en/

A variety of tools exist which can compile classical, irreversible code into reversible circuits. However, little effort has been spent on verifying these tools, potentially allowing compiler errors to cause incorrect results and negatively affect resource estimation. In this talk I will describe the design and implementation of a formally verified, optimizing reversible circuit compiler. Our compiler, called ReVer, compiles the simple ML-like language Revs to reversible circuits, with optimizations to reduce the number of ancilla bits used. We use the dependently typed language F* to verify with machine-checked proofs that ReVer compiles circuits that operate correctly with respect to the input program and cleans all temporary bits. Joint work with Martin Roetteler and Krysta Svore. http://arxiv.org/abs/1603.01635

Several breakthroughs in the analysis of quantum gates in U(2) can be linked to the tree structure of certain subgroups of U(2). When one moves to higher dimensions, these trees are replaced by Bruhat-Tits buildings, which are simplicial complexes with fascinating geometry. I will explain what these are and how they relate to navigating the group U(n).

Quaternary encoded binary circuits are more compact than their binary counterpart. Although quaternary reversible circuits are realizable, design of such circuits is still in its infancy. This work proposes a new, enhanced method of quaternary Galois field sum of products (QGFSOP) synthesis for quaternary quantum circuits. To achieve improved performance results, the algorithm makes use of 11 newly defined quaternary Galois field (QGF) expansions (for a total of 21 QGF expansions). This algorithm achieves QGFSOP minimization with the assistance of a pseudo-Kronecker Galois field decision diagram (QGFDD). This is a novel approach for QGFSOP synthesis. QGFSOP expressions are translated into quaternary quantum circuits by using newly developed quaternary quantum gate realizations optimized for quantum cost. Performance evaluation against existing works in the literature determined that are proposed method achieves an average QGFSOP expression product term savings of 32.66%. Toffoli gate realizations from the proposed gate library were found to achieve a minimum quantum cost savings of 39%. Other composite gate realizations either outperformed or matched existing realizations in terms of quantum cost.

Quipper is a functional programming language for quantum computing. In this tutorial, I will discuss Quipper's design rationale and give a practical demonstration.

< q|pic > is a system for preparing circuit diagrams in LaTeX, with an emphasis on diagrams used in quantum computing. The user prepares a description of the circuit in the human-readable "< q|pic > language": a Python program then converts this into LaTeX code using the TikZ graphics package. We give a brief overview of the capabilities of < q|pic > through a series of examples. Joint work with Tom Draper.

In this talk we will discuss topological circuit optimisation. This will start from the fundamental Clifford + T optimisation that occur at higher levels and then move into what is required for surface codes and 3D Raussendorf codes to integrate the algorithmic structure, ICM representation of a high level circuit and when required classical information in ancillary protocols becomes available. We will talk about probabilistic gate decomposition and what practical downsides they introduce. We will outline a first attempt at this that puts a preference on state distillation protocols and how they are integrated into large scale algorithms.

Besides being one of the most pristine qubits, the trapped ion technology provides novel ways to generate entanglement between ion qubits in the system. A technologically feasible architecture could enable construction of ion trap quantum computer systems on which a range of useful quantum algorithms can be effectively executed. We will discuss a scalable system architecture, a preliminary studies on the performance simulation on such an architecture, and experimental progress towards realization of a prototype system.

We give a new interactive protocol for the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in BQP has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional--i.e. it holds even for computationally unbounded provers. Compared to prior work, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffice. We also present a new soundness analysis, based on a reduction to an entanglement-based protocol. Reference: http://arxiv.org/abs/1509.09180

Stabilizer chains are a basic tool in computational group theory. We discuss how stabilizer chains and the corresponding transversals can be used to decompose reversible functions into elementary gates such as NOT, CNOT, and Toffoli. Several heuristics allow to find factorizations for any reversible function of reasonable length, though not minimal in general.

We present a method for exact circuit synthesis based on deterministic walks. We apply this method to construct a parallel framework for circuit synthesis, and implement one such version which performs optimal T-count synthesis over the Clifford+T gate set. We present several examples where parallelization offers a significant speedup on the run time, and breaks previous records for maximum achievable T-count.

We investigate the cost of Grover's quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms. We exhibit a T-optimized circuit for a pre-image attack on SHA-256 that is approximately $2^{149}$ surface code cycles deep and requires approximately $2^{13}$ logical qubits. This yields an overall cost of $2^{162}$ logical-qubit-cycles. Likewise, we exhibit a T-optimized SHA3-256 circuit that is approximately $2^{146}$ surface code cycles deep and requires approximately $2^{16}$ logical qubits for a total cost of, again, $2^{162}$ logical-qubit-cycles. Both attacks require on the order of $2^{128}$ queries in a quantum black-box model, hence our results suggest that executing these attacks may be as much as $17$ billion times more expensive than one would expect from the simple query analysis. http://arxiv.org/abs/1603.09383

LIQUi|> provides a modular software architecture for the simulation of quantum algorithms. It provides a high level interface and is independent of a specific quantum architecture. Recently we’ve released LIQUi|> to the public for academic use. It is a free package that runs on Windows, Linux and OSX as a provided executable with built-in examples and sample scripts as well as a development environment (using Visual Studio or mono, also freely available) that allows the user to compile their own quantum algorithms into an executable. The package includes a User’s Manual as well as over 700 pages of API documentation. This tutorial will focus on: -obtaining and installing the package from http://stationq.github.io/Liquid/ -obtaining and installing Visual Studio and mono as development environments (best for attendees to do this beforehand following instructions on the above web site, see “Getting Started”) -getting the system running using built in examples (e.g., Shor) -how to draw circuits (e.g., Teleport) -editing, compiling and running your own circuit (step-by-step) -use of scripting (e.g., controlling and creating Quantum Chemistry tests) -overview of documentation (User’s Manual, API docs, Videos, GitHub community)

In this talk, I will turn to the question of logical resource estimation for quantum programs in the quantum programming language Quipper. In the current implementation, gatecount can be obtained automatically for fixed size of circuits. I will present a static analysis tool for obtaining resource estimation parametric on the parameters fed to the program. I will discuss the conditions for this gate count to be in closed form.

In this talk I will show that minimizing T-count in n-qubit CNOT and T quantum circuits reduces to minimum distance decoding of the length $2^n-1$ punctured Reed-Muller code of order $n-4$. A converse reduction also exists, providing strong evidence that no polynomial-time solution is possible. As a consequence, we derive an algorithm for the optimization of T-count in Clifford+T circuits which can utilize the wide variety of Reed-Muller decoders developed over the years, along with a new upper bound on the number of T gates required to implement a unitary over CNOT and T gates. I will further generalize this result to show that minimizing finer angle Z-rotations corresponds to decoding lower order binary Reed-Muller codes. Joint work with Michele Mosca.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.