What We Do - Team - In News

Quantum Computing    Quantum computing is creating new ways to approach challenging problems in optimization, simulation, artificial intelligence, scientific discovery, and data analysis. Our lab works broadly across the quantum computing stack, from fundamental algorithms to methods that connect quantum processors with large-scale classical computing systems. Our research includes quantum and hybrid quantum–classical algorithms, variational quantum algorithms, quantum optimization, quantum simulation, quantum circuit design and synthesis, compilation and qubit mapping, resource-efficient computation, and rigorous theoretical analysis of quantum algorithms. We are particularly interested in scalable methods that combine quantum computing with high-performance computing and AI, including AI for quantum computing (using machine learning and generative models to design, optimize, and control quantum computations) and quantum computing for AI, where quantum methods are developed for machine learning, generative modeling, and scientific discovery. A central theme of our work is understanding how quantum, classical, AI, and HPC technologies can be combined to solve problems that are difficult for any one computational paradigm alone.

Machine Learning    Modern machine learning problems often involve enormous numbers of variables, samples, features, and interacting components, making conventional approaches computationally expensive or fundamentally difficult to optimize. Our research develops scalable machine learning and AI methods for problems involving large-scale optimization, complex structured data, graphs, and high-dimensional representations. We are particularly interested in algorithms that overcome slow convergence, combinatorial complexity, and NP-hard optimization subproblems, as well as methods that combine machine learning with optimization, scientific computing, graph algorithms, and emerging computing architectures.

AI, Literature Based Discovery and Text Mining    Scientific literature contains an enormous amount of knowledge, but many important connections remain implicit across papers, disciplines, and data sources. We develop AI systems for hypothesis generation and literature-based discovery that identify such hidden relationships and help researchers generate and prioritize new scientific hypotheses. Our work combines natural language processing, large-scale knowledge graphs, graph learning, machine learning, and large language models with experimental and curated scientific databases. A major application is biomedical and drug discovery, where our systems integrate information from millions of scientific publications and large biological and chemical datasets. We are also interested more broadly in scientific text mining, knowledge discovery, information extraction, and AI systems that can reason over large collections of heterogeneous scientific evidence.

Graph Algorithms and Network Science    Complex networks arise throughout science and engineering, including biological systems, social networks, communication systems, scientific knowledge graphs, transportation systems, and technological infrastructure. We study computational, algorithmic, modeling, and theoretical problems associated with such networks, with a particular emphasis on very large graphs. Our research includes scalable graph algorithms, community detection, graph partitioning, network optimization, anomaly and outlier detection, importance ranking, temporal and evolving networks, graph representation learning, visualization, and multilevel methods. We are especially interested in algorithms that uncover structure in networks too large or complex for conventional methods.

Combinatorial Scientific Computing    Many of the most expensive computations in science and engineering contain large discrete optimization problems hidden inside numerical algorithms. Combinatorial Scientific Computing develops graph- and hypergraph-based methods for exposing and exploiting this structure. Our work includes large-scale graph and hypergraph partitioning, ordering, coloring, clustering, task mapping, and related optimization problems. These techniques are used to improve load balancing, communication, memory locality, parallelism, and overall performance on modern high-performance computing systems. We are particularly interested in algorithms that connect combinatorial optimization with scientific computing, HPC, AI, and emerging quantum computing platforms.

Multiscale Methods    A broad range of scientific and optimization problems contain structure at multiple scales. Solving such problems directly at their finest resolution can require prohibitively large computational resources, even on modern supercomputers. We develop multiscale and multilevel algorithms that construct a hierarchy of progressively smaller representations of a problem, solve or analyze the problem at appropriate scales, and transfer information efficiently between them. These ideas originate in multigrid and multilevel scientific computing but extend naturally to graph algorithms, combinatorial optimization, machine learning, and quantum optimization. A major goal of our research is to use multiscale structure to make otherwise intractable problems computationally manageable.

The Expressive Power of Constrained QAOA: What You Might Have MISsed

 A central question in constrained quantum optimization is whether enforcing feasibility throughout the quantum evolution comes at the price of reduced expressiveness. Using Maximum Independent Set, we show that this does not have to be the case. 

We are happy to share our new preprint

Boris Tsvelikhovskiy Bao Bach, Ilya Safro"The Expressive Power of Constrained QAOA: What You Might Have MISsed" https://arxiv.org/abs/2609.18209

Some of the main results: ** Feasibility-preserving multi-angle QAOA can achieve full state controllability within the feasible subspace **  Even standard constrained QAOA, starting from the easily prepared empty set state, can reach an exact optimal MIS state at finite circuit depth ** We introduce a Flip-or-Stay mixer, closely related to the Laplacian of the feasible-state reconfiguration graph ** Surprisingly, two mixers that allow exactly the same transitions between feasible solutions can have dramatically different expressive power ** We also connect expressivity to trainability, showing that in the deep circuit regime the relevant landscape scale is determined by the size of the feasible solution space, rather than the full (2^n)-dimensional Hilbert space.

The broader message is that in constrained QAOA, the set of allowed moves is only part of the story. The structure of the mixer can fundamentally change the dynamics and the states the algorithm can reach.

Comments and feedback are very welcome!

#QuantumComputing #QAOA #QuantumOptimization #QuantumAlgorithms #VariationalQuantumAlgorithms #Optimization

Welcome to new PhD students!

Three new PhD students are joining our lab. Welcome Brent Russon, Daniel Lebedinskiy and Steven Halley. They will be working on quantum computing for optimization and AI.

Plenary talk at MOPTA 2026

 I really enjoyed the opportunity to give a plenary talk on scaling quantum optimization at MOPTA conference (Modeling and Optimization: Theory and Applications). MOPTA brings together an exciting mix of researchers and practitioners working across discrete and continuous optimization, with a great balance of theory and applications.

We discussed some of our recent work on developing building blocks for quantum optimization approaches that can scale to larger and more practically relevant problems, as well as the opportunities and challenges that arise when connecting quantum computing with modern optimization.

It was a great conference, many interesting conversations and discussions throughout the event. Many thanks to the organizers for the invitation and for putting together such an engaging program!

Paper accepted in ACM Transactions in Quantum Computing

Bao Bach, Ilya Safro, Ed Younis "Efficient Compilation for Shuttling Trapped-Ion Machines via the Position Graph Architectural Abstraction", ACM Transactions in Quantum Computing, 2026

https://dl.acm.org/doi/10.1145/3831246

With the growth of quantum platforms for gate-based quantum computation, compilation holds a crucial role in deciding the success of the implementation. While there has been rich research in compilation techniques for the superconducting-qubit regime. The trapped-ion architectures, currently leading in robust quantum computations for their reliable operations, still lack competitive compilation strategies. This work introduces a unifying hardware abstraction, the “position graph”, representing various hardware architectures. With this abstraction, we model trapped-ion Quantum Charge-Coupled Device (QCCD) architectures, enabling high-quality, scalable compilation methods. Specifically, we propose scheduling algorithms called SHuttling-Aware PERmutative (SHAPER) and SHuttling-AWare (SHAW) heuristic searches to tackle the complex constraints and dynamics of trapped-ion machines, with the cooperation of state-of-the-art permutation-aware mapping. These approaches generate executable circuits and native instructions that respect the physical constraints of shuttling-based architectures. We evaluate proposed algorithms across theorized and real architectures using the position graph framework. For completeness, we also introduce a linear program of trapped-ion scheduling that yields the optimal schedules, enabling a direct comparison with our heuristics. Our algorithm can successfully compile programs for extreme architectures where prior algorithms fail. When the baseline does complete, our produced schedules are 1.45 times faster on average, with best-case speedups up to 4 times faster.

Seven of our papers have been accepted to IEEE Quantum Computing and Engineering 2026

Seven of our papers have been accepted to the IEEE Quantum Computing and Engineering 2026. We are looking forward to catch up with many colleagues and friends and meet new people in Toronto!

1. Graph-Conditioned Meta-Optimizer for QAOA Parameter Generation on Multiple Problem Classes

Kien Nguyen and Ilya Safro

arXiv: https://arxiv.org/abs/2604.25275

2. Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

Brent Russon, Bao Bach, Ed Younis, and Ilya Safro

arXiv: https://arxiv.org/abs/2605.09237

3. Constrained Counterdiabatic Quantum Approximate Optimization Algorithm for Portfolio Optimization

Jose Falla and Ilya Safro

arXiv: https://arxiv.org/abs/2605.06858

4. Warm-Starting Rank-2 MaxCut Relaxation Using Local Correlators From Depth-1 Quantum Approximate Optimization Algorithm

Bao Bach, Filip Maciejewski, and Ilya Safro

Soon on arXiv

5. Quantum Hypergraph Partitioning

Cameron Ibrahim, Bao Bach, Jad Salem, Reuben Tate, Kien Nguyen, Stephan Eidenbenz, and Ilya Safro

arXiv: https://arxiv.org/abs/2605.10623

6. Implications of Reduced DLAs for the Standard QAOA Ansatz

Jose Falla, Bao Bach, Boris Tsvelikhovskiy, and Ilya Safro

Soon on arXiv

7. QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling

Van-Quang-Huy Nguyen, Hoang-Quan Nguyen, Samee Khan, Ilya Safro, and Khoa Luu

arXiv: https://arxiv.org/abs/2605.14001

Many thanks and congratulations to all our students and collaborators from University of California, Riverside, Los Alamos National Laboratory, Berkeley Lab, NASA - National Aeronautics and Space Administration, United States Naval Academy, University of Arkansas and Kansas State University. It's always a great pleasure working with you. 

Dr. Safro received the University of Delaware College of Engineering Faculty Award for Industry-Relevant Research

Thrilled and honored to receive the University of Delaware College of Engineering Faculty Award for Industry-Relevant Research. I am deeply grateful for this recognition. This work would not be possible without the outstanding students I have had the privilege to work with, as well as our amazing collaborators from industry and national laboratories. I am grateful to be on this journey with such wonderful people, and I look forward to the work ahead.

Dr. Safro                

Reductions of QAOA Induced by Classical Symmetries

 Super excited to share our new preprint "Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications" on arXiv! 

https://arxiv.org/abs/2602.16141

We explore how the performance of QAOA is determined by the structure of its dynamical Lie algebras and its connection to the expressivity and trainability. The primary objective of this work is to advance this understanding by studying the DLAs associated QAOA through the lens of symmetry reduction. Many combinatorial optimization objectives are invariant under a global bit-flip symmetry. From a classical standpoint, this symmetry allows one to fix the value of a single bit without loss of information. At first glance, this symmetry reduction appears to offer little advantage beyond a trivial reduction in problem size. One of the main contributions of this paper is to show that, at the quantum level, the situation is considerably richer. 

Huge congratulations to the students Bao Bach and Jose Falla! And special shout-out to first author Boris Tsvelikhovskiy for driving this project forward.

#QuantumComputing #QAOA #QuantumOptimization #Research #VariationalQuantumAlgorithms #Symmetry

The Duel of the Mixers in Quantum Approximate Optimization

Our new paper "Equivariant QAOA and the Duel of the Mixers" has been accepted in IEEE Transactions on Quantum Engineering!

In this work, we show that the choice of mixer Hamiltonian plays a critical role in QAOA performance. Many combinatorial optimization problems have natural symmetries, but standard QAOA mixers do not take advantage of them. We introduce new symmetry aware mixers that are tailored to the structure of the problem and can be efficiently implemented as quantum circuits. Through numerical experiments on graph coloring and graph partitioning, we demonstrate that these mixers consistently outperform the standard approach. We also explain why warm start QAOA often fails to improve results, identifying a fundamental limitation that prevents guaranteed convergence. This work shows that exploiting symmetry is a powerful and practical way to improve quantum optimization algorithms.

Congratulations and huge thanks to our co-authors Boris Tsvelikhovskiy and Yuri Alexeev! Check our paper at https://arxiv.org/abs/2405.07211

IEEE Quantum Computing and Engineering 2025

We had a fantastic time at IEEE Quantum Computing and Engineering (a.k.a. Quantum Week) https://lnkd.in/esWPtjHH. This is a highlight of the year that never disappoints. The conference initiated many exciting collaborations, and I’m especially proud that our lab presented or participated in five papers this time.

Special thanks to all of our amazing collaborators who made these papers possible Yuri Alexeev Marwa Farag Kyle Sherbert Karunya Shirali Sergii Strelchuk Mitchell Chiew Filip Maciejewski Khoa Luu Samee Khan. 

1. Ilya Tyagin, Marwa Farag, Kyle Sherbert, Karunya Shirali, Yuri Alexeev, Ilya Safro  "QAOA-GPT: Efficient Generation of Adaptive and Regular Quantum Approximate Optimization Algorithm Circuits"

2. Mitchell Chiew, Cameron Ibrahim, Ilya Safro, Sergii Strelchuk "Optimal fermion-qubit mappings via quadratic assignment"

3. Bao Bach, Filip Maciejewski, Ilya Safro "Solving Large-Scale QUBO with Transferred Parameters from Multilevel QAOA of low depth"

4. Kien Nguyen, Bao Bach, Ilya Safro "Cross-Problem Parameter Transfer in Quantum Approximate Optimization Algorithm: A Machine Learning Approach"

5. Hoang-Quan Nguyen, Xuan-Bac Nguyen, Sankalp Pandey, Samee U. Khan, Ilya Safro, Khoa Luu

 "QMoE: A Quantum Mixture of Experts Framework for Scalable Quantum Neural Networks"

What made it even more special was reconnecting with our former students Ruslan Shaydulin and Joey Xiaoyuan Liu, now leading experts in quantum computing. Seeing their impact on the field is both exciting and inspiring.

Looking forward to next year’s Quantum Week in Toronto!

#QuantumComputing #QAOA #QuantumOptimization #IEEEQCE #QuantumEngineering #HybridAlgorithms #Research #MachineLearning #QML 

Where Are Our PhD Students This Summer?

Congratulations to our PhD Students on their summer internships!

We’re proud to share that several of our PhD students are heading to exciting internship opportunities this summer. These positions will allow them to apply their research skills in real-world settings and gain valuable experience in industry and national labs.

Bao Bach - Los Alamos National Laboratory

Cameron Ibrahim - Pacific Northwest National Laboratory

Kien Nguyen - Fujitsu Research USA

Ilya Tyagin - BioCurie and Amazon

Two new papers in quantum computing and graph algorithms

We are happy to announce two new quantum computing papers from our group! I am particularly excited because both papers are direct applications of combinatorial scientific computing methods in the quantum computing domain.

The first, led by Hanjing Xu from Purdue University, presents a novel approach to transferring QAOA parameters for Maximum Independent Set problem using graph attention networks. This is a step toward building distributed hybrid quantum-classical algorithms, where large graph optimization problems are divided into smaller, quantum-solvable pieces and solved across quantum and classical systems. The approach achieves competitive performance and shows a promising direction for scalable quantum optimization.

Check our paper at https://arxiv.org/abs/2504.21135

The second paper, led by Mitchell Chiew from University of Cambridge and Cameron Ibrahim from University of Delaware, introduces optimization strategies for fermion-qubit mappings, a foundational step in simulating fermionic systems on quantum computers. By framing the problem as a quadratic assignment and strategically adding ancilla qubits, we achieve very good reductions to existing mappings, lowering the resource demands for quantum simulations. 

Check our paper at https://arxiv.org/abs/2504.21636

These papers couldn’t have happened without the great collaboration with Joey Xiaoyuan Liu from Fujitsu Research USA, Alex Pothen from Purdue University, and Sergii Strelchuk from the University of Oxford - thank you!

QAOA-GPT: Efficient Generation of Adaptive and Regular Quantum Approximate Optimization Algorithm Circuits

Our new paper "QAOA-GPT: Efficient Generation of Adaptive and Regular Quantum Approximate Optimization Algorithm Circuits" is now out! We introduce QAOA-GPT, a generative AI framework that uses GPT-style model to synthesize quantum circuits for solving combinatorial optimization problems and demonstrate it on MaxCut. Unlike traditional quantum approximate optimization algorithms and adaptive approaches, which rely on slow, iterative optimization, QAOA-GPT generates full circuits in a single forward pass, greatly improving scalability and efficiency. Importantly, this approach does not rely on prompt engineering or fine-tuning—the model is trained entirely from scratch using a custom circuit representation and graph-conditioned architecture.

It was a great pleasure collaborating on this project with an amazing team Marwa Farag and Yuri Alexeev from NVIDIA, and Kyle Sherbert and Karunya Shirali from Virginia Tech - thank you all for making this project a great experience! And huge congratulations to PhD student Ilya Tyagin for leading this work!

Check our paper at https://arxiv.org/abs/2504.16350

Cross-problem parameter transferability in Quantum Approximate Optimization Algorithm

Our latest work on making Quantum Approximate Optimization Algorithm more efficient through parameter transferability. Now it is the transferability across combinatorial optimization problems. Imagine a scenario where we have pre-trained QAOA parameters on a large collection of known optimization problems during the preprocessing. But then, a new problem class emerges, perhaps less studied or previously unknown. Should we invest substantial computational resources to re-optimize from scratch? 

We propose a graph neural network-based retrieval framework that learns graph embeddings and predicts transferable QAOA parameter sets optimized for MaxCut to accelerate convergence on Maximum Independent Set. Congratulations to PhD students Kien Nguyen and Bao Bach!

Check our paper at https://arxiv.org/abs/2504.10733

Kien Nguyen is joining our group

We're pleased to share that Kien Nguyen, PhD student in Computer Science, is joining our group. Kien will be working on quantum computing and machine learning.

Best Paper Award in Quantum Algorithms and IEEE Quantum Week

Our team had an amazing time at IEEE Quantum Computing and Engineering 2024 (aka IEEE Quantum Week) in Montreal, where we were honored to receive the Best Paper in Quantum Applications Award for the paper "MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA"! The conference was packed with excellent talks, workshops, tutorials and panels. 

It was also wonderful to catch up with our lab’s alumni, the Algorithms and Computational Science Lab legends Ankit Kulshrestha Joey Xiaoyuan Liu Ruslan Shaydulin, and see their success in the field. Graduate students Bao Bach and Cameron Ibrahim gave excellent talks on their papers. Big thanks to everyone who made this event such a success. This year there were over 1,550 participants from universities, national labs, and industry. Looking forward to even better event next year in Albuquerque, NM! 

#IEEEQuantum #QCE24 #QuantumComputing #QuantumWeek #IEEE #QuantumWeek2024

Our collaboration with NASA/USRA, Rigetti and Purdue

We have another accepted paper which is the result of our collaboration with amazing colleagues at NASA/USRA, Rigetti and Purdue.

Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, Davide Venturelli "A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization" is accepted in IEEE High-Performance Extreme Computing (HPEC) 2024

https://arxiv.org/abs/2408.07793

This work is a practical demonstration of our hybrid quantum-classical multilevel solver for the maxcut. Here we experimentally test how existing quantum processors perform as a sub-solver within the  multilevel strategy. We combine and extend (via additional classical processing) the recent Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's transmon device Ankaa-2 and then we find approximate solutions to 10 instances of fully connected Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios in the range ∼0.98−1.0. Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most ∼27,000 variables. The QPU (with classical post-processing steps) is used to find approximate solutions to dozens of problems, at most 82-qubit, which are iteratively used to construct the global solution. 

Recently accepted quantum computing papers

 July has been a prolific month for the quantum computing team in our lab. Four of our papers have been accepted for publication!

1) Jose Falla, Quinn Langfitt, Yuri Alexeev, Ilya Safro "Graph Representation Learning for Parameter Transferability in Quantum Approximate Optimization Algorithm" is accepted in Quantum Machine Intelligence. arxiv.org/abs/2401.06655

As the title suggests, we use graph embeddings to directly transfer precomputed parameters of QAOA to new graphs. Even relatively small-scale graph representation models imply good transferability, significantly accelerating computation.

2) Bao Bach, Jose Falla, Ilya Safro "MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA" is accepted in IEEE Quantum Computing and Engineering. arxiv.org/abs/2404.14399

Here, using combinations of representation learning techniques, ideas of R-QAOA, and quantum-inspired recursive optimization, we significantly accelerate the hybrid quantum-classical multilevel method and achieves a great time/quality trade-off that successfully competes with the fastest classical heuristics, making this algorithmic scheme a strong candidate for demonstrating practical quantum advantage in the future.

3) Cameron Ibrahim, Teague Tomesh, Zain Saleem, Ilya Safro "Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization" is accepted in IEEE Quantum Computing and Engineering. arxiv.org/abs/2405.00861

In this paper, we introduce the Deferred Constraint Quantum Divide and Conquer Algorithm, a method for constructing quantum circuits that reduces inter-device communication costs for some quantum graph optimization algorithms, an important step for distributed quantum computing.

4) Ankit Kulshrestha, Xiaoyuan Liu, Hayato Ushijima-Mwesigwa, Bao Bach, Ilya Safro "QAdaPrune: Adaptive Parameter Pruning For Training Variational Quantum Circuit", accepted in IEEE Quantum Computing and Engineering, Quantum AI workshop, https://arxiv.org/abs/2408.13352, 2024

Here we present QAdaPrune - an adaptive parameter pruning algorithm that automatically determines the threshold and then intelligently prunes the redundant and non-performing parameters to train quantum circuits. We show that the resulting sparse parameter sets yield quantum circuits that perform comparably to the unpruned quantum circuits and in some cases may enhance trainability of the circuits even if the original quantum circuit gets stuck in a barren plateau.

Congratulations to the graduate students Bao Bach, Jose Falla, and Cameron Ibrahim, and our amazing collaborators Teague Tomesh, Zain Hamid Saleem, Quinn Langfitt, Yuri Alexeev, Ankit Kulshrestha, Xiaoyuan Liu, and Hayato Ushijima-Mwesigwa. We look forward to meeting many of you in person and having a productive IEEE Quantum Computing and Engineering 2024 in Montreal!

This is what DALL-E thinks about us celebrating accepted papers. The quantum hardware store doors are open but where can we find this store?

Check our article on challenges and opportunities of scaling up quantum computation in SIAM News. May 2024

Our article is in SIAM News, May 2024

Rapid advancements in various quantum computing architectures have ignited a sense of cautious optimism about the realization of quantum advantage, especially as the field transitions from predominantly theoretical explorations to more applied functionalities. In addition to addressing challenges that pertain to single quantum bit (qubit) noise, fidelity, and decoherence, vendors are now emphasizing the scalability of their quantum systems as a critical component of their success. Current architectures—including trapped ions, superconducting circuits, and Rydberg atoms—face scalability hurdles in terms of the number of qubits and their fidelity. These hurdles have inspired both academic and industry researchers to develop scaling strategies that are reminiscent of the early (but still relevant) stages of classical supercomputing. Here, we discuss some of quantum computing’s opportunities and challenges in the realms of circuit optimization and scalability.
Click here to read full article

Quantum computing for finance: Our work is in UDaily.

 Great recent article in UDaily about our joint project with Argonne National Lab, JPMorgan Chase, Fujitsu and Menten AI. We discuss the obstacles and opportunities of quantum computing in finance.

Click here for the full article

Benchmarking Biomedical Literature-based Discovery and Hypothesis Generation Systems

Update: The paper is accepted for publication in BMC Bioinformatics.

We introduce a benchmarking framework Dyport for evaluating biomedical hypothesis generation (HG) and literature based discovery (LBD) systems. The evaluation of HG and LBD is still one of the major problems of these systems, especially when it comes to fully automated large-scale general purpose systems. For these, a massive assessment (that is normal in the machine learning and general AI domains) is often infeasible. One traditional evaluation approach is to make a system “rediscover” some of the landmark findings. However, this approach does not scale. Another traditional approach is to automatically discover some information in biomedical texts, train the system on historical data and test it on that "future" information. While this approach does scale well, the reliability and biomedical importance of the extracted test set are far from being illuminating. 

Utilizing curated datasets, Dyport tests HG/LBD systems under realistic conditions, enhancing the relevance of our evaluations. We integrate knowledge from the curated databases into a dynamic graph, accompanied by a method to quantify discovery importance. This not only assesses hypothesis accuracy but also their potential impact in biomedical research which significantly extends traditional link prediction benchmarks. Applicability of our benchmarking process is demonstrated on several link prediction systems applied on biomedical semantic knowledge graphs. Being flexible, our benchmarking system is designed for broad application in hypothesis generation quality verification, aiming to expand the scope of scientific discovery within the biomedical research community. 

Dyport is available at https://github.com/IlyaTyagin/Dyport

Paper: https://arxiv.org/pdf/2312.03303.pdf

Ankit Kulshrestha's PhD Defense

Congratulations to Dr. Ankit Kulshrestha for successfully defending his Ph.D. thesis "A Machine Learning Approach To Improve Scalability and Robustness of Variational Quantum Circuits"! Ankit will join the quantum computing research group at Fujitsu Research USA.

Welcoming our new PhD students!

 We're pleased to share that our group has expanded with the addition of two PhD students.

Bao Bach, joining from the Quantum Science and Engineering program, will be working on quantum machine learning and variational quantum algorithms. 

Saeideh Valipour has started her journey with us through the Computer Science PhD program. Her research areas include text mining, machine learning, and biomedical data analysis.

Let's extend a warm welcome to Bao and Saeideh as they begin their research endeavors with our group.

 

Two papers are accepted at IEEE High-Performance and Extreme Computing

We are happy to announce that two of our papers have been accepted at the IEEE High-performance and Extreme Computing Conference (HPEC 2023). 

"Hybrid Quantum-Classical Multilevel Approach for Maximum Cuts on Graphs" by Anthony Angone, Xiaoyuan Liu, Ruslan Shaydulin, and Ilya Safro. 

This paper is focusing on the Max-Cut problem. The study introduces a scalable hybrid multilevel approach to solve large instances of Max-Cut using both classical solvers and the quantum approximate optimization algorithm (QAOA). The results showcase the excellent performance of both classical and hybrid quantum-classical methods. 

The solver is publicly available at https://github.com/angone/MLMax-cut. 

Congratulations to the lead student and first author, Anthony Angone! 

"Decomposition Based Refinement for the Network Interdiction Problem" by Krish Matta, Xiaoyuan Liu, and Ilya Safro. 

This paper introduces a novel algorithm for the shortest path network interdiction problem. By decomposing the problem into sub-problems, the method efficiently utilizes Ising Processing Units alongside classical solvers. The results demonstrate comparable quality to existing exact solvers and also highlight a significant reduction in computational time for large-scale instances. 

The source code and experimental results can be accessed at https://github.com/krishxmatta/network-interdiction. 

A special shout-out to the lead student and first author, Krish Matta. A significant portion of his paper was accomplished during his high school years! Once again, congratulations to Anthony and Krish for their outstanding work and contributions to the field. We look forward to presenting these papers at HPEC 2023!

Learning To Optimize Quantum Neural Network Without Gradients

Our paper is accepted in IEEE Quantum Computing and Engineering (QCE) 2023. The preprint is available at https://arxiv.org/abs/2304.07442

Congratulations to PhD student Ankit Kulshrestha and two former students from our lab, now quantum computing research scientists at Fujitsu Research, Xiaoyuan Liu and Hyato Ushijima-Mwesigwa!

Quantum Machine Learning is an emerging sub-field in machine learning where one of the goals is to perform pattern recognition tasks by encoding data into quantum states. This extension from classical to quantum domain has been made possible due to the development of hybrid quantum-classical algorithms that allow a parameterized quantum circuit to be optimized using gradient based algorithms that run on a classical computer. The similarities in training of these hybrid algorithms and classical neural networks has further led to the development of Quantum Neural Networks (QNNs). However, in the current training regime for QNNs, the gradients w.r.t objective function have to be computed on the quantum device. This computation is highly non-scalable and is affected by hardware and sampling noise present in the current generation of quantum hardware. In this paper, we propose a training algorithm that does not rely on gradient information. Specifically, we introduce a novel meta-optimization algorithm that trains a meta-optimizer network to output parameters for the quantum circuit such that the objective function is minimized. We empirically and theoretically show that we achieve a better quality minima in fewer circuit evaluations than existing gradient based algorithms on different datasets.

Accepted paper in Nature Physics Reviews

Our paper "Quantum Computing for Finance" is accepted in Nature Physics Reviews. 

https://www.nature.com/articles/s42254-023-00603-1

The paper and its long version available in arXiv https://arxiv.org/pdf/2201.02773.pdf discuss not only the quantum algorithms in one of the most fascinating application areas but also the realistic obstacles the quantum computing faces to achieve any practical advantage over classical computing.

Graduate student achievement

 Congratulations to our PhD student Ankit Kulshrestha for receiving Rama and Shashi Marda fellowship for graduate studies! Ankit's research is in the areas of quantum and classical machine learning.

Biomedical hypothesis generation and literature-based discovery for landscape design

It is incredibly exciting to see our work transcend the bounds of its intended domain and find novel applications in unexpected areas. We initially developed AGATHA, a biomedical hypothesis generation system, to facilitate knowledge discovery within biomedical sciences. Yet, to our surprise and excitement, AGATHA's algorithm found an unanticipated yet transformative use in landscape design. AGATHA's unique ability to identify intricate conceptual relationships was exploited to understand the nexus between emerging infectious diseases (EIDs) and deforestation, enabling landscape planners to tread innovative research pathways. 

Our paper is available at arXiv https://arxiv.org/abs/2306.02588

David Marasco, Ilya Tyagin, Justin Sybrandt, James H. Spencer, Ilya Safro "Literature-based Discovery for Landscape Planning"

Generating and optimizing water networks

Our paper is accepted in the Journal of Pipeline Systems Engineering!

Ahmad Momeni, Varsha Chauhan, Abdulrahman Bin Mahmoud, Kalyan Piratla, Ilya Safro "Generation of Synthetic Water Distribution Data Using a Multi-Scale Generator-Optimizer", Journal of Pipeline Systems Engineering and Practice, vol. 14(1), https://ascelibrary.org/doi/full/10.1061/JPSEA2.PSENG-1358, 2023

Rare or limited access to real-world data has widely been a stumbling block for the development and employment of design optimization and simulation models in water distribution systems (WDS). Primary reasons for such accessibility issues could include data unavailability and high security protocols. Synthetic data can play a major role as a reliable alternative to mimic and replicate real-world WDS for modeling purposes. This study puts forth a comprehensive approach to generate synthetic WDS infrastructural data by (1) employing graph-theory concepts to generate multitudinous WDS skeleton layouts through retaining the critical topological features of a given real WDS; and (2) assigning component sizes and operational features such as nodal demands, pump curves, pipe sizes, and tank elevations to the generated WDS skeleton layouts through a multiobjective genetic algorithm (GA)–based design optimization scheme. Thousands of such generated-optimized networks are statistically analyzed in terms of the fundamental WDS characteristics both collectively and granularly. An outstanding novelty in this study includes an automatedly integrated algorithmic function that attempts to (1) simultaneously optimize the generated network in a biobjective scheme, (2) rectify pipe intersections that violate pipeline embedding standards, and (3) correct the unusual triangular loops in the generator by honoring the conventional square-shaped loop connectivity in a WDS. The proposed modeling approach was demonstrated in this study using the popular Anytown water distribution benchmark system. Generation and optimization of such representative synthetic networks pave the way for extensive access to representative case-study models for academic and industrial purposes while the security of the real-world infrastructure data is not compromised.

Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation

We are excited to announce that our paper received the best student paper award at #IEEE High Performance Extreme Computing #HPEC2022! Leading student is Cameron Ibrahim. Congratulations to all!

Cameron Ibrahim, Danylo Lykov, Zichang He, Yuri Alexeev, Ilya Safro "Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation", 2022, preprint at https://arxiv.org/abs/2209.02895

One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits.

Recently accepted papers in optimization and quantum and quantum inspired computing.

• Xiaoyuan Liu, Hayato Ushijima-Mwesigwa, Indradeep Ghosh, Ilya Safro "Partitioning Dense Graphs with Hardware Accelerators", International Conference on Computational Science (ICCS), 2022, preprint at https://arxiv.org/pdf/2202.09420.pdf
• Ankit Kulshrestha, Ilya Safro "BEINIT: Avoiding Barren Plateaus in Variational Quantum Algorithms", IEEE Quantum Computing and Engineering (QCE), 2022, preprint at https://arxiv.org/abs/2204.13751
• Xiaoyuan Liu, Ruslan Shaydulin, Ilya Safro "Quantum Approximate Optimization Algorithm with Sparsified Phase Operator", IEEE Quantum Computing and Engineering (QCE), 2022, preprint at https://arxiv.org/abs/2205.00118
• Xiaoyuan Liu, Hayato Ushijima-Mwesigwa, Avradip Mandal, Sarvagya Upadhyay, Ilya Safro, Arnab Roy "Leveraging Special-Purpose Hardware for Local Search Heuristics", Computational Optimization and Applications, 2022, preprint at https://arxiv.org/pdf/1911.09810.pdf

Quantum Computing for Finance

Quantum computers are expected to surpass the computational capabilities of classical computers and have transformative impact on numerous industry sectors, particularly finance. Finance is estimated to be one of the first industry sectors to benefit from quantum computing, not only in the medium and long terms, but even in the short term (however, this is subject to overcoming several engineering and algorithmic obstacles). 

Our team (Argonne National Lab - JPMorgan Chase - Menten AI - University of Chicago - University of Delaware) presents a comprehensive summary of the state of the art of quantum computing for financial applications, with particular emphasis on stochastic modeling, optimization, and machine learning, describing how these solutions, adapted to work on a quantum computer, can potentially help to solve financial problems, such as derivative pricing, risk modeling, portfolio optimization, natural language processing, and fraud detection, more efficiently and accurately. We also discuss the feasibility of these algorithms on nearterm quantum computers with various hardware implementations and demonstrate how they relate to a wide range of use cases in finance as well as discuss various obstacles to achieve these goals. We hope this article will not only serve as a reference for academic researchers and industry practitioners but also inspire new ideas for future research.

Herman, Dylan, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev. "A survey of quantum computing for finance." arXiv preprint  https://arxiv.org/abs/2201.02773 (2022).

Graduate Student Achievement Award

Congratulations to my former PhD student Xiaoyuan Joey Liu for winning Frank A. Pehrson Graduate Student Achievement Award! Her thesis is titled "Combinatorial Optimization Algorithms on Quantum and Quantum Inspired Devices". Xiaoyuan is now a research scientist at Fujitsu working in the area of quantum computing. This award is given to a computer science graduate student in recognition of outstanding performance, and potential for future significant contribution to the field of computer science.

Accelerating COVID-19 scientific discovery with hypothesis generation system

In 2020, the White House released the, “Call to Action to the Tech Community on New Machine Readable COVID-19 Dataset,” wherein artificial intelligence experts are asked to collect data and develop text mining techniques that can help the science community answer high-priority scientific questions related to COVID-19. The Allen Institute for AI and collaborators announced the availability of a rapidly growing open dataset of publications, the COVID-19 Open Research Dataset (CORD-19). As the pace of research accelerates, biomedical scientists struggle to stay current. To expedite their investigations, scientists leverage hypothesis generation systems, which can automatically inspect published papers to discover novel implicit connections. 

Ilya Tyagin, Ankit Kulshrestha, Justin Sybrandt, Krish Matta, Michael Shtutman, Ilya Safro "Accelerating COVID-19 research with graph mining and transformer-based learning", Innovative Applications of Artificial Intelligence (AAAI/IAAI), preprint at https://www.biorxiv.org/content/10.1101/2021.02.11.430789v1, 2022

We present an automated general purpose hypothesis generation systems AGATHA-C and AGATHA-GP for COVID-19 research. The systems are based on graph-mining and the transformer model. The systems are massively validated using retrospective information rediscovery and proactive analysis involving human-in-the-loop expert analysis. Both systems achieve high-quality predictions across domains (in some domains up to 0.97% ROC AUC) in fast computational time and are released to the broad scientific community to accelerate biomedical research. In addition, by performing the domain expert curated study, we show that the systems are able to discover on-going research findings such as the relationship between COVID-19 and oxytocin hormone.

Transferring QAOA parameters from small instances to large

The Quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for  achieving quantum advantage through quantum-enhanced combinatorial optimization. However, finding optimal parameters to run QAOA is a hard problem that is usually tackled by variational loop, i.e., the circuit is executed with the current parameters on a quantum device, and then the parameters are updated on a classical device. Such variational loops are extremely time consuming. In our recent paper we find the QAOA parameters for small optimization instances and transfer them to the larger ones accelerating the entire process.

Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, Ilya Safro "Transferability of optimal QAOA parameters between random graphs", IEEE International Conference on Quantum Computing and Engineering (QCE), preprint at https://arxiv.org/pdf/2106.07531.pdf, 2021

In a typical  QAOA setup, a set of quantum circuit parameters is optimized to prepare a quantum state used to find the optimal solution of a combinatorial optimization problem. Several empirical observations about optimal parameter concentration effects for special QAOA MaxCut problem instances have been made in recent literature, however, a rigorous study of the subject is still lacking. We show that convergence of the optimal QAOA parameters around specific values and, consequently, successful transferability of parameters between different QAOA instances can be explained and predicted based on the local properties of the graphs, specifically the types of subgraphs (lightcones) from which the graphs are composed. We apply this approach to random regular and general random graphs. For example, we demonstrate how optimized parameters calculated for a 6-node random graph can be successfully used without modification as nearly optimal parameters for a 64-node random graph, with less than 1% reduction in approximation ratio as a result. This work presents a pathway to identifying classes of combinatorial optimization instances for which such variational quantum algorithms as QAOA can be substantially accelerated.

Congratulations to Dr. Joey!

Congratulations to Dr. Xiaoyuan Joey Liu for successfully defending her Ph.D. thesis "Combinatorial Optimization Algorithms on Quantum and Quantum-inspired Devices"! Joey will join quantum computing research group at Fujitsu Research USA.

NIH funding for literature based discovery

NIH awarded $2.11M grant for University of South Carolina (PI Shtutman) - University of Delaware (PI Safro) collaborative project "Knowledge discovery and machine learning to elucidate the mechanisms of HIV activity and interaction with substance use disorder." This work will leverage our hypothesis generation model AGATHA that is based on information extracted from full MEDLINE. 

https://github.com/IlyaTyagin/AGATHA-C-GP

Here is its recent customization for COVID-19 in which Medline is fused with CORD-19, the dataset of all COVID-19 related papers.

https://arxiv.org/abs/2102.07631

Tutorial on the quantum approximate optimization algorithm, its applications and simulation

We recorded this tutorial for IEEE International Conference on Quantum Computing and Engineering (QCE) 2020. This tutorial consists of four parts:

1. QAOA theory and quantum computing basics
2. Hands on example of QAOA and MaxCut
3. Introduction to problem decomposition and solving large-scale problems with QAOA
4. Tensor networks and simulation of QAOA with classical computers

Multilevel Graph Partitioning for Three-Dimensional Discrete Fracture Network Flow Simulations

Combinatorial scientific computing in action! Our paper on accelerating 3D discrete fracture network flow simulations by multilevel graph partitioning is accepted in Mathematical Geosciences!

Hayato Ushijima-Mwesigwa, Jeffrey D. Hyman, Aric Hagberg, Ilya Safro, Satish Karra, Carl W. Gable, Gowri Srinivasan "Multilevel Graph Partitioning for Three-Dimensional Discrete Fracture Network Flow Simulations", accepted in Mathematical Geosciences, preprint at https://arxiv.org/abs/1902.08029, 2020

We present a topology-based method for mesh-partitioning in three-dimensional discrete fracture network (DFN) simulations that takes advantage of the intrinsic multi-level nature of a DFN. DFN models are used to simulate flow and transport through low-permeability fracture media in the subsurface by explicitly representing fractures as discrete entities. The governing equations for flow and transport are numerically integrated on computational meshes generated on the interconnected fracture networks. Modern high-fidelity DFN simulations require high-performance computing on multiple processors where performance and scalability depends partially on obtaining a high-quality partition of the mesh to balance work work-loads and minimize communication across all processors.

The discrete structure of a DFN naturally lends itself to various graph representations, which can be thought of as coarse-scale representations of the computational mesh. Using this concept, we develop a variant of the multilevel graph partitioning algorithm to partition the mesh of a DFN. We compare the performance of this DFN-based mesh-partitioning with standard multi-level graph partitioning using graphbased metrics (cut, imbalance, partitioning time), computational-based metrics (FLOPS, iterations, solver time), and total run time. The DFN-based partition and the mesh-based partition are comparable in terms of the graph-based metrics, but the time required to obtain the partition is several orders of magnitude faster using the DFN-based partition. The computation-based metrics show comparable performance between both methods so, in combination, the DFN-based partition is several orders of magnitude faster than the mesh-based partition.

ELRUNA: Network Alignment Algorithm

Our network alignment algorithm ELRUNA is accepted in ACM Journal of Experimental Algorithmics. Turns out that three relatively simple node similarity rules can successfully compete with several state of the art algorithms and improve both the running time and alignment quality. You can get it at https://github.com/BridgelessAlexQiu/ELRUNA

Zirou Qiu, Ruslan Shaydulin, Xiaoyuan Liu, Yuri Alexeev, Christopher S. Henry, Ilya Safro "ELRUNA: Elimination Rule-based Network Alignment", accepted in ACM Journal of Experimental Algorithmics, preprint at https://arxiv.org/abs/1911.05486, 2020

Networks model a variety of complex phenomena across different domains. In many applications, one of the most essential tasks is to align two or more networks to infer the similarities between cross-network vertices and discover potential node-level correspondence. In this paper, we propose ELRUNA (Elimination rule-based network alignment), a novel network alignment algorithm that relies exclusively on the underlying graph structure. Under the guidance of the elimination rules that we defined, ELRUNA computes the similarity between a pair of cross-network vertices iteratively by accumulating the similarities between their selected neighbors. The resulting cross-network similarity matrix is then used to infer a permutation matrix that encodes the final alignment of cross-network vertices. In addition to the novel alignment algorithm, we also improve the performance of local search, a commonly used post-processing step for solving the network alignment problem, by introducing a novel selection method RAWSEM (Random walk based selection method) based on the propagation of the levels of mismatching (defined in the paper) of vertices across the networks. The key idea is to pass on the initial levels of mismatching of vertices throughout the entire network in a random-walk fashion. Through extensive numerical experiments on real networks, we demonstrate that ELRUNA significantly outperforms the state-of-the-art alignment methods in terms of alignment accuracy under lower or comparable running time. Moreover, ELRUNA is robust to network perturbations such that it can maintain a close to optimal objective value under a high level of noise added to the original networks. Finally, the proposed RAWSEM can further improve the alignment quality with a less number of iterations compared with the naive local search method.

Can we outperform Quantum Approximate Optimization Algorithm?

Check our new paper:

Xiaoyuan Liu, Anthony Angone, Ruslan Shaydulin, Ilya Safro, Yuri Alexeev, Lukasz Cincio "Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers", preprint at https://arxiv.org/abs/2102.05566, 2021

We propose a hybrid quantum-classical algorithm, Layer Variational Quantum Eigensolver (L-VQE), inspired by the Variational Quantum Eigensolver (VQE). L-VQE is a heuristic approach to solve combinatorial optimization problems on near term intermediate-scale quantum devices. We demonstrate the potential of the proposed approach by applying it to the problem of community detection, a famous problem in network science. Our large-scale numerical simulation study shows that L-VQE has the potential to outperform Quantum Approximate Optimization Algorithm (QAOA), and is more robust to sampling noise as compared with standard VQE approaches.

Literature-based knowledge discovery to accelerate COVID-19 research

Our new paper on customization of AGATHA knowledge discovery model for COVID-19 is out!

Ilya Tyagin, Ankit Kulshrestha, Justin Sybrandt, Krish Matta, Michael Shtutman,  Ilya Safro

"Accelerating COVID-19 research with graph mining and transformer-based learning", 2021

https://www.biorxiv.org/content/10.1101/2021.02.11.430789v1

In 2020, the White House released the, "Call to Action to the Tech Community on New Machine Readable COVID-19 Dataset," wherein artificial intelligence experts are asked to collect data and develop text mining techniques that can help the science community answer high-priority scientific questions related to COVID-19. The Allen Institute for AI and collaborators announced the availability of a rapidly growing open dataset of publications, the COVID-19 Open Research Dataset (CORD-19). As the pace of research accelerates, biomedical scientists struggle to stay current. To expedite their investigations, scientists leverage hypothesis generation systems, which can automatically inspect published papers to discover novel implicit connections. We present an automated general purpose hypothesis generation systems AGATHA-C and AGATHA-GP for COVID-19 research. The systems are based on graph-mining and the transformer model. The systems are massively validated using retrospective information rediscovery and proactive analysis involving human-in-the-loop expert analysis. Both systems achieve high-quality predictions across domains (in some domains up to 0.97% ROC AUC) in fast computational time and are released to the broad scientific community to accelerate biomedical research. In addition, by performing the domain expert curated study, we show that the systems are able to discover on-going research findings such as the relationship between COVID-19 and oxytocin hormone.

Reboot the Computing-Research Publication Systems

Many good points by Moshe Vardi on current CS research publication system in the Communications of ACM

Reboot the Computing-Research Publication Systems: The virtualization of conferences due to COVID-19 has sharpened my conviction that the computing-research publication system is badly broken and in need of a serious reboot.

Do we always need big data in text mining?

Do we always need Big Data text mining? Can we filter it? Check our new paper "Accelerating Text Mining Using Domain-Specific Stop Word Lists" accepted at IWBDR https://arxiv.org/pdf/2012.02294.pdf

Text preprocessing is an essential step in text mining. Removing words that can negatively impact the quality of prediction algorithms or are not informative enough is a crucial storage-saving technique in text indexing and results in improved computational efficiency. Typically, a generic stop word list is applied to a dataset regardless of the domain. However, many common words are different from one domain to another but have no significance within a particular domain. Eliminating domain-specific common words in a corpus reduces the dimensionality of the feature space, and improves the performance of text mining tasks. In this paper, we present a novel mathematical approach for the automatic extraction of domain-specific words called the hyperplane-based approach. This new approach depends on the notion of low dimensional representation of the word in vector space and its distance from hyperplane. The hyperplane-based approach can significantly reduce text dimensionality by eliminating irrelevant features. We compare the hyperplane-based approach with other feature selection methods, namely \c{hi}2 and mutual information. An experimental study is performed on three different datasets and five classification algorithms, and measure the dimensionality reduction and the increase in the classification performance. Results indicate that the hyperplane-based approach can reduce the dimensionality of the corpus by 90% and outperforms mutual information. The computational time to identify the domain-specific words is significantly lower than mutual information.

Quantum Approximate Optimization Algorithm and Symmetry

 Our new paper QAOA symmetry and its predictability using classical symmetry is out! We analyze the connections between the symmetries of the objective function and the symmetries of QAOA dynamics, and applications to performance prediction, simulation and more https://scirate.com/arxiv/2012.04713

Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, Ilya Safro "Classical symmetries and QAOA", 2020

We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques towards predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

On improving nonlinear SVM scalability using multilevel frameworks

Our paper "AML-SVM: Adaptive Multilevel Learning with Support Vector Machines" is accepted at 2020 IEEE International Conference on Big Data. https://arxiv.org/abs/2011.02592

The support vector machines (SVM) is one of the most widely used and practical optimization based classification models in machine learning because of its interpretability and flexibility to produce high quality results. However, the big data imposes a certain difficulty to the most sophisticated but relatively slow versions of SVM, namely, the nonlinear SVM. The complexity of nonlinear SVM solvers and the number of elements in the kernel matrix quadratically increases with the number of samples in training data. Therefore, both runtime and memory requirements are negatively affected. Moreover, the parameter fitting has extra kernel parameters to tune, which exacerbate the runtime even further. This paper proposes an adaptive multilevel learning framework for the nonlinear SVM, which addresses these challenges, improves the classification quality across the refinement process, and leverages multi-threaded parallel processing for better performance. The integration of parameter fitting in the hierarchical learning framework and adaptive process to stop unnecessary computation significantly reduce the running time while increase the overall performance. The experimental results demonstrate reduced variance on prediction over validation and test data across levels in the hierarchy, and significant speedup compared to state-of-the-art nonlinear SVM libraries without a decrease in the classification quality. 

How to use NISQ quantum devices to solve large-scale problems?

Our paper on multilevel hybrid quantum-classical  optimization "Multilevel Combinatorial Ooptimization  Across Quantum Architectures" is accepted in ACM Transactions on Quantum Computing! Big kudos to two lead former students Hayato and Ruslan! https://arxiv.org/abs/1910.09985

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore's law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this paper, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. In order to demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave's quantum annealer and IBM's gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitudes larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution.

New NSF grant to develop a simulator for quantum computing

NSF awarded grant to develop large-scale QAOA simulator! This is a collaborative project with the Yuri Alexeev@University of Chicago.

Generating biomedical scientific hypotheses with AGATHA

 Accepted paper in the 29TH ACM International Conference on Information and Knowledge Management (CIKM)

Sybrandt, Tyagin, Shtutman, Safro "AGATHA: Automatic Graph-mining and Transformer based Hypothesis Generation Approach", preprint at http://arxiv.org/pdf/2002.05635.pdf

Medical research is risky and expensive. Drug discovery requires researchers to efficiently winnow thousands of potential targets to a small candidate set. However, scientists spend significant time and money long before seeing the intermediate results that ultimately determine this smaller set. Hypothesis generation systems address this challenge by mining the wealth of publicly available scientific information to predict plausible research directions. We present AGATHA, a deep-learning hypothesis generation system that learns a data-driven ranking criteria to recommend new biomedical connections. We massively validate our system with a temporal holdout wherein we predict connections first introduced after 2015 using data published beforehand. We additionally explore biomedical sub-domains, and demonstrate AGATHA's predictive capacity across the twenty most popular relationship types. Furthermore, we perform an ablation study to examine the aspects of our semantic network that most contribute to recommendation quality. Overall, AGATHA achieves best-in-class recommendation quality when compared to other hypothesis generation systems built to predict across all available biomedical literature. Reproducibility: All code, experimental data, and pre-trained models are available online: sybrandt.com/2020/agatha.

Two papers on graph representation learning

 Accepted papers at Workshop on Mining and Learning with Graphs co-located with ACM KDD 2020! 

1) Ding, Zhang, Sybrandt, Safro "Unsupervised Hierarchical Graph Representation Learning by Mutual Information Maximization", 2020

Graph representation learning based on graph neural networks (GNNs) can greatly improve the performance of downstream tasks, such as node and graph classification. However, the general GNN models do not aggregate node information in a hierarchical manner, and can miss key higher-order structural features of many graphs. The hierarchical aggregation also enables the graph representations to be explainable. In addition, supervised graph representation learning requires labeled data, which is expensive and error-prone. To address these issues, we present an unsupervised graph representation learning method, Unsupervised Hierarchical Graph Representation (UHGR), which can generate hierarchical representations of graphs. Our method focuses on maximizing mutual information between "local" and high-level "global" representations, which enables us to learn the node embeddings and graph embeddings without any labeled data. To demonstrate the effectiveness of the proposed method, we perform the node and graph classification using the learned node and graph embeddings. The results show that the proposed method achieves comparable results to state-of-the-art supervised methods on several benchmarks. In addition, our visualization of hierarchical representations indicates that our method can capture meaningful and interpretable clusters.

2) Sybrandt, Safro "FOBE and HOBE: First- and High-Order Bipartite Embeddings", 2020

Typical graph embeddings may not capture type-specific bipartite graph features that arise in such areas as recommender systems, data visualization, and drug discovery. Machine learning methods utilized in these applications would be better served with specialized embedding techniques. We propose two embeddings for bipartite graphs that decompose edges into sets of indirect relationships between node neighborhoods. When sampling higher-order relationships, we reinforce similarities through algebraic distance on graphs. We also introduce ensemble embeddings to combine both into a "best of both worlds" embedding. The proposed methods are evaluated on link prediction and recommendation tasks and compared with other state-of-the-art embeddings. While being all highly beneficial in applications, we demonstrate that none of the considered embeddings is clearly superior (in contrast to what is claimed in many papers), and discuss the trade offs present among them. 

PhD thesis defense

Congratulations to Dr. Ruslan Shaydulin for successfully defending his Ph.D. thesis "Quantum and Classical Multilevel Algorithms for (Hyper)Graphs"! Ruslan will join Argonne National Lab with  MGM fellowship in August. This is the second defense in our lab this week!

PhD thesis defense

Congratulations to Dr. Ehsan Sadrfaridpour for successfully defending his Ph.D. thesis "Fast Machine Learning Algorithms for Massive Datasets with Applications in Biomedical Domain"! Ehsan will join Lowe's data science team this summer.

Our work in HPCwire

News coverage in HPCwire about our collaboration with Argonne on hybrid quantum-classical computing
Argonne Receives Two Awards from DARPA for Quantum Information Science

NSF grant to tackle COVID-19

Our team received NSF grant to tackle COVID-19 using our AI hypothesis generation system AGATHA
Clemson news coverage: Artificial intelligence could aid in fight against COVID-19

Ilya Safro of @socclemson said that his team will soon roll out a new artificial intelligence system aimed at helping researchers explore the scientific literature as they strive for new discoveries to combat the novel coronavirus.https://t.co/TwQyZqEUra pic.twitter.com/fh3K8iAoWO

— Clemson Engineering, Computing & Applied Sciences (@ClemsonCECAS) April 21, 2020

Board game night

Board game night from quarantine! pic.twitter.com/6env2hICaa

— Justin Sybrandt, Ph.D. (@Justin_Sybrandt) March 28, 2020

 

Combing the best of quantum and classical computing

 News coverage from Clemson: Combing the best of quantum and classical computing

From SoC@Clemson

Congrats to Dr. Ilya Safro on receiving funding from @DARPA to work on hybrid quantum-classical algorithms for combinatorial optimization problems, a 4 year collaborative research with @argonne. He is looking for Ph.D. students to join the Algorithms & Computational Science lab. pic.twitter.com/YfIYVc7HzO

— School of Computing (@socclemson) April 3, 2020