We invite you to attend (remote-only) Episode XLII of the Warsaw Quantum Computing Group meetings! "Simultaneous resources reduction for quantum optimization"
Abstract from Adam:
The current state-of-the-art quantum algorithms for combinatorial optimization require representing the original problem as unconstrained binary optimization, where the objective function is a polynomial accepting binary string and outputting an objective value. Depending on the choice of the quantum algorithm, such representation is either embedded into a quantum annealer or simulated with a gate-based quantum computer. Unfortunately, such representation, especially when restricted to 2-local interactions, results in higher redundancy, significantly increasing the resources required. This is particularly important as the current and near-future quantum hardware is necessarily small and fragile to the noise.
We overcome this issue with an alternative way of encoding the problem into a quantum computer. Why our representation still relies on the bitstring input, making it suitable for current quantum devices with qubits, we significantly reduce the number of quantum resources needed, and for some problems like Max-K-Cut or Travelling Salesman Problem, our implementation reaches an almost optimal value for all cost measures simultaneously. These measures include but are not limited to a number of qubits, gates or the depth of the circuit. While presented for only special combinatorial problems, our approach is generic and will be particularly suitable for complicated constrained optimization problems.
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. Finally, Adam Glos is a member of QWorld Association where he coordinates QResearch department and coorganize remote internships programs QIntern.
This meeting is organized by the Quantum AI Foundation.