Institute of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
• 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
Tuesday, 2nd of March 2021, 9:30-11:00
Adam Glos Institute of Theoretical and Applied Informatics, Polish Academy of Sciences
Bałtycka 5, 44-100 Gliwice, Poland
Topic: 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).