Institute of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
Objectives:
• understand and discuss current problems in quantum informatics,
• discuss new quantum computing technologies,
• exchange ideas and research results,
• integrate information across different research teams,
• build a community around quantum informatics.
Venue: via Internet, Webex https://ibm.webex.com/meet/tomasz.stopa
Program: Tuesday, 12th April 2022, 9:35-11:00
Adam Glos, Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Gliwice, PL
Topic: Optimal QAOA design for the Traveling Salesman Problem
PresentationAbstract:
Combinatorial Optimization is a potential candidate for achieving quantum advantage in the Noisy Intermediate-Scale Quantum era. Quantum Approximate Optimization Algorithm (QAOA) is a promising algorithm that may provide solutions to these problems faster than its classical counterparts. Unfortunately, QAOA requires that the problem Hamiltonian is implemented in the circuit, thus directly affecting the resources required. For example, for the Travelling Salesman Problem (TSP) all the known implementations require either O(n^2) number of qubits or O(n^2) depth. We show that this limitation can be broken through the use of simulated QAOA, where instead of applying each Pauli term independently, a quantum version of classical pseudocode is implemented, using only O(n log(n)) number of qubits and O(n polylog(n)) depth, even on the LNN architecture. In fact, other significant cost measures such as the number of gates, trainable gates or energy span are also optimized. Our results are the first which show significant improvement over state-of-the-art problem Hamiltonian implementation for TSP.
Bio: Adam Glos is a PhD researcher working in the Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, and the Finnish start-up Algorithmiq. His research area covers the NISQ-era oriented optimization, with a particular focus on the efficient representations for the currently most prominent quantum algorithms.