• Skip to primary navigation
  • Skip to main content
SRI InternationalSRI mobile logo

SRI International

SRI International - American Nonprofit Research Institute

  • About
    • Blog
    • Press room
  • Expertise
    • Advanced imaging systems
    • Artificial intelligence
    • Biomedical R&D services
    • Biomedical sciences
    • Computer vision
    • Cyber & formal methods
    • Education and learning
    • Innovation strategy and policy
    • National security
    • Ocean & space
    • Quantum
    • QED-C
    • Robotics, sensors & devices
    • Speech & natural language
    • Video test & measurement
  • Ventures
  • NSIC
  • Careers
  • Contact
  • 日本支社
Show Search
Hide Search
Quantum publications August 19, 2021 Article

Quantum Optimization Heuristics with an Application to Knapsack Problems

Karim Eldefrawy, Nicholas Genise August 19, 2021

SRI Authors: Karim Eldefrawy, Nicholas Genise

Citation

Copy to clipboard


Wim van Dam, Karim Eldefrawy, Nicholas Genise, Natalie Parham (2021). Quantum Optimization Heuristics with an Application to Knapsack Problems. arXiv:2108.08805 [quant-ph].

Abstract

This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems. The first technique describes how to use the outcome of a prior greedy classical algorithm to define an initial quantum state and mixing operation to adjust the quantum optimization algorithm to explore the possible answers around this initial greedy solution. The second technique is used to nudge the quantum exploration to avoid the local minima around the greedy solutions. To analyze the benefits of these two techniques we run the quantum algorithm on known hard instances of the Knapsack Problem using unit depth quantum circuits. The results show that the adjusted quantum optimization heuristics typically perform better than various classical heuristics.

↓ View online

Share this

Facebooktwitterlinkedinmail

Publication, Quantum publications Article

How can we help?

Once you hit send…

We’ll match your inquiry to the person who can best help you.

Expect a response within 48 hours.

Our privacy policy
Career call to action image

Make your own mark.

Search jobs
Our work

Case studies

Publications

Timeline of innovation

Areas of expertise

Blog

Institute

Leadership

Press room

Media inquiries

Compliance

Privacy policy

Careers

Job listings

Contact

SRI Ventures

Our locations

Headquarters

333 Ravenswood Ave
Menlo Park, CA 94025 USA

+1 (650) 859-2000

Subscribe to our newsletter

日本支社

SRI International

  • Privacy Policy
  • Cookies
  • DMCA
  • Copyright © 2022 SRI International