a hybrid approach for solving optimization problems on small quantum computers

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers

2019, Computer

Related Papers

ACM Transactions on Quantum Computing

Susan Mniszewski

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 article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. 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 quant...

Advanced Quantum Technologies

Breast Cancer Research and Treatment

Antonio Ghidini

Yuri Alexeev

Quantum computers are expected to surpass the computational capabilities of classical computers during this decade and have transformative impact on numerous industry sectors, particularly finance. In fact, finance is estimated to be the first industry sector to benefit from quantum computing, not only in the medium and long terms, but even in the short term. This survey paper presents a comprehensive summary of the state of the art of quantum computing for financial applications, with particular emphasis on Monte Carlo integration, optimization, and machine learning, showing how these solutions, adapted to work on a quantum computer, can help solve more efficiently and accurately problems such as derivative pricing, risk analysis, portfolio optimization, natural language processing, and fraud detection. We also discuss the feasibility of these algorithms on near-term quantum computers with various hardware implementations and demonstrate how they relate to a wide range of use cases...

arXiv (Cornell University)

Gabriel Tamura

Proceedings of the AAAI Conference on Artificial Intelligence

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA cir...

2020 IEEE High Performance Extreme Computing Conference (HPEC)

Uchenna Chukwu

Rafael Pereira da Silva

This paper outlines the use of noisy intermediate-scale quantum (NISQ) computers for Hamiltonian minimization problems. We delve into the mathematical formulation of Variational Quantum Eigensolver (VQE), Quantum Annealing (QA) and Quantum Approximation Optimization Algorithm (QAOA), with computational results for a 3-qubit minimization problem and its extension to 6-qubit, 13-qubit and 140-qubit. We show how different initial parameters leads to optimal, less accurate, or no satisfactory solutions using the considered versions of VQE and QAOA, a well known challenge. For all problems, the optimal solution was found using QA and hybrid solvers. This work serves as a hands-on approach to understand quantum annealing, variational quantum algorithms, quantum hardware limitations and current landscape.

Cornell University - arXiv

Devdatt Dubhashi

2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)

Victory Omole

RELATED PAPERS

Proceedings of the Second International Workshop on Post Moores Era Supercomputing

Alexey Galda

SciPost Physics Core

Samuel Lomonaco

Advanced Materials

Yossi Paltiel

Christoph Niedermeier

Constantin Dalyac

henri calandra

SN Comput. Sci.

arXiv: Computational Finance

Hamed Joorati

Quantum Machine Intelligence

Rachel Stromswold

Vishal Sharma

Gary Kochenberger

ACM Computing Surveys

Fabrizio Falchi

2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS)

2020 IEEE International Conference on Quantum Computing and Engineering (QCE)

Catherine McGeoch

Proceedings of the 28th Annual International Conference on Mobile Computing And Networking

John Kaewell

EPJ Quantum Technology

Sixteenth ACM Conference on Recommender Systems

Maurizio Ferrari Dacrema

Physical Review A

Florian Neukart

2019 Tenth International Green and Sustainable Computing Conference (IGSC)

WIREs Computational Molecular Science

Charlotte Deane

Tyler Kharazi

Mary Mehrnoosh Eshaghian-Wilner

IEEE Transactions on Quantum Engineering

Claudio Gambella

Manpreet Jattana

Sofia Fanarioti

Proceedings of the ACM Special Interest Group on Data Communication

Davide Venturelli

2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)

Maxine Khumalo

Scientific Reports

Hirotaka Irie

2021 IEEE European Test Symposium (ETS)

Mahabubul Alam

Anushervon Saidmuradov

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Argonne National Laboratory

The best of both worlds: how to solve real problems on modern quantum computers.

In recent years, quantum devices have become available that enable researchers — for the first time — to use real quantum hardware to begin to solve scientific problems. However, in the near term, the number and quality of qubits (the basic unit of quantum information) for quantum computers are expected to remain limited, making it difficult to use these machines for practical applications.

A hybrid quantum and classical approach may be the answer to tackling this problem with existing quantum hardware. Researchers at the U.S. Department of Energy’s ( DOE ) Argonne National Laboratory and Los Alamos National Laboratory, along with researchers at Clemson University and Fujitsu Laboratories of America, have developed hybrid algorithms to run on quantum machines and have demonstrated them for practical applications using IBM quantum computers (see right rail for description of Argonne’s role in the  IBM Q Hub at Oak Ridge National Laboratory [ ORNL ]) and a D-Wave quantum computer.

“ This approach will enable researchers to use near-term quantum computers to solve applications that support the DOE mission. For example, it can be applied to find community structures in metabolic networks or a microbiome.” — Yuri Alexeev, principal project specialist, Computational Science division

The team’s work is presented in an article entitled ​ “ A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers ” that appears in the June 2019 issue of the Institute of Electrical and Electronics Engineers ( IEEE ) Computer Magazine. 

Concerns about qubit connectivity, high noise levels, the effort required to correct errors, and the scalability of quantum hardware have limited researchers’ ability to deliver the solutions that future quantum computing promises.

The hybrid algorithms that the team developed employ the best features and capabilities of both classical and quantum computers to address these limitations. For example, classical computers have large memories capable of storing huge datasets — a challenge for quantum devices that have only a small number of qubits. On the other hand, quantum algorithms perform better for certain problems than classical algorithms.

To distinguish between the types of computation performed on two completely different types of hardware, the team referred to the classical and quantum stages of hybrid algorithms as central processing units (CPUs) for classical computers and quantum processing units (QPUs) for quantum computers.

The team seized on graph partitioning and clustering as examples of practical and important optimization problems that can already be solved using quantum computers: a small graph problem can be solved directly on a QPU , while larger graph problems require hybrid quantum-classical approaches.

As a problem became too large to run directly on quantum computers, the researchers used decomposition methods to break the problem down into smaller pieces that the QPU could manage — an idea they borrowed from high-performance computing and classical numerical methods.

All the pieces were then assembled into a final solution on the CPU , which not only found better parameters, but also identified the best sub-problem size to solve on a quantum computer.

Such hybrid approaches are not a silver bullet; they do not allow for quantum speedup because using decomposition schemes limits speed as the size of the problem increases. In the next 10 years, though, expected improvements in qubits (quality, count, and connectivity), error correction, and quantum algorithms will decrease runtime and enable more advanced computation.

“ In the meantime,” according to Yuri Alexeev, principal project specialist in the Computational Science division, ​ “ this approach will enable researchers to use near-term quantum computers to solve applications that support the DOE mission. For example, it can be applied to find community structures in metabolic networks or a microbiome.”

Additional paper authors include Ruslan Shaydulin and Ilya Safro of Clemson University, Hayato Ushijima-Mwesigwa of Fujitsu Laboratories of America, and Christian F.A. Negre and Susan M. Mniszewski of Los Alamos National Laboratory.

This research leveraged the computing resources of the Argonne  Leadership Computing Facility, a  DOE Office of Science User Facility;  IBM quantum computers at the Oak Ridge National Laboratory IBM  Q hub; and a D-Wave 2000Q quantum computer provided by the DOE National Nuclear Security Administration’s Advanced Simulation and Computing Program at Los Alamos National Laboratory.

Argonne National Laboratory seeks solutions to pressing national problems in science and technology by conducting leading-edge basic and applied research in virtually every scientific discipline. Argonne is managed by UChicago Argonne, LLC for the U.S. Department of Energy’s Office of Science.

The U.S. Department of Energy’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States and is working to address some of the most pressing challenges of our time. For more information, visit https://​ener​gy​.gov/​s​c​ience .

• News Releases

The best of both worlds: how to solve real problems on modern quantum computers

DOE/Argonne National Laboratory

image: Photo shows Dr. Alexeev with a model of an IBM Q quantum computer. view more 

Credit: Argonne National Laboratory

In recent years, quantum devices have become available that enable researchers — for the first time — to use real quantum hardware to begin to solve scientific problems. However, in the near term, the number and quality of qubits (the basic unit of quantum information) for quantum computers are expected to remain limited, making it difficult to use these machines for practical applications.

A hybrid quantum and classical approach may be the answer to tackling this problem with existing quantum hardware. Researchers at the U.S. Department of Energy’s (DOE) Argonne National Laboratory and Los Alamos National Laboratory, along with researchers at Clemson University and Fujitsu Laboratories of America, have developed hybrid algorithms to run on quantum machines and have demonstrated them for practical applications using IBM quantum computers (see below for description of Argonne's role in the IBM Q Hub at Oak Ridge National Laboratory [ORNL]) and a D-Wave quantum computer.

“This approach will enable researchers to use near-term quantum computers to solve applications that support the DOE mission. For example, it can be applied to find community structures in metabolic networks or a microbiome.” — Yuri Alexeev, principal project specialist, Computational Science division

The team’s work is presented in an article entitled “ A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers ” that appears in the June 2019 issue of the Institute of Electrical and Electronics Engineers (IEEE) Computer Magazine. 

Concerns about qubit connectivity, high noise levels, the effort required to correct errors, and the scalability of quantum hardware have limited researchers’ ability to deliver the solutions that future quantum computing promises.

The hybrid algorithms that the team developed employ the best features and capabilities of both classical and quantum computers to address these limitations. For example, classical computers have large memories capable of storing huge datasets — a challenge for quantum devices that have only a small number of qubits. On the other hand, quantum algorithms perform better for certain problems than classical algorithms.

To distinguish between the types of computation performed on two completely different types of hardware, the team referred to the classical and quantum stages of hybrid algorithms as central processing units (CPUs) for classical computers and quantum processing units (QPUs) for quantum computers.

The team seized on graph partitioning and clustering as examples of practical and important optimization problems that can already be solved using quantum computers: a small graph problem can be solved directly on a QPU, while larger graph problems require hybrid quantum-classical approaches.

As a problem became too large to run directly on quantum computers, the researchers used decomposition methods to break the problem down into smaller pieces that the QPU could manage — an idea they borrowed from high-performance computing and classical numerical methods.

All the pieces were then assembled into a final solution on the CPU, which not only found better parameters, but also identified the best sub-problem size to solve on a quantum computer.

Such hybrid approaches are not a silver bullet; they do not allow for quantum speedup because using decomposition schemes limits speed as the size of the problem increases. In the next 10 years, though, expected improvements in qubits (quality, count, and connectivity), error correction, and quantum algorithms will decrease runtime and enable more advanced computation.

“In the meantime,” according to Yuri Alexeev, principal project specialist in the Computational Science division, “this approach will enable researchers to use near-term quantum computers to solve applications that support the DOE mission. For example, it can be applied to find community structures in metabolic networks or a microbiome.”

Additional paper authors include Ruslan Shaydulin and Ilya Safro of Clemson University, Hayato Ushijima-Mwesigwa of Fujitsu Laboratories of America, and Christian F.A. Negre and Susan M. Mniszewski of Los Alamos National Laboratory.

This research leveraged the computing resources of the Argonne  Leadership Computing Facility, a DOE Office of Science User Facility; IBM quantum computers at the Oak Ridge National Laboratory IBM Q hub; and a D-Wave 2000Q quantum computer provided by the DOE National Nuclear Security Administration's Advanced Simulation and Computing Program at Los Alamos National Laboratory.

About the IBM Q Hub at Oak Ridge National Laboratory... The IBM Q Network is the world's first community of Fortune 500 companies, startups, academic institutions and research labs working with IBM to advance quantum computing and explore practical applications for business and science. As one of the member organizations of the IBM Q Hub at ORNL, Argonne is developing quantum algorithms to help tackle challenges in chemistry and physics. The new algorithms will also be used to model and simulate quantum network architectures and develop hybrid quantum-classical architectures, which combine the power of quantum processors with Argonne's world-class supercomputing resources. Membership in the IBM Q Hub is enabling Argonne researchers to leverage their expertise in scalable algorithms across a broad set of multidisciplinary scientific applications and explore the impact of quantum computing on key areas including quantum chemistry and quantum materials.

Argonne National Laboratory seeks solutions to pressing national problems in science and technology. The nation’s first national laboratory, Argonne conducts leading-edge basic and applied scientific research in virtually every scientific discipline. Argonne researchers work closely with researchers from hundreds of companies, universities, and federal, state and municipal agencies to help them solve their specific problems, advance America’s scientific leadership and prepare the nation for a better future. With employees from more than 60 nations, Argonne is managed by UChicago Argonne, LLC for the U.S. Department of Energy’s Office of Science .

The U.S. Department of Energy’s Office of Science is the single largest supporter of basic research in the physical sciences in the United States and is working to address some of the most pressing challenges of our time. For more information, visit https://energy.gov/science .

10.1109/MC.2019.2908942

Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.

Original Source

The best of both worlds: How to solve real problems on modern quantum computers

In recent years, quantum devices have become available that enable researchers -- for the first time -- to use real quantum hardware to begin to solve scientific problems. However, in the near term, the number and quality of qubits (the basic unit of quantum information) for quantum computers are expected to remain limited, making it difficult to use these machines for practical applications.

A hybrid quantum and classical approach may be the answer to tackling this problem with existing quantum hardware. Researchers at the U.S. Department of Energy's (DOE) Argonne National Laboratory and Los Alamos National Laboratory, along with researchers at Clemson University and Fujitsu Laboratories of America, have developed hybrid algorithms to run on quantum machines and have demonstrated them for practical applications using IBM quantum computers (see below for description of Argonne's role in the IBM Q Hub at Oak Ridge National Laboratory [ORNL]) and a D-Wave quantum computer.

The team's work is presented in an article entitled "A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers" that appears in the June 2019 issue of the Institute of Electrical and Electronics Engineers (IEEE) Computer Magazine.

Concerns about qubit connectivity, high noise levels, the effort required to correct errors, and the scalability of quantum hardware have limited researchers' ability to deliver the solutions that future quantum computing promises.

The hybrid algorithms that the team developed employ the best features and capabilities of both classical and quantum computers to address these limitations. For example, classical computers have large memories capable of storing huge datasets -- a challenge for quantum devices that have only a small number of qubits. On the other hand, quantum algorithms perform better for certain problems than classical algorithms.

To distinguish between the types of computation performed on two completely different types of hardware, the team referred to the classical and quantum stages of hybrid algorithms as central processing units (CPUs) for classical computers and quantum processing units (QPUs) for quantum computers.

The team seized on graph partitioning and clustering as examples of practical and important optimization problems that can already be solved using quantum computers: a small graph problem can be solved directly on a QPU, while larger graph problems require hybrid quantum-classical approaches.

As a problem became too large to run directly on quantum computers, the researchers used decomposition methods to break the problem down into smaller pieces that the QPU could manage -- an idea they borrowed from high-performance computing and classical numerical methods.

All the pieces were then assembled into a final solution on the CPU, which not only found better parameters, but also identified the best sub-problem size to solve on a quantum computer.

Such hybrid approaches are not a silver bullet; they do not allow for quantum speedup because using decomposition schemes limits speed as the size of the problem increases. In the next 10 years, though, expected improvements in qubits (quality, count, and connectivity), error correction, and quantum algorithms will decrease runtime and enable more advanced computation.

"In the meantime," according to Yuri Alexeev, principal project specialist in the Computational Science division, "this approach will enable researchers to use near-term quantum computers to solve applications that support the DOE mission. For example, it can be applied to find community structures in metabolic networks or a microbiome."

• Quantum Computing
• Quantum Physics
• Environmental Issues
• Earth Science
• Hazardous Waste
• Quantum Computers
• Computers and Internet
• Spintronics Research
• Quantum entanglement
• Artificial intelligence
• Quantum computer
• Quantum number
• Introduction to quantum mechanics
• Quantum dot
• Quantum tunnelling

Story Source:

Materials provided by DOE/Argonne National Laboratory . Note: Content may be edited for style and length.

Journal Reference :

• Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Ilya Safro, Susan M. Mniszewski, Yuri Alexeev. A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers . Computer , 2019; 52 (6): 18 DOI: 10.1109/MC.2019.2908942

Cite This Page :

Explore More

• Controlling Shape-Shifting Soft Robots
• Brain Flexibility for a Complex World
• ONe Nova to Rule Them All
• AI Systems Are Skilled at Manipulating Humans
• Planet Glows With Molten Lava
• A Fragment of Human Brain, Mapped
• Symbiosis Solves Long-Standing Marine Mystery
• Surprising Common Ideas in Environmental ...
• 2D All-Organic Perovskites: 2D Electronics
• Generative AI That Imitates Human Motion

Trending Topics

Strange & offbeat.

A Hybrid Quantum-Classical Approach for Solving Combinatorial Problems via Graph Decomposition - Research - College of Engineering - Purdue University

A Hybrid Quantum-Classical Approach for Solving Combinatorial Problems via Graph Decomposition

Project description.

This postdoctoral project focuses on solving combinatorial problems on hybrid quantum-classical machines using separators in graphs to decompose the computation into a collection of computations on smaller graphs. The project will explore solutions for various classes of graphs with good separators, including planar graphs, graphs derived from finite element meshes, and geometric graphs such as disk overlap graphs, all of which possess small separators that decompose the graph into a collection of smaller subgraphs. The motivation for this work is the fact that quantum computers will have only a relatively small number of sparsely connected and noisy qubits for the next several years, which severely limits the size of problems that can be solved on quantum machines. Hence to solve large problems on quantum computers, one needs to decompose the graph into a collection of small subgraphs, which can be accomplished for separable graphs.

Postdoc Qualifications

Co-advisors, short bilbiography.

share this!

May 13, 2024

This article has been reviewed according to Science X's editorial process and policies . Editors have highlighted the following attributes while ensuring the content's credibility:

fact-checked

peer-reviewed publication

trusted source

Novel hybrid scheme speeds the way to simulating nuclear reactions on quantum computers

by US Department of Energy

The nuclear reactions that power the stars and forge the elements emerge from the interactions of the quantum mechanical particles, protons and neutrons. Explaining these processes is one of the most challenging unsolved problems in computational physics.

As the mass of the colliding nuclei grows, the resources required to model them outpace even the most powerful conventional computers. Quantum computers could perform the necessary computations. However, they currently fall short of the required number of reliable and long-lived quantum bits.

Research, published in Physical Review A , combined conventional computers and quantum computers to significantly accelerate the prospects of solving this problem.

The researchers successfully used the hybrid computing scheme to simulate the scattering of two neutrons. This opens a path to computing nuclear reaction rates that are difficult or impossible to measure in a laboratory. These include reaction rates that play a role in astrophysics and national security.

The hybrid scheme will also aid in simulating the properties of other quantum mechanical systems. For example, it could help researchers study the scattering of electrons with quantized atomic vibrations known as phonons, a process that underlies superconductivity.

A team of scientists at the University of Washington, the University of Trento, the Advanced Quantum Testbed (AQT), and Lawrence Livermore National Laboratory proposed a hybrid algorithm for the simulation of the (real time) dynamics of quantum mechanical systems of particles.

In this hybrid approach, the time evolution of the particles' spatial coordinates is carried out on a classical processor, while the evolution of their spin variables is carried out on quantum hardware. The researchers demonstrated this hybrid scheme by simulating the scattering of two neutrons at the AQT.

The demonstration validated the principle of the proposed co-processing scheme after implementing error mitigation strategies to improve the accuracy of the algorithm and adopting theoretical and experimental methods to elucidate the loss of quantum coherence.

Even with the simplicity of the demonstration system this project studied, the results suggest that a generalization of the present hybrid scheme may provide a promising pathway for simulating quantum scattering experiments with a quantum computer .

Leveraging future quantum platforms with longer coherence times and higher quantum gate fidelities, the hybrid algorithm would enable the robust computation of complex nuclear reactions important for astrophysics and technological applications of nuclear science.

Journal information: Physical Review A

Provided by US Department of Energy

Explore further

Feedback to editors

Exploring the ultrasmall and ultrafast through advances in attosecond science

9 hours ago

Machine learning and AI aid in predicting molecular selectivity of chemical reactions

Persistent strain of cholera defends itself against forces of change, scientists find

Study reveals insights into protein evolution

Scientists help unravel life's cosmic beginnings

Physicists create five-lane superhighway for electrons

10 hours ago

Fruit fly testes offer potential tool against harmful insects

Researchers find new approach for antibiotic development

Exceptionally large transverse thermoelectric effect produced by combining thermoelectric and magnetic materials

Chemical analysis of natural CO₂ rise over the last 50,000 years shows that today's rate is 10 times faster

Relevant physicsforums posts, qubits state calculation.

7 hours ago

What are anomalies in quantum field theory?

21 hours ago

Quantum mechanics formalisms and conservation of energy

May 12, 2024

Eigenstates of particle with 1/2 spin (qbit)

When and why can ∂p/∂t=0 in position space.

May 11, 2024

EPR in Bohm formulation

More from Quantum Physics

Related Stories

Springing simulations forward with quantum computing

Apr 22, 2024

Combining classical and quantum computing opens door to new discoveries

Jun 15, 2021

Physical features boost the efficiency of quantum simulations

Dec 8, 2021

Revolutionary hardware unveils new quantum computing model

Aug 15, 2023

CCNY team in quantum algorithm breakthrough

Nov 13, 2020

New quantum computing algorithm skips past time limits imposed by decoherence

Oct 5, 2020

Recommended for you

Scientists discover 'weird' statistics of electrons ejected by intense quantum light

14 hours ago

New surface acoustic wave techniques could lead to surfing a quantum internet

16 hours ago

Researchers create complex quantum graph states with photons

Researchers achieve first condensation of non-ground state cesium atoms

17 hours ago

Spectral evidence found for Dirac spinons in a kagome lattice antiferromagnet

Let us know if there is a problem with our content.

Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form . For general feedback, use the public comments section below (please adhere to guidelines ).

Please select the most appropriate category to facilitate processing of your request

Thank you for taking time to provide your feedback to the editors.

Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.

E-mail the story

Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient's address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Phys.org in any form.

Newsletter sign up

Get weekly and/or daily updates delivered to your inbox. You can unsubscribe at any time and we'll never share your details to third parties.

More information Privacy policy

Donate and enjoy an ad-free experience

We keep our content available to everyone. Consider supporting Science X's mission by getting a premium account.

E-mail newsletter

Novel quantum algorithm proposed for high-quality solutions to combinatorial optimization problems

C ombinatorial optimization problems (COPs) have applications in many different fields such as logistics, supply chain management, machine learning, material design and drug discovery, among others, for finding the optimal solution to complex problems. These problems are usually very computationally intensive using classical computers and thus solving COPs using quantum computers has attracted significant attention from both academia and industry.

Quantum computers take advantage of the quantum property of superposition, using specialized qubits, that can exist in an infinite yet contained number of states of 0 or 1 or any combination of the two, to quickly solve large problems. However, when COPs involve constraints, conventional quantum algorithms like adiabatic quantum annealing struggle to obtain a near-optimal solution within the operation time of quantum computers.

Recent advances in quantum technology have led to devices such as quantum annealers and gate-type quantum devices that provide suitable platforms for solving COPs. Unfortunately, they are susceptible to noise, which limits their applicability to quantum algorithms with low computational costs.

To address this challenge, Assistant Professor Tatsuhiko Shirai and Professor Nozomu Togawa from the Department of Computer Science and Communications Engineering at Waseda University in Japan have recently developed a post-processing variationally scheduled quantum algorithm (pVSQA). Their study was published in the journal IEEE Transactions on Quantum Engineering .

"The two main methods for solving COPs with quantum devices are variational scheduling and post-processing. Our algorithm combines variational scheduling with a post-processing method that transforms infeasible solutions into feasible ones, allowing us to achieve near-optimal solutions for constrained COPs on both quantum annealers and gate-based quantum computers," explains Dr. Shirai.

The innovative pVSQA algorithm uses a quantum device to first generate a variational quantum state via quantum computation. This is then used to generate a probability distribution function which consists of all the feasible and infeasible solutions that are within the constraints of the COP.

Next, the post-processing method transforms the infeasible solutions into feasible ones, leaving the probability distribution with only feasible solutions. A classical computer is then used to calculate an energy expectation value of the cost function using this new probability distribution. Repeating this calculation results in a near-optimal solution.

The researchers analyzed the performance of this algorithm using both a simulator and real quantum devices such as a quantum annealer and a gate-type quantum device. The experiments revealed that pVSQA achieves a near-optimal performance within a predetermined time on the simulator and outperforms conventional quantum algorithms without post-processing on real quantum devices.

Dr. Shirai said, "Drastic social transformations are urgently needed to address various social issues. Examples include the realization of a carbon-neutral society to solve climate change issues and the realization of sustainable development goals to address issues such as increased energy demand and food shortage.

"Efficiently solving combinatorial optimization problems is at the heart of achieving these transformations. Our new method will play a significant role in realizing these long-term social transformations."

In conclusion, this study marks a significant step forward for using quantum computers for solving COPs, holding promise for addressing complex real-world problems across various domains.

More information: Tatsuhiko Shirai et al, Post-Processing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems, IEEE Transactions on Quantum Engineering (2024). DOI: 10.1109/TQE.2024.3376721

Provided by Waseda University

Smart. Open. Grounded. Inventive. Read our Ideas Made to Matter.

Which program is right for you?

Through intellectual rigor and experiential learning, this full-time, two-year MBA program develops leaders who make a difference in the world.

A rigorous, hands-on program that prepares adaptive problem solvers for premier finance careers.

A 12-month program focused on applying the tools of modern data science, optimization and machine learning to solve real-world business problems.

Earn your MBA and SM in engineering with this transformative two-year program.

Combine an international MBA with a deep dive into management science. A special opportunity for partner and affiliate schools only.

A doctoral program that produces outstanding scholars who are leading in their fields of research.

Bring a business perspective to your technical and quantitative expertise with a bachelor’s degree in management, business analytics, or finance.

A joint program for mid-career professionals that integrates engineering and systems thinking. Earn your master’s degree in engineering and management.

An interdisciplinary program that combines engineering, management, and design, leading to a master’s degree in engineering and management.

Executive Programs

A full-time MBA program for mid-career leaders eager to dedicate one year of discovery for a lifetime of impact.

This 20-month MBA program equips experienced executives to enhance their impact on their organizations and the world.

Non-degree programs for senior executives and high-potential managers.

A non-degree, customizable program for mid-career professionals.

Credit: metamorworks / Shutterstock

Will quantum computing be better for your business?

MIT Sloan Office of Communications

Nov 17, 2023

New MIT Sloan research presents a framework for business leaders to analyze whether to use quantum or traditional computing to yield the best outcome

Cambridge, MA, Nov. 17, 2023 —  MIT Sloan School of Management  researchers present a new framework for understanding in which circumstances quantum computing will provide significant advantages to businesses, and when traditional computing will be the more economical choice. 

“ The Quantum Tortoise and the Classical Hare: A simple framework for understanding which problems quantum computing will accelerate (and which it will not) ” is co-authored by  Neil Thompson , research scientist at MIT Sloan and the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL),  Sukwoong Choi , assistant professor at University at Albany and digital fellow at MIT Initiative on the Digital Economy, and  William S. Moses  (MIT CSAIL PhD ’23), incoming assistant professor at University of Illinois Urbana-Champaign. This work is part of a larger collaboration between Accenture and the MIT  Initiative on the Digital Economy , and is funded by Accenture.

“Many business leaders are looking to quantum computing as the promising successor to classical computing, but research shows–and leaders in  quantum computing agree–it will continue to underperform classical computing in many areas,” says Thompson. “As a result, to understand where quantum computing will perform better first requires understanding  why  it can be.” 

The research paper finds that quantum computers must meet two conditions to yield an improvement on classical computers. First, they  must be powerful enough to solve the problem at hand, which is a challenge because  most quantum computers are currently so small they can only run  toy problems , such as factoring numbers so small that using a  classical computer makes more sense). Second, it must gain enough of an advantage from having a better algorithm that it can run a problem in less time than it would take a classical computer. 

While these factors sound straightforward, they have powerful implications regarding which problems will benefit from quantum computing and which won’t. Better yet, they can often be calculated before investing in a project. 

“Companies often consistently face fixed sets of problems, and decision-makers might wonder if these problems could be solved more quickly and efficiently with quantum computing,” Thompson says. “Our framework provides a way to analyze the potential impact of switching to quantum computing before making the investment.” 

Thompson notes this research can be used across industries—such as automotive, chemistry, and finance—where companies have started to examine applications of quantum computing. In particular, the framework considers how well a quantum computer might solve a problem using  Shor’s algorithm , which is one of a few well-known quantum algorithms, compared with how well a classical computer might solve a problem. The analysis reveals that many problems, particularly those of small to moderate size, will most likely  not  benefit from quantum computing in the near-term. 

The reason that quantum computers will often be slower than classical ones (and therefore be the “tortoise” in this paper) is that the hardware itself runs slower, doing fewer operations per second. 

“You might think this would doom them to always be slower, but sometimes they have more efficient ways of solving problems that are unavailable to classical computers,” says Thompson These quantum algorithms, if they provide enough of an advantage, can allow quantum computers to outpace their classical brethren. Unfortunately, even if quantum computers could theoretically be better, they often aren’t in practice because current and near-term quantum computers have limited computational capacity, so they aren’t powerful enough to run the problems where quantum computers are better.

The framework has an economic dimension, which the authors term “quantum economic advantage.” This represents the crossover point, when businesses would start wanting to use quantum computing because it represents the lowest-cost way of achieving a particular level of performance. 

This study gives managers and their teams the tools for understanding when quantum economic advantage is achieved, which requires evaluating the two key criteria:

• Feasibility: Can the quantum computer, given its speed and size, effectively handle the problem at hand?
• Algorithm Advantage: If the quantum computer is capable, would it actually process the task faster than a classical computer of comparable cost? 

“We need to consider the speed of the computer versus the route,” Thompson said. “Thinking of it like a race, in getting from point A to point B, the algorithm is the route. If the race is short, it may not be worth investing in better route planning. For it to be worth it, it has to be a longer race.”

A consequence of these conditions is that larger problems show the most benefit from quantum computing. For example, computers might be used to look for a particular DNA sequence in a human genome. While the best classical algorithm for this problem is less powerful than the best quantum algorithm, classical computers are much faster and can run more applications at the same time. As problem sizes get larger, the “algorithmic benefit” of quantum computing becomes more important. In particular, the length of a typical human genome (~3 billion DNA “letters”) is not big enough for quantum to be better, so it shouldn’t be used for this purpose. By contrast, large databases of genomes (with more than 1 trillion letters) could be large enough where quantum is a better option.

“Ultimately, this research suggests that quantum computing will be the more attractive option under one of two conditions for businesses,” Thompson said. “First, that the quantum algorithm is exponentially faster than the classical algorithm, or second, that the quantum algorithm is significantly better and the problem size is quite large.”

Building on this analysis, Thompson says future research will delve into which specific problems and industries will benefit most from quantum—and which won’t. 

About the MIT Sloan School of Management

The MIT Sloan School of Management is where smart, independent leaders come together to solve problems, create new organizations, and improve the world. Learn more at mitsloan.mit.edu .

Related Articles