In quantum computing, the basic unit of information is a qubit. Simulation of a general quantum program takes exponential time in the number of qubits, which makes simulation infeasible beyond 50 qubits on current supercomputers. So, for the understanding of larger programs, we turn to static techniques. In this paper, we present an abstract interpretation of quantum programs and we use it to automatically verify assertions in polynomial time. Our key insight is to let an abstract state be a tuple of projections. For such domains, we present abstraction and concretization functions that form a Galois connection and we use them to define abstract operations. Our experiments on a laptop have verified assertions about the Bernstein-Vazirani, GHZ, and Grover benchmarks with 300 qubits.
Thu 16 JunDisplayed time zone: Pacific Time (US & Canada) change
15:30 - 16:50 | |||
15:30 20mTalk | (OOPSLA 2020) A Model for Detecting Faults in Build Specifications SIGPLAN Track Thodoris Sotiropoulos Athens University of Economics and Business, Stefanos Chaliasos Imperial College London, Dimitris Mitropoulos University of Athens, Diomidis Spinellis Athens University of Economics and Business & Delft University of Technology | ||
15:50 20mTalk | (OOPSLA 2020) Unifying Execution of Imperative Generators and Declarative Specifications SIGPLAN Track Pengyu Nie University of Texas at Austin, Marinela Parovic University of Texas at Austin, Zhiqiang Zang University of Texas at Austin, Sarfraz Khurshid University of Texas at Austin, Aleksandar Milicevic Microsoft, Milos Gligoric University of Texas at Austin | ||
16:10 20mTalk | (PLDI 2021) Logical Bytecode Reduction SIGPLAN Track Christian Gram Kalhauge Technical University of Denmark, Jens Palsberg University of California, Los Angeles (UCLA) | ||
16:30 20mTalk | (PLDI 2021) Quantum abstract interpretation SIGPLAN Track Link to publication DOI Authorizer link Pre-print |