log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Quantum Abstract Interpretation
Le Chang - UMD
Monday, November 15, 2021, 11:30 am-12:30 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

In quantum computing, the basic unit of information is a
qubit. Simulation of a general quantum program takes ex-
ponential time in the number of qubits, which makes simu-
lation infeasible beyond 50 qubits on current supercomput-
ers. So, for the understanding of larger programs, we turn to
static techniques. In this paper, we present an abstract inter-
pretation of quantum programs and we use it to automati-
cally verify assertions in polynomial time. Our key insight is
to let an abstract state be a tuple of projections. For such do-
mains, we present abstraction and concretization functions
that form a Galois connection and we use them to define ab-
stract operations. Our experiments on a laptop have verified
assertions about the Bernstein-Vazirani, GHZ, and Grover
benchmarks with 300 qubits.

This talk is organized by Deena Postol