Data Structures for Quantum Information (Delivered in English)
- LecturerProf. Alfons Laarman (Leiden University)
Host: Yu-Fang Chen - Time2024-01-11 (Thu.) 10:00 ~ 12:00
- Location資訊所新館101會議室 , Auditorium 101 at IIS new Building
Live Stream
https://meet.google.com/ajf-cjoi-axa
Abstract
On the road towards quantum supremacy, to deal with noisy and frugile hardware, an essential component is quantum circuit compilation, which entails quantum circuit simulation, optimization, verification and synthesis. Circuit compilation hinges on efficient methods for the (classical) representation of quantum states and the simulation of quantum operations on these representations. This talk focuses on various promising methods: the stabilizer formalism and its generalizations, decision diagrams (DDs), matrix product states (MPS; a specific type of tensor network) and restricted Boltzmann machines (RBMs).
First, we show that states represented in the stabilizer formalism can be exponentially more succinct than in DDs. This is surprising, given that the stabilizer formalism is non-universal for quantum computing and classically simulatable. To remedy this, we introduce a more powerful decision diagram variant, called Local Invertible Map-DD (LIMDD). We prove that the set of quantum states represented by poly-sized LIMDDs strictly contains the union of stabilizer states and other decision diagram variants.
Second, we analyze the performance of the simulation of quantum circuits with LIMDDs comparing to the state-of-the-art simulation paradigms based on stabilizer decomposition techniques for Clifford + T circuits. We give circuits which LIMDDs can efficiently simulate, while the stabilizer decomposition techniques cannot. This shows that LIMDDs successfully unite the strengths of two state-of-the-art approaches. LIMDDs thus pave the way for fundamentally more powerful solutions for simulation and analysis of quantum computing as confirmed by a prototype implementation of the LIMDD data structure.
Finally, we analytically investigate various widely-used data structures for quantum state representation: matrix product states (MPS), decision diagrams (DDs) and restricted Boltzmann machines (RBMs). We map the relative succinctness of these data structures and provide the complexity for all relevant query and manipulation operations. Highlights include exponential separations between the succinctness of LIMDD, MPS and RBM, while other DDs turn out to be at least as succinct as LIMDD and MPS. We also show that the inner product and fidelity cannot be computed in polynomial time for LIMDD and RBM representations unless P = NP. Moreover, we provide translations that demonstrate that MPS-based simulation is never slower than DD-based simulation, excluding LIMDD. Together this yields a first “knowledge compilation map” for quantum information, which contributes to the understanding of the inherent time and space efficiency trade-offs in circuit compilation tasks.
First, we show that states represented in the stabilizer formalism can be exponentially more succinct than in DDs. This is surprising, given that the stabilizer formalism is non-universal for quantum computing and classically simulatable. To remedy this, we introduce a more powerful decision diagram variant, called Local Invertible Map-DD (LIMDD). We prove that the set of quantum states represented by poly-sized LIMDDs strictly contains the union of stabilizer states and other decision diagram variants.
Second, we analyze the performance of the simulation of quantum circuits with LIMDDs comparing to the state-of-the-art simulation paradigms based on stabilizer decomposition techniques for Clifford + T circuits. We give circuits which LIMDDs can efficiently simulate, while the stabilizer decomposition techniques cannot. This shows that LIMDDs successfully unite the strengths of two state-of-the-art approaches. LIMDDs thus pave the way for fundamentally more powerful solutions for simulation and analysis of quantum computing as confirmed by a prototype implementation of the LIMDD data structure.
Finally, we analytically investigate various widely-used data structures for quantum state representation: matrix product states (MPS), decision diagrams (DDs) and restricted Boltzmann machines (RBMs). We map the relative succinctness of these data structures and provide the complexity for all relevant query and manipulation operations. Highlights include exponential separations between the succinctness of LIMDD, MPS and RBM, while other DDs turn out to be at least as succinct as LIMDD and MPS. We also show that the inner product and fidelity cannot be computed in polynomial time for LIMDD and RBM representations unless P = NP. Moreover, we provide translations that demonstrate that MPS-based simulation is never slower than DD-based simulation, excluding LIMDD. Together this yields a first “knowledge compilation map” for quantum information, which contributes to the understanding of the inherent time and space efficiency trade-offs in circuit compilation tasks.