Project 8: Quantum-Inspired Classical Optimization

Build a classical optimizer inspired by quantum annealing ideas.

Project Overview

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate Weekend
Main Language Python
Alternative Languages C++, Julia
Knowledge Area Optimization
Tools Plotting tool
Main Book “Quantum Computing: An Applied Approach” by Jack Hidary

What you’ll build: A classical optimizer that mimics annealing or QUBO solving for small problems.

Why it teaches quantum: It builds intuition about energy landscapes and optimization without quantum hardware.

Core challenges you’ll face:

  • Defining a cost function as an energy landscape
  • Implementing a cooling or annealing schedule
  • Comparing results to brute force

Real World Outcome

You will solve small QUBO problems and visualize convergence over time.

Example Output:

$ python anneal.py --problem maxcut --n 6
Best energy: -8
Converged in 400 steps

Verification steps:

  • Compare with brute-force minimum
  • Plot energy vs iteration

The Core Question You’re Answering

“How can quantum ideas inspire better classical optimization?”

This builds intuition for quantum annealing.

Concepts You Must Understand First

Stop and research these before coding:

  1. QUBO formulation
    • How do you express problems as quadratic binary optimization?
    • Book Reference: “Quantum Computing: An Applied Approach” by Jack Hidary, Ch. 10
  2. Annealing
    • Why does slow cooling help escape local minima?
    • Book Reference: “Optimization by Simulated Annealing” by Kirkpatrick et al.
  3. Energy landscapes
    • How do local minima trap optimizers?
    • Book Reference: “Algorithms for Optimization” by Mykel J. Kochenderfer, Ch. 7

Questions to Guide Your Design

  1. Schedule design
    • How will you set initial temperature and cooling rate?
    • How will you detect convergence?
  2. Problem encoding
    • Which small problems will you test (Max-Cut, SAT)?
    • How will you validate solutions?

Thinking Exercise

Energy Intuition

For a 2-bit QUBO, list all states and their energies. Identify the minimum.

Questions while working:

  • Why is brute force feasible only for small n?
  • How does annealing explore the space?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is a QUBO problem?”
  2. “Why does annealing help optimization?”
  3. “How do you choose a cooling schedule?”
  4. “What is the difference between classical and quantum annealing?”
  5. “How do you validate optimization results?”

Hints in Layers

Hint 1: Starting Point Start with very small QUBO matrices.

Hint 2: Next Level Implement a simple simulated annealing loop.

Hint 3: Technical Details Track acceptance rates as temperature decreases.

Hint 4: Tools/Debugging Plot energy trajectories across multiple runs.

Books That Will Help

Topic Book Chapter
QUBO “Quantum Computing: An Applied Approach” by Jack Hidary Ch. 10
Annealing “Optimization by Simulated Annealing” by Kirkpatrick et al. Section 2
Energy landscapes “Algorithms for Optimization” by Mykel J. Kochenderfer Ch. 7

Implementation Hints

  • Use random restarts to avoid local minima.
  • Keep problem size small for validation.
  • Compare against brute-force results.

Learning Milestones

  1. First milestone: You can encode a QUBO problem.
  2. Second milestone: You can run annealing and find low energy.
  3. Final milestone: You can explain annealing behavior and limits.