Qiskit Quantum Seminar

Currently Playing: Approximate Solutions of Combinatorial Problems via Quantum Relaxations | Qiskit Seminar Series

Approximate Solutions of Combinatorial Problems via Quantum Relaxations https://github.com/qiskit-community/prototype-qrao Your formal invite to weekly Qiskit videos ► https://ibm.biz/q-subscribe Speaker: Bryce Fuller Host: Olivia Lanes, PhD. Abstract: Combinatorial problems are formulated to find optimal designs within a fixed set of constraints. They are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization is to date an open problem. Here we propose new methods for producing approximate solutions for the maximum cut problem and its weighted version, which are based on relaxations to local quantum Hamiltonians. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and it is based on estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors Bio: Bryce Fuller is a Quantum Computing Applications Researcher at IBM Quantum. He joined IBM in 2019 after completing his Bachelors Degree in Electrical and Computer Engineering at the University of Texas at Austin–where his focus was in data science and machine learning. He is focused on the design and practical implementation of quantum algorithms for machine learning and optimization as well as the changing landscape of software used to design quantum algorithms. In addition to his research, Bryce is a subject matter expert on the IBM Quantum Prototypes team. -- The Qiskit Seminar Series is a deep dive into various academic and research topics within the quantum community. It will feature community members and leaders every Friday, 12 PM EDT.