23/06/2021

Quantum Abstract Interpretation

Nengkun Yu, Jens Palsberg

Keywords: quantum programming, scalability, abstract interpretation

Abstract Paper Code Similar Papers

Abstract: 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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38956286
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at PLDI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 2:33 
 0
 0
 0
 0
 14:12 
 0
 0
 0
 0
 15:46 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 10:26 
 0
 0
 0
 0
 15:22 
 0
 0
 0
 0
 13:27 
 0
 0
 0
 0
 18:06 
 0
 0
 0
 0
 12:07 
 0
 0
 0
 0
 12:34 
 0
 0
 0
 0
 7:09 
 0
 0
 0
 0
 4:58 
 0
 0
 0
 0
 16:51 
 0
 0
 0
 0
 5:09 
 0
 0
 0
 0
 3:26 
 0
 0
 0
 0
 4:57 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 16:25 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 18:07 
 0
 0
 0
 0
 13:09 
 0
 0
 0
 0
 11:33 
 0
 0
 0
 0
 22:04 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 27:04 
 0
 0
 0
 0
 14:26 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 6:17 
 0
 0
 0
 0
 15:12 
 0
 0
 0
 0
 15:30 
 0
 0
 0
 0
 5:24 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 5:39 
 0
 0
 0
 0
 3:04 
 0
 0
 0
 0
 21:16 
 0
 0
 0
 0
 15:46 
 0
 0
 0
 0
 15:28 
 0
 0
 0
 0
 2:54