Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Instytut Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 02.03.2021 w godzinach 9:30-11:00 via Internet, Webex https://ibm.webex.com/meet/tomasz.stopa
Adam Glos Institute of Theoretical and Applied Informatics, Polish Academy of Sciences
Bałtycka 5, 44-100 Gliwice, Poland
Temat: Space-efficient binary optimization for variational computing
In the era of Noisy Intermediate-Scale Quantum (NISQ) computers it is crucial to design quantum algorithms which do not require many qubits or deep circuits. Unfortunately, the most well-known quantum algorithms are too demanding to be run on currently available quantum devices. Moreover, even the state-of-the-art algorithms developed for the NISQ era often suffer from high space complexity requirements for particular problem classes. During the presentation, we show that it is possible to greatly reduce the number of qubits needed for the Travelling Salesman Problem (TSP), a paradigmatic optimization task, at the cost of having deeper variational circuits. We claim that the approach can be generalized for other problems where the standard bit-encoding is highly inefficient. Finally, we also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models. All the proposed encodings remain efficient to implement within the Quantum Approximate Optimization Algorithm framework.
The results presented will be a mixture of ideas from work , and the on-going project with project QProgMods (https://miszczak.eu/grants/qprogmods/) in collaboration with Z. Zimborás.
 A. Glos, A. Krawiec, and Z. Zimborás. "Space-efficient binary optimization for variational computing." arXiv preprint arXiv:2009.07309 (2020).