Reinforcement Learning Assisted Recursive QAOA

Yash J. Patel, Sofiene Jerbi, Thomas Bäck, Vedran Dunjko

Jul 14 2022 quant-ph cs.AI cs.LG arXiv:2207.06294v1

Scite!7  PDF

Variational quantum algorithms such as the Quantum Approximation Optimization Algorithm (QAOA) in recent years have gained popularity as they provide the hope of using NISQ devices to tackle hard combinatorial optimization problems. It is, however, known that at low depth, certain locality constraints of QAOA limit its performance. To go beyond these limitations, a non-local variant of QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of approximate solutions. The RQAOA has been studied comparatively less than QAOA, and it is less understood, for instance, for what family of instances it may fail to provide high quality solutions. However, as we are tackling NPNP-hard problems (specifically, the Ising spin model), it is expected that RQAOA does fail, raising the question of designing even better quantum algorithms for combinatorial optimization. In this spirit, we identify and analyze cases where RQAOA fails and, based on this, propose a reinforcement learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly better on these identified instances where RQAOA underperforms, and is similarly performing on instances where RQAOA is near-optimal. Our work exemplifies the potentially beneficial synergy between reinforcement learning and quantum (inspired) optimization in the design of new, even better heuristics for hard problems.

Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines

Jonas Jäger, Roman V. Krems

Jul 14 2022 quant-ph cs.LG arXiv:2207.05865v1

Scite!5  PDF

Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. Here, we show that variational quantum classifiers (VQC) and support vector machines with quantum kernels (QSVM) can solve a classification problem based on the k-Forrelation problem, which is known to be PromiseBQP-complete. Because the PromiseBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make VQC and QSVM efficient solvers for any BQP problem. This means that the feature map of VQC or the quantum kernel of QSVM can be designed to have quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.

Quantum state tomography with tensor train cross approximation

Alexander Lidiak, Casey Jameson, Zhen Qin, Gongguo Tang, Michael B. Wakin, Zhihui Zhu, Zhexuan Gong

Jul 14 2022 quant-ph arXiv:2207.06397v1

Scite!2  PDF

It has been recently shown that a state generated by a one-dimensional noisy quantum computer is well approximated by a matrix product operator with a finite bond dimension independent of the number of qubits. We show that full quantum state tomography can be performed for such a state with a minimal number of measurement settings using a method known as tensor train cross approximation. The method works for reconstructing full rank density matrices and only requires measuring local operators, which are routinely performed in state-of-art experimental quantum platforms. Our method requires exponentially fewer state copies than the best known tomography method for unstructured states and local measurements. The fidelity of our reconstructed state can be further improved via supervised machine learning, without demanding more experimental data. Scalable tomography is achieved if the full state can be reconstructed from local reductions.

Categories: Week-in-QML


Leave a Reply

Your email address will not be published. Required fields are marked *