Article
Computer Science, Interdisciplinary Applications
Thiago Serra, Teng Huang, Arvind U. Raghunathan, David Bergman
Summary: Quantum annealing (QA) is used to solve quadratic unconstrained binary optimization (QUBO) problems efficiently, but the limited connectivity of qubits in existing QA hardware has led to research on preprocessing algorithms for embedding problem variables into the hardware graph. This paper employs integer linear programming to search for embedding solutions, and introduces the concept of template embeddings for different classes of minors of the Chimera graph, improving upon existing methods based on odd cycle transversals. The study demonstrates that this approach can be used to certify the absence of a minor embedding using a specific template, achieving better scalability and significantly smaller runtimes compared to state-of-the-art OCT-based methods.
INFORMS JOURNAL ON COMPUTING
(2022)
Article
Quantum Science & Technology
Elijah Pelofske, Georg Hahn, Hristo N. N. Djidjev
Summary: Quantum annealing has the potential to solve NP-hard problems, but the current hardware is limited in size, which hinders solving larger optimization problems. In this research, we demonstrate that a hybrid approach combining parallel quantum annealing with graph decomposition can accurately solve the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
QUANTUM INFORMATION PROCESSING
(2023)
Article
Physics, Multidisciplinary
Aaron Villanueva, Peyman Najafi, Hilbert J. Kappen
Summary: This paper studies quantum annealing for combinatorial optimization, computes the minimal spectral gap and its location, and shows the requirement of precise knowledge for quantum speed-up. However, the intractability of computing the density of states makes quadratic speed-up unfeasible for practical problems. The paper also conjectures similar negative results for other instance independent transverse Hamiltonians.
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2023)
Article
Quantum Science & Technology
Elisabeth Lobe, Lukas Schuermann, Tobias Stollenwerk
Summary: The study investigates the embedding of complete graphs into broken Chimera graphs, proposing an optimization solution to the matching problem and experimentally verifying the performance on various hardware graph instances. It demonstrates that for different types of hardware graph instances, the exact approach can embed larger complete graphs within fixed runtime compared to previous heuristic methods.
QUANTUM INFORMATION PROCESSING
(2021)
Article
Optics
Gianluca Passarelli, Ka-Wa Yip, Daniel A. Lidar, Procolo Lucignano
Summary: The article studies adiabatic reverse annealing (ARA) in an open system. By simulating the effects of decoherence on ARA performance, it is found that ARA in an open system is less sensitive to the choice of initial state and loses its time advantage compared to standard quantum annealing. This suggests that error mitigation strategies are needed to realize the benefits of ARA in realistic settings.
Article
Computer Science, Artificial Intelligence
Shuliang Wang, Xiaorui Qin, Lianhua Chi
Summary: This paper proposes a compressed graph embedding method based on HashWalk, which can reduce computational cost and improve time efficiency in node classification.
PATTERN RECOGNITION LETTERS
(2022)
Article
Quantum Science & Technology
Juan Carlos Criado, Michael Spannowsky
Summary: We present a general method, called Qade, for solving differential equations using a quantum annealer. The method is flexible and reliable, being able to solve systems of coupled partial differential equations with non-linear variable coefficients and arbitrary inhomogeneous terms. Several examples, including a partial differential equation and a system of coupled equations, are tested on state-of-the-art quantum annealers, and accurate solutions can be obtained for problems requiring a small enough function basis. The implementation of the method in a Python package is provided at gitlab.com/jccriado/qade.
QUANTUM SCIENCE AND TECHNOLOGY
(2023)
Article
Physics, Multidisciplinary
Yusuke Kimura, Hidetoshi Nishimori
Summary: The study establishes a generic bound on the rate of decrease of transverse field for quantum annealing to converge to the ground state of a generic Ising model. It provides a mathematically rigorous condition for better control of convergence speed in specific problems.
JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL
(2022)
Article
Computer Science, Theory & Methods
Anwar Said, Saeed-Ul Hassan, Suppawong Tuarob, Raheel Nawaz, Mudassir Shabbir
Summary: In this work, a distributed and permutation invariant graph embedding method called DGSD is proposed, which extracts graph representations on independently distributed machines by considering nodes' degree, common neighbors, and direct connectivity to find local proximity, suitable for processing large graphs with linear space complexity. Its scalability on sufficiently large random and real-world networks is demonstrated, along with its performance evaluation on bioinformatics and social networks in a distributed computing environment.
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
(2021)
Article
Physics, Multidisciplinary
Pratibha Raghupati Hegde, Gianluca Passarelli, Giovanni Cantele, Procolo Lucignano
Summary: In order to optimize quantum annealing in the race towards quantum advantage, this study proposes the use of long-short term memory neural networks to automate the search for optimal annealing schedules for random Ising models on regular graphs. By training the network using locally-adiabatic annealing paths, optimal annealing schedules for unseen instances and even larger graphs than those used for training can be predicted.
NEW JOURNAL OF PHYSICS
(2023)
Article
Computer Science, Theory & Methods
F. Orts, A. M. Puertas, G. Ortega, E. M. Garzon
Summary: This paper introduces quantum computing and focuses on adiabatic quantum computing as a quantum programming model. It has been successfully applied in solving problems like graph partitioning, traffic routing, and task scheduling. Specifically, the paper discusses the scheduling of unrelated parallel machines and extends the model to consider task priorities and delays. The proposed quantum nonlinear programming framework solves the Quadratic Unconstrained Binary Optimization problem on the D-Wave platform. It also utilizes compact models to handle larger scheduling problems and estimates the required qubits based on scheduling parameters.
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE
(2023)
Article
Physics, Multidisciplinary
Chen-Fu Chiang, Paul M. Alsing
Summary: We investigate the irreconcilability issue of translating the search algorithm from the CTQW framework to the AQC framework. By modifying the catalyst Hamiltonian and introducing adaptive scheduling, we resolve the constant energy gap issue and improve the adiabatic local search in AQC.
Article
Computer Science, Artificial Intelligence
Lixin Cui, Ming Li, Lu Bai, Yue Wang, Jing Li, Yanchao Wang, Zhao Li, Yunwen Chen, Edwin R. Hancock
Summary: This paper proposes a novel framework for computing Quantum-based Entropic Representations (QBER) for un-attributed graphs using Continuous-time Quantum Walk (CTQW). By transforming each original graph into a family of k-level neighborhood graphs, the framework captures multi-level topological information of the original global graph. The structure of each neighborhood graph is characterized using the Average Mixing Matrix (AMM) of CTQW, enabling the computation of Quantum Shannon Entropy and entropic signature. Experimental results demonstrate the effectiveness of the proposed approach in classification accuracies, outperforming other entropic complexity measuring methods, graph kernel methods, and graph deep learning methods.
PATTERN RECOGNITION
(2024)
Article
Quantum Science & Technology
Erica Grant, Travis S. Humble
Summary: In this study, we empirically benchmark the probability of chain breaks in a suite of embedded Hamiltonians and identify sweet spots for problem solving. We also correlate the physical location of chain breaks in the quantum annealing hardware with the underlying embedding technique and use these localized rates in a tailored post-processing strategy, demonstrating the ability to tune the embedded Hamiltonian and remove computational errors.
QUANTUM SCIENCE AND TECHNOLOGY
(2022)
Article
Quantum Science & Technology
Bibek Pokharel, Zoe Gonzalez Izquierdo, P. Aaron Lott, Elena Strbac, Krzysztof Osiewalski, Emmanuel Papathanasiou, Alexei Kondratyev, Davide Venturelli, Eleanor Rieffel
Summary: This study compares the performance of four quantum annealers in solving scheduling problems and finds that hardware upgrades and optimizations greatly improve performance.
QUANTUM INFORMATION PROCESSING
(2023)
