Quantum Hamiltonian Descent

Quantum Hamiltonian Descent (QHD) is a novel framework of quantum algorithms for continuous optimization.

This is a joint work by Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu.

Data

All the experiment results (raw data) are available here.

1. NonCVX-2d: We test two quantum algorithms (QHD and QAA) and classical algorithms (Nesterov's accelerated GD and SGD) for 22 optimization instances. Most of the instance problems are non-convex and thus considered hard for classical algorithms. In each instance folder (e.g., /NonCVX-2d/ackley/), the following data are provided:

• Wave functions drawn from QHD evolution (resolution = 128, snapshot interval = 5e-1, total evolution time = 10), e.g., /ackley_QHD128_WFN/;
• Wave functions drawn from QHD evolution (resolution = 256, snapshot interval = 5e-1, total evolution time = 10), e.g., /ackley_QHD256_WFN/;
• Loss curve of QHD (resolution = 128, with snapshot_times and loss_val), e.g., /ackley_QHD128_loss.npy;
• Loss curve of QHD (resolution = 256, with snapshot_times and loss_val), e.g., /ackley_QHD256_loss.npy;
• Wave functions and loss curve of QAA (resolution = 64, total evolution time = 10), e.g., /ackley_QAA64_T10.mat;
• Wave functions and loss curve of QAA (resolution = 128, total evolution time = 10), e.g., /ackley_QAA128_T10.mat;
• Solution paths of Nesterov's accelerated gradient descent algorithm (num. of samples = 1000, stepsize = 1e-3, maximal iteration = 1e4, effective total evolution time = 10), e.g., /ackley_NAGD.mat;
• Solution paths of stochastic gradient descent algorithm (sample size = 1000, stepsize = 1e-3, maximal iteration = 1e4, effective total evolution time = 10), e.g., /ackley_SGD.mat.

2. QP: We test QHD and other algorithms for 160 randomly generated quadratic programming instances (dimension = 5, 50, 60, 75). These problems are non-convex (with indefinite Hessian) and have box constraints. We split the test problems into 4 benchmarks by their dimensions. In each instance folder (e.g., /QP/QP-50d-5s/instance_0/), the following data are provided:

• Quadratic programming instance description (Q, b, Q_c, b_c), e.g., /instance_0.npy;
• Samples from QHD (sample size = 1000, resolution = 8, implemented on D-Wave Advantage 6.1, evolution time = 800 microseconds), e.g., /advantage6_qhd_rez8_sample_0.npy;
• Post-processed solutions of QHD (sample size = 1000, post-processed by Scipy TNC) and the corresponding runtime data, e.g., /tnc_post_advantage6_qhd_rez8_sample_0.npy and /tnc_post_advantage6_qhd_rez8_runtime_0.npy;
• Samples from QAA (sample size = 1000, resolution = 8, implemented on D-Wave Advantage 6.1, evolution time = 800 microseconds), e.g., /advantage6_qaa_rez8_sample_0.npy;
• Post-processed solutions of QAA (sample size = 1000, post-processed by Scipy TNC) and the corresponding runtime data, e.g., /tnc_post_advantage6_qaa_rez8_sample_0.npy and /tnc_post_advantage6_qaa_rez8_runtime_0.npy;
• Random initializations (sample size = 1000, used by all classical local NLP solvers), e.g., /rand_init_0.npy;
• Solutions returned by Gurobi (used as the ground truth), e.g., /gurobi_solution_0.npy;
• Solutions returned by Scipy TNC solver and the corresponding runtime data, e.g., /tnc_sample_0.npy and /tnc_runtime_0.npy;
• Solutions returned by Ipopt and the corresponding runtime data, e.g., /ipopt_sample_0.npy and /ipopt_runtime_0.npy;
• Solutions returned by SNOPT and the corresponding runtime data, e.g., /snopt_sample_0.npy and /snopt_runtime_0.npy;
• Solutions returned by MatLab Fmincon (solver='sqp') function and the corresponding runtime data, e.g., /matlab_sqp_sample_0.npy and /matlab_sqp_runtime_0.npy;
• Solutions returned by QCQP and the corresponding runtime data, e.g., /qcqp_sample_0.npy and /qcqp_runtime_0.npy;

There are 10 instances in the 5-dimensional benchmark /QP/QP-5d/. For these problems, we also run numerical simulations of DWave-implemented QHD and QAA (evolution time = 1e3 ns = 1 microsecond). The numerical simulation is performed on a classical computer and we use the parameters provided in D-Wave's official doc.

• Samples from simulated QHD (sample size = 1000, resolution = 8, evolution time = 1 microsecond), e.g., /advantage6_sim_qhd_rez8_T1000_sample_0.npy;
• Post-processed solutions of simulated QHD (sample size = 1000, post-processed by Scipy TNC) and the corresponding runtime data, e.g., /tnc_post_advantage6_sim_qhd_rez8_T1000_sample_0.npy and /tnc_post_advantage6_sim_qhd_rez8_T1000_runtime_0.npy;
• Samples from simulated QAA (sample size = 1000, resolution = 8, evolution time = 1 microsecond), e.g., /advantage6_sim_qaa_rez8_T1000_sample_0.npy;
• Post-processed solutions of simulated QAA (sample size = 1000, post-processed by Scipy TNC) and the corresponding runtime data, e.g., /tnc_post_advantage6_sim_qaa_rez8_T1000_sample_0.npy and /tnc_post_advantage6_sim_qaa_rez8_T1000_runtime_0.npy;

Visualization of Experiment data