Sergii StrelchukLink opens in a new windowLink opens in a new window (Cambridge)

Title: Insights in quantum complexity from classical simulation of quantum computation

Abstract: Given the difficulty of building and controlling large numbers of qubits, early applications of quantum algorithms are likely to involve both quantum and classical ingredients. One of the most active areas of quantum computing investigates the fundamental limits of computation which could be carried out in these systems by studying the trade-off possibilities between classical and quantum resources. Efficient classical simulation techniques enable us to better understand the power of quantum computing and settings where it will provide a genuine advantage. I will present three cases where efforts to classically simulate quantum computations in the ‘high complexity’ regime had remarkable consequences as they led to:

• new quantum circuit reduction (compression) techniques for general quantum circuits
• new sub-universal quantum computational models capable of performing efficient convolutions over permutation group Sn with applications to Quantum Approximate Optimization Algorithm
• novel techniques for simulating quantum circuits using efficient tensor network contraction algorithms with the worst-case subexponential upper bound on the runtime