Abstract Current gate-based quantum computers have the potential to provide a computational advantage if algorithms use quantum hardware efficiently. To make combinatorial optimization more efficient, we introduce the filtering variational quantum eigensolver which utilizes filtering operators to achieve faster and more reliable convergence to the optimal solution. Additionally we explore the use of causal cones to reduce the number of qubits required on a quantum computer. Using random weighted MaxCut problems, we numerically analyze our methods and show that they perform better than the original VQE algorithm and the quantum approximate optimization algorithm. We also demonstrate the experimental feasibility of our algorithms on a Quantinuum trapped-ion quantum processor powered by Honeywell.
Abstract Current gate-based quantum computers have the potential to provide a computational advantage if algorithms use quantum hardware efficiently. To make combinatorial optimization more efficient, we introduce the filtering variational quantum eigensolver which utilizes filtering operators to achieve faster and more reliable convergence to the optimal solution. Additionally we explore the use of causal cones to reduce the number of qubits required on a quantum computer. Using random weighted MaxCut problems, we numerically analyze our methods and show that they perform better than the original VQE algorithm and the quantum approximate optimization algorithm. We also demonstrate the experimental feasibility of our algorithms on a Quantinuum trapped-ion quantum processor powered by Honeywell.
Abstract Even a minor boost in solving combinatorial optimization problems can greatly benefit multiple industries. Quantum computers, with their unique information processing capabilities, hold promise for delivering such enhancements. The filtering variational quantum eigensolver (F-VQE) is a variational hybrid quantum algorithm designed to solve combinatorial optimization problems on existing quantum computers with limited qubit number, connectivity, and fidelity. In this work we employ instantaneous quantum polynomial circuits as our parameterized quantum circuits. We propose a hardware-efficient implementation that respects limited qubit connectivity and show that they halve the number of circuits necessary to evaluate the gradient with the parameter-shift rule. To assess the potential of this protocol in the context of combinatorial optimization, we conduct extensive numerical analysis. We compare the performance against three classical baseline algorithms on weighted MaxCut and the asymmetric traveling salesperson problem (ATSP). We employ noiseless simulators for problems encoded on 13–29 qubits, and up to 37 qubits on the IBMQ real quantum devices. The ATSP encoding employed reduces the number of qubits and avoids the need of constraints compared to the standard quadratic unconstrained binary optimization/Ising model. Despite some observed positive signs, we conclude that significant development is necessary for a practical advantage with F-VQE.
Variational quantum eigensolver (VQE), a kind of quantum-classical hybrid method, has latent powers to leverage noisy quantum devices by effectively managing a limited number of qubits with finite coherent times. We implemented VQE with real quantum processors through IBM Quantum Experience and applied it to combinatorial optimizations. Notably, a short-depth quantum circuit consisting of a lower number of quantum gate than that in the quantum approximate optimization algorithm can search the ground states of diagonal Hamiltonians encoding the problems. Since the simplest case of the quantum circuit for VQE requires only single-qubit gates, it can be realized using current quantum computers.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
Abstract Combinatorial optimization models a vast range of industrial processes aiming at improving their efficiency. In general, solving this type of problem exactly is computationally intractable. Therefore, practitioners rely on heuristic solution approaches. Variational quantum algorithms are optimization heuristics that can be demonstrated with available quantum hardware. In this case study, we apply four variational quantum heuristics running on IBM’s superconducting quantum processors to the job shop scheduling problem. Our problem optimizes a steel manufacturing process. A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster and samples the global optimum more frequently than the quantum approximate optimization algorithm (QAOA), the standard variational quantum eigensolver (VQE), and variational quantum imaginary time evolution (VarQITE). Furthermore, F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.
ABSTRACT: Even if the quantum computing popularity has recently grown, the currently-available technology is not ready for a fundamental revolution of informatics. In this transition phase, hybrid quantum-classical algorithms can help in understanding the real power that this novel paradigm can reach in the future. In this work, we tested the capability of two such algorithms to solve combinatorial optimization problems: the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). We used them to solve max-cut problems, consisting of separating the vertices of an undirected graph in two sub-groups so that the number of edges connecting vertices of different sub-groups is maximal. To do that, we mapped the problem into a quantum system, using the Ising formalism. In particular, we investigated the effect of changing the number of measurements of the quantum circuit associated with the system on the algorithms convergence. A large number of measurements (or shots) allows a better knowledge of the quantum state, but on the other hand, increases the convergence time, making the algorithms less competitive compared to classical techniques. The results showed that VQE needs a mínimum number of measurements to start converging towards the optimal problem solution. Once this threshold is overcome, the solution improves as 1/√shots. QAOA, on the other hand, does not seem to converge, independently of the number of shots.
Combinatorial optimization on near-term quantum devices is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise or error rates. In this article, inspired by the variational quantum eigensolver (VQE), we propose an iterative layer VQE (L-VQE) approach. We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE with the quantum approximate optimization algorithm (QAOA) and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to finite sampling errors and has a higher chance of finding the solution as compared with standard VQE approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.