Write a Blog >>
SPLASH 2019
Sun 20 - Fri 25 October 2019 Athens, Greece
Wed 23 Oct 2019 17:07 - 17:30 at Attica - Formalization Chair(s): Eric Koskinen

In 2016, the first quantum processors have been made available to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, such possibility also brought challenges. One challenge is the so called Qubit Allocation problem: the mapping of a virtual quantum circuit into an actual quantum architecture. There exist solutions to this problem; however, in our opinion, they fail to capitalize on decades of improvements on graph theory. In contrast, this paper shows how to model qubit allocation as the combination of Subgraph Isomorphism and Token Swapping. This idea has been made possible by the publication of an approximative solution to the latter problem in 2016. We have compared our algorithm against five other qubit allocators, all independently designed in the last two years, including the winner of the IBM Challenge. When evaluated in "Tokyo", a quantum architecture with 20 qubits, our technique outperforms these state-of-the-art approaches in terms of the quality of the solutions that it finds and the amount of memory that it uses, while showing practical runtime.

Wed 23 Oct

Displayed time zone: Beirut change

16:00 - 17:30
FormalizationOOPSLA at Attica
Chair(s): Eric Koskinen Stevens Institute of Technology
16:00
22m
Talk
Formal Foundations of Serverless ComputingACM SIGPLAN Distinguished Paper Award
OOPSLA
Abhinav Jangda University of Massachusetts Amherst, Donald Pinckney University of Massachusetts Amherst, Yuriy Brun University of Massachusetts Amherst, Arjun Guha University of Massachusetts, Amherst
Link to publication DOI Pre-print
16:22
22m
Talk
A Formalization of Java’s Concurrent Access Modes
OOPSLA
John Bender University of California, Los Angeles, Jens Palsberg University of California, Los Angeles
DOI
16:45
22m
Talk
A Path to DOT: Formalizing Fully Path-Dependent Types
OOPSLA
Marianna Rapoport University of Waterloo, Ondřej Lhoták University of Waterloo
DOI Pre-print Media Attached
17:07
22m
Talk
Qubit Allocation as a Combination of Subgraph Isomorphism and Token Swapping
OOPSLA
DOI Pre-print