Fidelity-based Deep Adiabatic Scheduling
Authors: Eli Ovits
Lior Wolf
Venue: ICLR 2021 Spotlight (2021)

Abstract: Adiabatic quantum computation is a form of computation that acts by slowly interpolating a quantum system between an easy to prepare initial state and a final state that represents a solution to a given computational problem. The choice of the interpolation schedule is critical to the performance: if at a certain time point, the evolution is too rapid, the system has a high probability to transfer to a higher energy state, which does not represent a solution to the problem. On the other hand, an evolution that is too slow leads to a loss of computation time and increases the probability of failure due to decoherence. In this work, we train deep neural models to produce optimal schedules that are conditioned on the problem at hand.  We consider two types of problem representation: the Hamiltonian form, and the Quadratic Unconstrained Binary Optimization (QUBO) form. A novel loss function that scores schedules according to their approximated success probability is introduced. We benchmark our approach on random QUBO problems, Grover search, 3-SAT, and MAX-CUT problems and show that our approach outperforms, by a sizable margin, the linear schedules as well as alternative approaches that were very recently proposed.

Published as a conference paper at ICLR 2021
FIDELITY-BASED DEEP ADIABATIC SCHEDULING
Eli Ovits & Lior Wolf Tel Aviv University
ABSTRACT
Adiabatic quantum computation is form of computation that acts by slowly in- terpolating a quantum system between an easy to prepare initial state and final state that represents a solution to a given computational problem. The choice of the interpolation schedule is critical to the performance: if at certain time point, the evolution too rapid, the system has a high probability to transfer to a higher energy state, which does not represent a solution to the problem. On the other hand, an evolution that is too slow leads to a loss of computation time and increases the probability of failure due to decoherence. In this work, train deep neural models to produce optimal schedules that are conditioned on the prob- lem at hand. We consider two types of problem representation: the Hamiltonian form, and the Quadratic Unconstrained Binary Optimization (QUBO) form. A novel loss function that scores schedules according to their approximated suc- cess probability is introduced. We benchmark our approach on random QUBO problems, Grover search, 3-SAT, and MAX-CUT problems and show that our ap- proach outperforms, by sizable margin, the linear schedules as well as alternative approaches that were very recently proposed.
INTRODUCTION
Many of the algorithms developed for quantum computing employ the quantum circuit model, in which a quantum state involving multiple qubits undergoes a series of invertible transformations. However, an alternative model, called Adiabatic Quantum Computation (AQC) (Farhi et al.) 2000) McGeoch) 2014). is used in some of the leading quantum computers, such as those manufactured by D-Wave Systems (Boixo et al. (0044). AQC algorithms achieve quantum speedups over classical algorithms (Albash & Lidar 2018), and are polynomially equivalent to the quantum circuit model Aharonov al. 2008).
In AQC, given a computational problem Q, e.g., a specific instance of a 3SAT problem, a physical system is slowly evolved until specific quantum state that represents proper solution achieved. Each AQC run involves three components:
An initial Hamiltonian H4, chosen such that its ground state (in matrix terms, the minimal eigenvector of Ho) is easy to prepare and there is large spectral gap. This is typically independent of the specific instance of Q.
2. A final Hamiltonian H, designed such that its ground state corresponds to the solution of the problem instance Q.
3. An adiabatic schedule, which is a strictly increasing function s(t) that maps point in time
0 < S ty where t, total computation time, to the entire interval [0, 1] (i.e., s(0) = 0, s(t,) = 1, and s(t,) < s(tg) iff t < is and vice versa).
These three components define a single time-dependent Hamiltonian H(t), which can be seen as an algorithm for solving Q:
H(I) = (1 - s(t)) Ho + s(f) Hp
(1)
At the end of the adiabatic calculation, the quantum state is measured. The square the overlap between the quantum state and ground state of the final Hamiltonian, is the fidelity, and represents the probability of success in finding the correct solution. An AQC algorithm that evolved over an insufficient time period (a schedule that is too fast) will have low fidelity. Finding the optimal

---

Published as a conference paper at ICLR 2021
schedule, i.e,, the one that would lead to high fidelity and would keep the time complexity of the algorithm minimal is, therefore, of a great value. However, for most problems, an analytical solution for the optimal schedule does not exist (Albash & Lidar 2018).
Attempts were made to optimize specific aspects of the adiabatic schedule by using iterative methods (Zeng et al. 2015) by direct derivations (Susa al. 2018). Performance was evaluated by exam- ining characteristics of the resulting dynamic (e.g. the minimum energy gap) and no improvement was demonstrated on the full quantum calculation.
Previous attemppts to employ Al for the task of finding the optimal schedule have relied on Rein- forcement Learning (Lin et al. 2020; Chen et al. 2020). While these methods were able to find schedules that are better than the linear path, they are limited to either learning one path for a fam- ily of problems (without considering the specific instance) or rerunning the AQC of a specific instance Q multiple times in order to optimize the schedule.
In our work, supervised learning employed in order to generalize from a training set of problems and their optimal paths to new problem instances. Training is done offline and the schedule our neural model outputs is function of the specific problem instance. The problem instance is encoded in our model either based on the final Hamiltonian Hp or directly based on the problem.
The suggested neural models are tested using several different problem types: Grover search prob- lems, 3SAT and MAX-CUT problems, and randomized QUBO problems. We show that the evo- lution schedules suggested by our model greatly outperform the naive linear evolution schedule, as well as those schedules provided by the recent RL methods, and allow for much shorter total evolution times.
BACKGROUND
The goal of the scheduling task is to find schedule st)) that maximizes the probability to get the correct answer for instance Q, using H₂ and Hp over an adiabatic quantum computer. The solution Q is coded as the lowest energy eigenstate of Hp.
In order to achieve the solution state with high probability, the system must be evolved "sufficiently slowly". The adiabatic theorem (Roland & Cerf 2002 AAbash & Lidar] 2018 Rezakhani et al., 2009) is used to analyze how fast could this evolution be. It states that the probability to reach the desired state the end of the adiabatic calculation is 1 e2 for <<<<<>
( (L) at H(()) [Fa(())
SE
g2)
where the Dirac notation (Tumulka, 2009 is used") Et(t) (E) is the ground state (first excited state) of the time dependent Hamiltonian H(t), i.e., the eigenstates that corresponds to the lowest (2nd lowest) eigenvalue, and g(() is the time dependent instantaneous spectral gap between the smallest and second smallest eigenvalues of H(t).
Let be the total calculation time. let st) be an evolution schedule, such that s00) = 0, s(t,) 1. Applying the adiabatic condition for st), we get
(Ei
da d H(s(t)) (s((()))
< ds dt
(²(s)
de de
Se (E((s) 4H(ss (b()
(3)
gd (s())
we could solve for t(s) by integration to get
(E) H(s) Eo(())
t(s)
de
ds
(4)
(s(s)
and the total required evolution time is
1
(E((s)
A AH(s) Eo(s))
1 ((s
de
ds
(5)
g2(s)
See appendix A for the conventional matrix notation.
2

---

Published as a conference paper at ICLR 2021
We note that finding a numerical solution for eq sition of H(z).
4 requires calculating the full eigenvalue decompo-
2.1 MOST-RELATED WORK
Two recent contributions use deep learning in order obtain, for given f,, a schedule that outper- form the linear schedule. [Lin et al. (2020) suggest using deep reinforcement learning in order to find an optimal schedule for each specific class of problems (e.g.. 3SAT problems of a certain size). In contrast, we study the problem of finding schedules for generic problem instances. They train and benchmark their performance by simulating an adiabatic quantum computer, and scoring the com- putation results for randomly chosen problem instances. Their results are generally better than the naive linear schedule, and the solution produced by their neural network somewhat transferable for larger problem sizes.
Chen et al. 2020) also use RL to construct, given a l,, a schedule for 3SAT problems. The most successful technique suggested is Monte Carlo Tree Search (MCTS, Silver et al. (2016)), which produces results that significantly outperform the linear schedule. This technique requires running the adiabatic evolution process many times for each problem, in order to find successful schedule. An approach inspired by alpha-zero (Silver et al. 2018) is used to adapt the generic MCTS solution specific problem class, while requiring only few additional rounds of the adiabatic process for each new instance. In our method, we do not require any run given a new problem instance.
3 METHOD
We consider two types of deep neural models. The first model is designed to get the problem Hamiltonian Hp as input. For qubit problem, the problem Hamiltonian is generally of size 2n x 2 In this work, we consider problem Hamiltonians which are diagonal and can be represented by vector of size 2". This scenario covers both the Grover search problem and the 3SAT problem we present in Sec.
The second model is designed to get quadratic unconstrained binary optimization (QUBO) problem as an input. The QUBO problem has the following form:
I argmmnn (x Q=),
where x a vector of binary variables and Q E R defines the specific QUBO instance. The QUBO problem is NP-Con XP-Complete, and many types of common problems can be reduced to QUBO Glover et al. 2018). The QUBO formulation is of special interest in the context adiabatic quan- tum computing, since it allows relatively easy mapping to real quantum annealing devices that do not possess full qubit connectivity (Cruz-Santos et al. 2019).
A QUBO problem Q can be converted to the Hamiltonian form in the following fashion:
1 + of Qui +0)+ ) Σ
Qui + o
1 1+02)
Hp Σ
2
(
where of is the Pauli matrix a= operating only on qubit (Liboff 2003). The resulting Hp is of size 2n x 2 and is diagonal.
The prediction target of our models is the desired normalized schedule 8(t), which is defined over the range [0, 1] as s(t) = stt/t,). For the purpose of estimation, it is sampled at 100 points in the interval [o, 1]. The representation of this schedule is given as vector d E [o, 1]99. which captures the temporal derivative of the schedule. In other words, dl is trained to hold the differences between consecutive points on the path, i.e., element is given by d, 8((i + 1)/100) (ii/100). Note that the sum of d one.
3.1 UNIVERSALITY OF THE OPTIMAL SCHEDULE
The reason that work with the normalized schedule is that the optimal evolution schedule is not dependent upon the choice of ty. As shown next, for every time budget ty, the same normalized schedule would provide the highest fidelity (neglecting decoherence).
3

---

Published as a conference paper at ICLR 2021
[0.ty] [0, 1] be suggested evolution schedule, which outperforms different sug- gested schedule $2()), for specific t, = T1. Le. achieves a greater fidelity at the end of the schedule for specific problem instance Q. Then, Thm. shows that 81 (t) outperforms s2(t) for every possible choice of y for the same problem Q.
Let s1(t)
Theorem 1. Let (t) and 82(t) be two monotonically increasing fully differentiable bijective func- tions from (0, = 71] to [0, 1|. Let Q be optimization problem, and assume that (t( achieves greater fidelity than (t) at the end of a quantum adiabatic computation for Q with total evolution time is Ti- Then, for any other choice ty T2. the scaled schedule si ( [ t) will achieve greater fulelity than 82( (1) for an adiabatic computation over the same problem Q with total evolution time I 72.
The proof can be found in appendix B
3.2 ARCHITECTURE
The model architectures are straightforward and no substantial effort was done to optimize them. The Hamiltonian as input model has seven fully connected layers, with decreasing sizes: 4096, 2048, 2048, 1024, 512, and finally the output layer, which, as mentioned, is of size 99.
For the QUBO model, in which the input is a matrix, two part architecture was used. In the first part, five layers of 2D convolution was employed, with kernel size of 3 x 3, for 64 kernels. The output from the convolution layers was then flattened to vector of size 64n², and fed to the second part of the network, consisted of five fully connected layers, with decreasing dimensions of 2048, 1024, 1024, 512, and finally the output layer of size 99.
This output layers in both models normalized to have of one. For both models, the SELU activation function Klambauer et al. (017) was used for all layers, except the final layer, which used the sigmoid (logistic) function.
3.3 FIDELITY BASED Loss FUNCTION
Let (x((() is the state of the quantum system at time sl.. The fidelity of the QAC is given by Farhi et al., 2000)
Psuccess (Eb = 1) () (t)+tt))))
(8)
where (Ee(s 1)] is the l-th eigenstate of the parameter dependent evolution Hamiltonian H(s), such that (Eo(s = 1)] is the ground state of the final Hamiltonian Hp. Finding (Eo(s 1)] requires performing eigenvalue decomposition for Hp. which equivalent to solving the original optimiza- tion problem, and is done for the training set.
The quantum state (t)) is evolving according the Schrödinger equation
d
dt (v)))) H((t) (+)))
A brute force approach for finding Peuccess is to numerically solve the Schrödinger equation, see appendix[C] This full numerical calculation is, however, too intense to be practical. We next develop an approximate method that would be easier to compute and still be physically meaningful. is based on the adiabatic local evolution speed limit from Eq. 3
ds
(s(s (E) 4 H(s) Eo(3)
<
(10)
dt
This inequality could be used as a local condition for convergence of any suggested path. We define
g2(ss
d
(11)
(+)
de H(s) Eo(s))
We would like to use the local condition to create a global convergence condition for a full suggested path s(t), < < lg. To do so, integrate both sides of Eq. 10 over the suggested schedule
4

---

Published as a conference paper at ICLR 2021
This integral represents mean value of the local adiabatic condition, for every point in the suggested schedule.
ds
(12)
(i)
We note that integrand is always positive (assuming s(t) is monotonically increasing). Recall that the adiabatic theorem ties to the fidelity: = v1 Psuccess. By defining the right hand side of [q as our loss function, we ensure that any training process that minimizes Eq. [2 will maximize the fidelity. Recall that the vector d that the network outputs is vector of differences, therefore, approximates the local derivatives of the obtained path. Let s* be the optimal normalized path, which we estimate for each training sample. The loss function is, therefore, defined
99
df
[(d, 8')= 98 ( (i/100))
(13)
The values of gE are precomputed along the optimal path 8* for efficiency. While the denominator is obtained on points that do not correspond to the estimated path (the commutative sum of d), the approximation becomes increasingly accurate at the estimated path appraoches the optimal one.
3.4 TRAINING DATA AND THE TRAINING PROCESS
In order train the QUBO problem model, produced training dataset of 10,000 random QUBO instances for each problem size: n 6, 8, 10. The QUBO problems were generated by sampling independently, from the normal distribution, each coefficient of the problem matrix Q. The entire matrix Q was then multiplied by a single random normal variable.
We approximated an optimal evolution schedule for each problem, by calculating the full eigenvalue decomposition of Hd as described in 2 We also calculated the value of g(s(t)) for each problem.
For the model that lems, converted to the Hamiltonian form. In addition, we added another 500 cases of randomized Hamiltonians with randomized values around distinct energy levels. For each Hamiltonian, We first randomized an energy level between the following values: 0.5, 1, 1.5 or 2, and then randomized uni- formly distributed values around the selected energy level. To each Hamiltonian we added a single ground state with energy O. This type of Hamiltonian is not commonly created by the random QUBO creation process described above, but is more representative of binary optimization problems, and specifically more closely resembles problem Hamiltonians for the Grover problem and the 3SAT problem, which we later use to benchmark our model performance. We note that the Hamiltonian for these specific problems in our test set nevertheless different from randomized problem Hamiltonians, which highlights the generalization capability of our method.
the problem Hamiltonian as input, we used the same prepared QUBO prob-
The training performed using the Adam optimizer (Kingma & Ba 2014), with batches of size 200. Batch normalization (loffe & Szegedy] 2015) was applied during training. A uniform dropout value of 0.1 is employed for all layers during the model training.
4 RESULTS
As baseline to the loss L (Eq. 13 which the model output was compared to the known optimal schedule from the dataset, which was calculated in advance.
we use, we employed the Mean Squared Error (MSE) loss, for
4.1 GROVER SEARCH
The Grover algorithm is a well-known quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just VN evaluations of the function, where N is size of the search space. For an qubit space, the search is over the set {0, 1,.,, 2" - 13. making N = 2". It is possible to reproduce the Grover speedup using an adiabatic formulation, with the following problem Hamiltonian:
Hp I
|m) {ml
(14)
5

---

Published as a conference paper at ICLR 2021
where (m) is the state that represents the value search. Roland & Cerf 2002) this problem, a linear schedule does not produce quantum speedup over a classical algorithm. but for specific initial Hamiltonian H, - |t6) (Nol, for v/ as the maximal superposition state (a sum of the states representing all values from 0 to N - 1), an optimal schedule could be derived analytically achieve quadratic speedup. The optimal path is given by
showed that for
st)
1
2/N tan (2s 1) tan VN
1
(15)
In practice, the proposed Hy is hard physically realize, and a simpler initial Hamiltonian is used:
H₂
oz
(16)
where of is the Pauli matrix ox operating only on qubit
(Liboff 2003).
We test our model's performance by using the Grover problem Hamiltonian Hp as input for sev- eral problem sizes. Different Grover problems are completely symmetrical, and identical after changing variables, so it is sufficient to use a single test case to test our model.
We benchmark our model's performance by simulating AQC for multiple values of t,, and caleu- lating the fidelity by measuring the overlap between the quantum state at the end the adiabatic evolution and the solution state.
We also show the convergence pattern for the fidelity (i.e. the overlap with the solution state, mea- sured during the adiabatic evolution) for single specific 1y. For each problem size, chose different ty. for which a full convergence (p > 0.95) is achieved with the evolution schedule sug- gested by our model. We compare several suggested schedules: the path produced by training our model using our novel loss function, the path produced by training our model using the MSE loss, the linear path, and a numerically calculated optimal path. We also include the results reported by Lin et al. (2020) for the same problem.
The results are reported in Fig. [oor 6, 10, see appendix for 8. It is evident that our model produces paths that are significantly superior to the linear path, and also outperforms Lin al. 2020). The advantage of the new loss function over the MSE loss also clear.
Recall that for Grover search with certain n, Hp is a diagonal matrix of size 2" x 2". To check whether the model trained on = 10 generalizes to larger search problems, we view the diagonal ID signal. This signal is smoothed by a uniform averaging mask of size 62n"
of Hp for n' and subsampled to obtain a diagonal of size 2n.
The results are presented in Fig. 2 Evidently, the network trained for n 10 achieves much better results than the linear baseline for sizes n' = 12, 14, 16. We also trained a network for n = 16. As can be seen in Fig. c). this network does achieve better fidelity than the smaller network. We note that no significant changes were made to the network architecture, and the only difference is in the size of the input layer. Appendix D presents results for the n 16 network on n' 17,.., 20. Our C-trained model achieves much better fidelity than the linear schedule and the MSE baseline.
4.2 3SAT
In the 3-SAT problem, the logical statement consists of m clauses, Ct, such that each clause contain disjunction over three variables out of binary variables. A solution to the 3SAT problem is an assignment for the n variables that satisfies all m clauses. is possible to construct a problem Hamiltonian for each 3SAT problem, by taking sum over all clauses
1 m
H
Σ 1+o 2
(17)
where aff is the Pauli matrix 0₂ operating only on the state that represents the assignment Ja = {0, i1. b {0, 1).1c c= {0, 1}} which produces False value for clause i. This Hamiltonian counts the number of clauses which are not satisfied by each assignment, and its ground state cor- responds to the eigenvalue 0 and represents the solution of the problem, for which all clauses are satisfied.

---

Published as a conference paper at ICLR 2021
Ous
Spinaa Livergath
Probubiityy of succeus
Fidclty
0.6
dkiggnd
0.4-
0.4
Okex
0.2
0.2
Optimal
Jougeed
0.0
0.0
10
150
175
200
(a)
(b)
1.0
1.0
Oup. MBE Lis
0.8
088
Optizal pah
Lintspplh
0.6-
Fidely
0.6
RL designal puth
0.4
Ches
0.2
Oytinal
KL. donggnge
100
200
300
400
(c)
(d)
1.0
Probibiitt of 1000089
0.8
Cues MSE Loss
MSE
Optimal
pats
Optinxl path
KL. deideeed aads
Lavor
0.0
100
200
400
500
0.0
dougned
0
20
40
60
80
100
(e)
(f)
Figure 1: Results for Grover search over (a-c) n=6 or (d-f) n=10 qubits. (a) fidelity for t, 75, and (d) fidelity for t 425. (b,e) fidelity at time ty for multiple Ły values. (c.f) suggested schedules.
Loni
(a)
(b)
(c)
Figure 2:
Fidelity for various y values for Grover search problems of size n' larger than the 10. for which the network was trained. (a) n' 12, (b) n' = 14, (c) n = 16. For n' = 16, we also present the result obtained by network trained for solving n 16.
We test our model's performance, by randomizing 3SAT problems, and converting them to Hamil- tonian form. Following Chen et al. (2020), we focus on 3SAT problems with single solution, and number of clauses adiabatic algorithms (Znidarid 2005)
This type of 3SAT problems considered difficult solve with

---

Published as a conference paper at ICLR 2021
Protubiity of suices
Probubility of suscess
0.6
0.4
0.4
MCTTS
0.2
0.2
Chrss MSC
Lince puth
Lines pata
0.0
0.0
250
(a)
(b)
Fidelity for various ł values, over random 3SAT instances with m=3n clauses. Keep note of the different time scale for each problem size, as larger problems require longer times to converge. (a) n=8 qubits (b) n=1l qubits. For n 11, we employ the test set Chen et al. (2020) and directly compare with their MCTS method.
Figure 3:
We benchmark our model's performance by simulating the adiabatic computation for multiple values of if and calculating the fidelity by measuring the overlap between the quantum state at the end of the adiabatic evolution and the solution state.
In addition to the linear path and the paths obtained by training with either L or MSE, we also include n=11, the results for the schedules designed by MCTS (Chen et 2020). For this purpose, we method outperform all
used the test data obtained by Chen al. As can be seen in Fig. baselines. Note that the MCTS methdod was optimized, for each problem instance and for each t using tens AQC of runs the specific test problem, while method does not
the test data.
As stated in Sec. 3.4 the Hamiltonian model is trained on 10,000 random QUBO problems and 500 random Hamiltonian problems. In Appendix [ study the performance when the 500 random samples are removed from the training set and when employing fewer training samples.
4.3 MAX-CUT
To further demonstrate the generalization capability of the trained model, our Hamiltonian model for size n=10 is tested on random MAX-CUT problems. In graph, maximum cut is partition of graph's 's vertices into two complementary sets, such that the total edges weight between the sets is as large as possible. Finding the maximum cut for general graph is known to be an NP-complete problem (MAX-CUT).
To generate random MAX-CUT problem instances, choose random subset of edges that con- tains at least half of the edges of the fully connected graph. We then sample the weights of each edge uniformly. When converting MAX-CUT problem to the Hamiltonian form, is the number of vertices in the graph (Goto et al. 2019)
Fig. 4 presents the results of The results were averaged over 50 runs and conducted for n = 10. As can be seen, our complete method outperforms the baselines.
method for both with L and MSE, well the linear path.
4.4 QUBO
To test our models with general QUBO problems, sets of random QUBO test problems of varying difficulty are generated Since the final energy gap of the corresponding problem Hamiltonian critical parameter that determines the difficulty of the problem at hand (problems with small energy gap require much longer evolution schedules), we generated two sets of test problems. The first has energy gap of 10 and the second has energy gap of 0.1. Varying the gap was obtained by multiplying the random Q matrix by the required values the gap.
We benchmark the model's performance in previous problems. However, in this case, have two alternatives models: the one the receives the matrix Q as input and the one that receives the Hamiltonian Hp.
8

---

Published as a conference paper at ICLR 2021
1.0
Ours, MSL loss
Ours
Probubility of success
0.8
path
0.6
0.4
0.2
0.0
100
T
Figure 4: Fidelity for various by values, for random n 10 MAX-CUT instances.
Probokiitt of 3uc00s5
QUBO, MSE
Prohakiity sucosss
QUEO,,
0.6
0.6
0.4
044
Joi
0.2
0.2
QUIO, MSE
0.0
0.0
150
175
200
(a)
(b)
Figure 5: Fidelity for various ty values, over random QUBO instances of size n=10. Keep note of the different time scale for each problem, as problems with different energy gaps require different times converge. The energy gaps are (a) g 10, (b) g ~011
We noticed that the process of creating samples of varying spectral gaps creates a mismatch in scale with the training set problems. To compensate, we pre-process the inputs the network models. Specifically, for the model that has as input, that if it is larger than 60, we scale Q to have a norm of 60. Similarly for the model that accepts clip every value that is larger than 90 be 90 (Q with high norms translate to Hamiltonians with specific coeefieicents that are high). To clarify, this preprocessing is only applied the input to the models and does change the problem solve.
normalize the Frobenius norm of cach Q such
Hp as input,
Our Results are presented at Fig. 5 As can be seen, our dedicated QUBO model (Q as input) constructs successful schedules, outperforming all other models. The Hamiltonian model trained with our loss obtains the second highest results. The advantage of the fidelity-based loss term is evident in all cases.
For further comparison between the L loss term and MSE, please refer to Appendix
CONCLUSIONS
Optimal scheduling of AQC tasks the main way reduce the time complexity for an emerging class of quantum computes. While recent work has applied RL for this task, it either provided generic schedule for each class of problems required running the exact computation that needs to be solved multiple times. Our solution employs separate training set, and at test time provides schedule that is tailored to the specific instance, without performing any runs. Remarkably, although our training was performed for one type of problem (QUBO), it generalizes well completely different instances: Grover search, 3-SAT, and MAX-CUT. At the heart of our method lies a new type of loss that maximizes the fidelity based experiments demonstrate the effectiveness of our method, as well as its advantage over the recent contributions.
approximation of the success probability. Our

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant ERC CoG 725974).
REFERENCES
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Review, 50(4):755- 787, 2008. doi: 10. 1. 1377080034479.
Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90(1), jan 2018. doi: 10. 100//evmodphys..000055550
Sergio Boixo, Troels F. Rønnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer. Evidence for quantum annealing with more than one hundred qubits. Nature Physics, 10(3):218-22) 224, feb 2014. doi: 10. 10.1038/mphys2900.
Yu-Qin Chen, Yu Chen, Chee-Kong Lee, Shengyu Zhang, and Chang- Yu Hsieh. Optimizing quantum annealing schedules: From monte carlo tree search to quantumzero. arXiv preprint arXiv:2004.02836, 2020.
William Cruz-Santos, Salvador E. Venegas-Andraca, and Marco Lanzagorta. A QUBO formulation of minimum multicut problem instances trees for d-wave quantum annealers. Scientific Reports, 9(1), nov 2019. doi:
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant muunt-ph00001166 2000.
Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and using qubo models. 2018.
Hayato Goto, Kosuke Tatsumura, and Alexander R. Dixon. Combinatorial optimization by simu- lating adiabatic bifurcations nonlinear hamiltonian systems. Science Advances, 5(4):eaav2372, apr 2019. doi: 20.1166/ciadv..av2377.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167. 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Advances in neural information processing systems, pp. 971 980. 2017.
Richard Liboff. Introductory quantum mechanics. Addison- Aldison-Wesley, San Francisco, 2003. ISBN 0805387145.
Jian Lin, Zhong Yuan Lai, and Xiaopeng Li. Quantum adiabatic algorithm design using reinforce- ment learning. Physical Review A, (5) 2020.
Catherine C. McGeach. Adiabatic quantum computation and quantum annealing: Theory and practice. Synthesis Lectures on Quantum Computing, 5(2):1-93, jul 2014. doi: 10.2200/ v0025ecl1111y20144770m0
A. T. Rezakhani, W.-J. Kuo, A. Hamma, D. A. Lidar, and P. Zanardi. Quantum adiabatic brachis- tochrone. Physical Review Letters, 103(8), aug 2009. doi: 10.1 10.110//yyseee 103.000000.0
Jérémie Roland and Nicolas J. Cerf. Quantum search by local adiabatic evolution. Physical Review A, 65(4), mar 2002. doi: 10. 1110:ppyyrrva.5550422300
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7787):484 489, 2016.
10

---

Published as a conference paper at ICLR 2021
David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419)::140- 1144, 2018.
Yuki Susa, Yu Yamashiro, Masayuki Yamamoto, and Hidetoshi Nishimori. Exponential speedup of quantum annealing by inhomogeneous driving of the transverse field. Journal of the Physical Society of Japan, 87(2):023002, 2018.
Roderich Tumulka. Dirac notation. In Compendium of Quantum Physics, pp. 172-174. Springer, 2009.
Lishan Zeng, Jun Zhang, and Mohan Sarovar. Schedule path optimization for quantum annealing and adiabatic quantum computing. arXiv preprint 1rXiv:1505.00200 2015.
Marko Žnidarič. Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability. Physical Review A, 71(6), jun 2005. doi: 10.110//phytrew.7700020..
A CONVENTIONAL MATRIX NOTATION
For those not familiar with the Dirac notation, we repeat the equations conventional matrix mul- tiplication notation.
(t) (
(L)))
8
(2)
g²(t)
(s(tt)) T ds ((st))))((((( at de
ds
g2(s)
=
(3)
(²(s(t)
dt
Ei
a Eo(ss
(s) H()
t(s) 1
ds
(4)
g²(s)
(s)) d H(s) Eo(s)
de
4= 1(8 = 1)
ds
(5)
(x())
Psuccess
Eo(s 1) 1/(t T)x²(t
ty)
(8)
d (t) = (1)))(((t)
(9)
dt
ds
g2(s)
S 8 (s) de (.((s)
(10)
dt
(2(s)
(5(())
(11)
(1)
d Eo(ss)
de
Hp 1 - mmF mFm
(14)
11

---

Published as a conference paper at ICLR 2021
B PROOF OF THM. 1
Theorem 1. Let 51 (t) and s2(t) be two monotonically increasing fully differentiable bijective func- tions from {0,t, = Ti] to [0, 1.. Let Q be optimization problem, and assume that s1(t) achieves greater fidelity than s2(t) at the end of a quantum adiabatic computation for Q with total evolution time tj -T- Then, for any other choice ty T2. the scaled schedule $1 72 will achieve greater fidelity than s2( (t an adiabatic computation over the same problem with total evolution time ty T2
Proof. The adiabatic condition from Eq. 3 defines a local speed limit over the evolution schedule. We define:
SE (Er()) d g((s)
(18)
de (()) Es()))
Then, for both schedules s; (t) = 1, 2 the local adiabatic speed is
1 ds, (t)
dt et),, 0 sttsi
(19)
9 (st (1))
We now consider new f 72. We use the same suggested schedules with a scaling factor a
-;
72"
st sccaled (t) 8: (at)
(20)
It is clear that staated (t 1t=00 0) 0 and sccated (t = T2) = (2)T2) = 81 (t = TI) = 1, and the
same is true for 22 agcated (l). We calculate the new derivative
dsseated (t) ds; (at)
(21)
dt
dt
By multiplying Eq. 19 by factor we get for the new time axis 0 5 T2
ds; (at)
ei(()
(22)
LE (st (at)) di
2
then, we can switch to the scaled schedules and finally
1 dspeated (t) (1) c graated
(23)
LE (spoaled (t)) dt
We now consider the fidelity for each evolution schedule. According the adiabatic theorem, the fidelity achieved at the end of the adiabatic evolution for each schedule is dependent solely on the local adiabatic speeds e, (t). The resulting fidelity for the full path is then bounded by some functional F L + R which transforms all of the local adiabatic speeds to single number.
ps 2 F (c)(t)
(24)
Following Roland & Cerl (002). we assume a global maximum value
Flf (t)) maz (f (t))
(25)
P: 2 max (e)(t)
(26)
it is clear that for this choice of F,
F laf (t)) aF If (t)
(27)
For any positive scalar a. It follows that the new values for fidelity for the scaled schedules are bounded by
pt new > 1 - 1-1 ()) = 1- a2-
(28)
We assumed pl > P2. so F (e)(1) < F (+)(1)). and for any a it remains true that
a²F (e](1) aF ())())
(29)
and therefore
p plaw 2 p2 new
(30)
We note that this holds true for many choices for [f (t)), as long as
F F (1) = 9 (a) [
(31)
for some monotonically increasing function g.
n
12

---

Published as a conference paper at ICLR 2021
C SOLVING THE SCHRÓDINGER EQUATION FOR THE ADIABATIC EVOLUTION
It is possibly numerically integrate and solve differential equation in Eq. 9 using the explicit evolu- tion Hamiltonian (s) for every 0 < < 1, and the boundary condition (t = 0)) = (E = 0)), where [E 0)) is the known ground state of the initial Hamiltonian Ha, This first order differ-
ential equation, could be solved numerically to obtain |v5(1 = (y)) in the following fashion:
1. Divide the time axis to slices 1..M
2. For every time slice, find Hi. H(s(t= 1/4 -m))
3. Calculate the eigenvalue decomposition Hm: eigenvectors V; and eigenvalues E;
4. Find the projection of the last quantum state (4/m1) onto the eigenvectors space
N
1/m 1) = Σ a;V;
(32)
1=1
a: (Vi vi-1)
(33)
5. Evolve the quantum state according to
N
Σ
e ei 4f
az VV
(34)
6. Repeat steps 2-5 until reaching Ly
D ADDITIONAL GROVER SEARCH RESULTS
The results of Grover search for 8 qubits, for our model, well as the method of Lin et al. 2020) and other baselines are presented Fig.
D.1 n' > n EXPERIMENTS FOR THE 16 MODEL
To demonstrate approach's 's ability to employ model of certain size for larger problems, present result for sizes n = 17, 18, 19, 20 using the model trained for n 16.
The results shown in Fig. Our predicted schedule greatly outperforms the baseline linear schedule, with even greater ad advantage for larger problem sizes. We also compare to the same Hamil- tonian model, trained with the MSE loss, As can be seen, this model outperforms the linear model, but is less effective than the model trained with L.
E ALTERNATIVE TRAINING SETS
The training set of the Hamiltonian model contains 10,000 random QUBO problems and 500 random Hamiltonian problems, see Sec. 3.4 Fig. g depicts the effect of training on the first group only, i.e., on the Hamiltonian forms for the QUBO problems. This is shown for both the 3SAT problem and the Grover problem. As can be seen, there relatively small drop in performance for the 3SAT problems and signifcant one for the Grover problem. Note that in both cases, we cannot compare the QUBO model. For the 3SAT problem, there is polynomial overhead in size, when using the QUBO form Glooerr et al. 2018 For the Grover problem, the QUBO problem is undefined.
In another set of experiments, we varied the size the training dataset. In addition to the 10000+500 samples (of the two types mentioned above), we employed sets of size 1000+62, 2500+125, and 5000+250. Fig. 9 presents the results for 3SAT problems. Evidently, adding more training samples helps. However, there is, expected, diminishing returns effect. Note that the 3SAT problem is not captured by neither the random Hamiltonians nor by the random QUBO problems. Therefore, the success these instances indicates generalization capability.
13

---

Published as a conference paper at ICLR 2021
Ours, MSE Loss
Ours
0.8
Optimal path
Linear
Fidelty
0.6
designed path
0.4
0.2
0.0
0
20
60
80
100
120
140
(a)
Probability of success
0.8
0.4
Ours,
Optimal path
Lincar polh
RL designed pulh
0.0
25
50
75
100
125
150
175
200
T
(b)
1.0
0.8
0.6
0.4
Ours, MSE Loss
Ours
0.2
Optimal path
0.0
RL designed
0
20
40
60
80
100
(c)
Figure 6: Model Results for Grover search n=8 qubits. (a) fidelity for ty 150. (b) fidelity for multiple ly. (c) suggested schedules for one specific instance.
F COMPARING THE ALTERNATIVE LOSS TERMS
In this work, novel loss function was presented, that allowed training neural networks with better performance than standard losses. The suggested loss function is justified by derivation in Sec. (.3] further supported by all experiments conducted and for both the Hamiltonian and the QUBO networks.
14

---

Published as a conference paper at ICLR 2021
38
0.8
Probabitty of success
Probabiiy of Nnce
Ours Ours, MSE
Our
Ours, NSE
Optimal path
Opt mal path
Lincir pats
Linoor soth
5-2
10000
20000
30000
40000
50000
60000
20000
40000
60000
85000
100000
120000
(a)
(b)
1.0
1.0
3.0
Fribbal 1 CITTIA
Probub Ry of success
Ours
Ours
Dum, MSE
Ours, MSE
Optimal path
Opt.mal path
0.44
Lnnzr
Lincor soth
50000
100003
150000
200000
252000
100000
200030
300030
4000000
500009
(d)
Figure 7: Fidelity for various ly values for Grover search problems of size n' larger than the 16 for which the network was trained. (a) n' different time scale for each problem size.
17, (b) n'' 18, (c) n' = 19, (d) n' 20. Note the
1.0
1.0
Robbablity of scsccoss
0.8
Probubilryy of snocDs
0.8
0.6
0.6
Fall
Only QUBO
0.4
0.4
Linsse zth
Pall Treniing Onls QUBO probicus
0.2
Linor
30
100
150
200
250
300
350
190
200
500
400
500
(a)
(b)
Figure 8: Success probability when training with and without the random Hamiltonians. (a) 3SAT problems of size 10. (b) The Grover problem of size 10.
To visually demonstrate the advantage of our loss function, we present specific example. We consider for a single 3SAT problem the optimal path and three variants of it. In the first, we add random noise to s(t). in the second, shift the optimal path constant. The third variant adds a linear function to it. We also consider the path that was obtained by employing L or MSE, see Fig. 10 a).
As can be seen in Fig. b)),), the best path is the optimal one, followed by the path of our full method, method with MSE and the optimal path with the added linear factor. As can be seen in Tab. T
15

---

Published as a conference paper at ICLR 2021
1.0
Probability of success
0.8
0.6
0.4
train set 10500
train set size 5250
train set size 2625
0.2
train set size 1062
Linear path
0.0
25
50
75
100 T
125
150
175
200
Figure 9: The effect of changing the size of the training set for 3SAT problems of size n 10.
1.
1.0
0.8
Probability of succ000
0.8
0.6
0.6
Surgented achodade
Seggenad
0.4
schodale
Sugganal ochobdic jormanz addiive faster)
Supaested achedule
Suggental schoddle Cinor adtiow facre)
0.2
Oer, MXL loa
MSE
Ouz
supgosed
Oytinal
Optinal
0
10
40
50
60
(b)
Figure 10: (a) Six different paths that were compared for single 3SAT problem. (b) The obtained success probabilities.
our loss is predictive of the success probability, while the MSE is less so. Specifically, the MSE loss assigns relatively low loss to the optimal path with the added Gaussian noise, while our method predicts that it would result in low success probability.
To generalize this sample, we compare the ability of the two loss terms identify the path that would obtain fidelity of 0.8 faster. This discrimination ability is visualized via receiver operating characteristic (ROC) curve.
A set of 250 test problems, randomized in similar fashion to the training dataser of QUBO problems with n = 8, was generated and its optimal path s* was computed. For each problem, two possible schedules, 81 and 52, were randomized. Following Lin al. (2020). who showed that the Fourier spectrum an effective representation for paths, we sample the coefficients of the paths in the Fourier domain.
For each loss, we compute the score of the two paths with respect to the optimal path, and compute the ratio of the score associated with s and the associated with 82 For our loss, this is given as C(dl.s") = where d,, d2 are the difference vectors obtained form the paths 81, 82, respectively. We simulate both paths, and assign a label of 1 leads to the probability threshold on 0.8 faster than 82, O otherwise.
16

---

Published as a conference paper at ICLR 2021
Table I: The probability of success at certain time point for each path presented in Fig. Tota) and the loss obtained by both MSE and & in comparison to the optimal path. The high value of 1.2353 a typo. It is result of loss penalizing jittery paths.
Path
Probability of success at = 45
MSE loss
Our loss
Optimal with Gaussian noise
0.63
0,0029
1.2353
Optimal with constant shift Optimal with linear shift Our with the MSE loss Our with C Optimal
0.77
0.0070
0,0119
0,82
0,0043
0.0099
0.89
0.0014
0.0061
0.91
0.0043
0.0010
0.97
1.0-
MSE
Our loss
0.8
True positive rate
0.6
0.4
0.2-
0.0-
0.0
0.2
0.4
0.6
0.8
1.0
False positive rate
Figure 11: ROC curves for identifying the better path out of two options, see text for details. The red curve is for the loss term and the blue for the MSE loss.
We compare the resulting ROC curve for L and for the MSE loss in Fig. 11 It is evident that the suggested loss function more discriminative of better paths than the the MSE loss.
G TRAINING DYNAMICS
In Fig. 12 we present the evolution of the training and validation losses during model training. This shown both for L and for the MSE loss for the Hamiltonian model of size 10.
17

---

Published as a conference paper at ICLR 2021
0.8
Training loss
Validation loss
0.6
Loss
0.4
0.2
0.0
100
200
300
400
500
600
Number of Batch
0.14
Training
Validation loss
0.12
0.10
0.08
0.06
100
200
300
400
500
600
Number Batch
(b)
Figure 12: The loss of the training and validation sets during the training process of the n 10 Hamiltonian model. (a) Training optimize the loss term C. (b) Optimizing the MSE loss.
18


Reviews:
[{"review_id": "u2V0SgCXFZ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**summary** \nthe paper proposes to learn parametric form of optimal quantum annealing schedule. Authors construct 2 versions of neural network parameterizations mapping problem data onto an optimal schedule. They train these networks on artifically generated sets of problem of different size and test final models on the Grover search problem as well as 3SAT. Experiments demonstrate improved performance in comparison to existing approaches.\n\n**pros**\n* the approach is straightforward to implement \n* experiments show the ability to do zero-shot generalization to different problem classes\n* empirically proposed models perform better then baselines\n\n\n**cons**\n* the mechanism of observed generalization to unseen problem instances is unclear. Training dataset size is chosen to be fixed 10000, it is unclear whether the learned model isn't just memorizing the inputs but rather providing useful generalization. Experiments with varying the dataset size say as 2^m could help clarify this. In addition to that providing training curves with train and validation errors as function of step would be also very useful.\n* The authors don't provide any intuition for why MSE objective performs worse then  success probability objective. Is it the case that training the latter is easier for some reason?\n\n\n**questions**\n* it is not clear how the architecture is varied for different model sizes. Since the input size changes with problem size, neural networks must vary at least in the input layer. Do they share the rest of the layers between different problem sizes?\n\n**comments**\n* it would be useful to add comparison b/w QUBO model and Hamiltonain model for the set of QUBO problems. Is it true that QUBO models performs better in this case?", "extra_scores": {}, "extra_text": {}}, {"review_id": "XRx1SM3pN9X", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I would like to thank the authors for the rebuttal. The added experiments have made this work better.\n\nWhile the collection of training data still seems hard (require exponential computation), I like the idea and the new experiments on generalizing from small training size to large ones. I still think the application domain of the proposed work is limited. The application to quantum computing is definitely interesting, but adiabatic scheduling is a more restricted domain and the contribution in this work is not applicable to gate-based quantum computers explored by Google, IBM, Rigetti, etc.\n\nBecause the revised manuscript is stronger now, I have modified my rating accordingly.\n\n##########################################################################\n\nSummary:\n\nThis paper concerns a specific application of machine learning in quantum computing: training classical machine learning models to predict the optimal schedule in adiabatic quantum computation. Adiabatic quantum computation depends greatly on the schedule to achieve good quantum speed-up. While in various cases, the optimal schedule is known. There will be instances where the optimal schedule is unknown, and the work proposes predicting those optimal schedules using neural networks. The main contribution comes from designing a new loss function for training such a model.\n\n##########################################################################\n\nReasons for score: \n\nI think the application is relatively narrow, even within the field of machine learning/quantum physics. The proposed neural architectures are very standard. The novelty comes from how to define a good loss function. The loss function is well-motivated and the empirical performances are convincing. However, the contribution may be too specific to be used in other machine learning/quantum physics applications, so I think most audiences attending ICLR may not be very interested in this result.\n \n##########################################################################Pros: \n\nPros:\n \n1. The proposed loss function is well-motivated.\n\n2. The proposed method works well on a wide range of tasks (QUBO, Grover search, 3-SAT).\n \n \n##########################################################################\n\nCons: \n\n 1. The application of the contribution of this work is relatively narrow (producing schedules for adiabatic quantum computation).\n\n\n2. The problem size tested by this work is small (6, 8, and 10). The QUBO problems that can be solved by current quantum devices (such as D-Wave machines) seems to be much larger (bigger than 1000).\n\n\n3. The proposed machine learning approach can not be used for larger n (e.g., n > 100) because the input to the classical neural network is a 2^n vector. If this scalability issue can not be addressed, then the proposed method would not be useful in practice (any form of quantum advantage would become vacuous if we need an exponential preprocessing time to find the schedule).\n\n \n##########################################################################\n\nQuestions during the rebuttal period: \n\n\n1. I have some concerns about the scalability of the proposed technique as discussed in the Cons section. The input to the neural network is a 2^n dimension vector. Do the authors have ideas and supporting evidence for how one could scale to a large system when n is like 50~100?\n\n2. Are there other non-ML alternatives to the linear schedule that people employ in practice? If the importance of scheduling is as claimed, I believe there should be extensive literature studying heuristics scheduling for QUBO and 3SAT. How does the proposed ML method compare to these existing heuristics?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "I5kKdjX0zb_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider the problem of providing optimal scheduling schemes for adiabatic quantum computing (AQC), i.e. with a way of interpolating / evolving a Hamiltonian from its initial form to its final form such that it is nwither too slow nor too rapid and thus can harness the speedup that AQC offers for solving combinatorial optimization problems (or, to be specific: QUBOs).\nIndeed, optimal scheduling of is a problem of theoretical as well of practtical concern as it makes or breaks the success of AQC but general, closed form solutions are hard to come by (or simply unknown at this point in time). \nAddressing drawback of previouslt proposed reinforcement learning approaches to this problem, the authors propose to train deep neural networks. To this end, they introduce a novel loss function loss that maximizes the fidelity based on an approximation of the success probability. In practical experiments, they find that schedules learned this way outperform those from previous approaches and, in addition, generalize from one type of problem to different instances of problems. Their experiments also reveal the approach to outperform previous.\n\nThis paper presents, original, convincing, and interesting work on a problem of considerable practical importance in adiabatic quantum computing. The idea of using neural networks in order to learn good (optimal) schedules for AQC is elegant and apparanetly leads to very good results. Moreover, to those with a background in AQC and deep learning, the paper is easy to read and clearly describes basic ideas and required technical details. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "2h1leo4wvrL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nDeep neural networks are used for supervised learning of optimal optimization schedule for various problems in adiabatic quantum computing (AQC). The usefulness of the method is assessed on three families of optimization problems.\n\nStrengths:\nThe supervised learning method is straightforward and general, yet is the first such method to be employed for adiabatic scheduling.\n\nThe method show impressive performance on all of the problem instances, outperforming both simple baselines and recently proposed methods using reinforcement learning.\n\nIn contrast to previous ML methods, the proposed method doesn't require simulations of the adiabatic evolution during training, with all such work being done upfront, in preparation of the training set.\n\nCritiques:\nIn order to apply the proposed supervised learning method, the ability to compute the optimal adiabatic schedule with reasonable accuracy is already required. To ensure this method has relevance for nontrivial problems in AQC, I would request that the authors give more evidence for the generalization capabilities of their method, for example by assessing the performance of the model in one of the following settings: (1) With different training set sizes, or (2) Using only QUBO instances or only randomized Hamiltonians (as described in Section 3.4) for the training data, rather than the mixture of both which is currently employed. I understand that the performance on Grover search and 3-SAT gives some evidence for this generalization ability, but some more clear-cut evidence would be desirable here.\n\nUsing the literal Hamiltonian as an input to the supervised problem scales quite poorly with increasing problem sizes. Could the authors comment on how to deal with this scaling issue? In particular, do the authors see any means of giving an efficient parameterization for the Grover search and 3-SAT problems in lieu of the Hamiltonian diagonal elements, along the same lines as how QUBO problems can be specified via the instance matrix Q.\n\nCan the authors comment on why the \"optimal\" path in Figure 1 sometime gives a worse final probability of success than the supervised learning method proposed?\n\nRecommendation:\nWhile the paper leaves open some questions about the generality and scalability of the proposed method, the novelty and performance of the method is promising. I would recommend acceptance.\n\n### UPDATE AFTER THE REBUTTAL\n\nMany thanks to the authors for revising the paper, the new material is comprehensive and does a lot to address my questions about the feasibility of scaling up the model. I would know the authors are short on space, but I would request that the current Figure 2 be tweaked in some manner to makes the legend in Figure 2c bigger. The current legend is nearly illegible, and the difference between the model trained on size 10 vs 16 is important. Independently of this, I have raised my score in light of these new additions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are for accepting the paper: in particular, R1 and R3 found the rebuttal sufficiently convincing to increase their scores from their initial assessment leaning towards rejection. 

Strengths:
+ Clarity 
+ Simplicity of the proposed approach 
+ Convincing experiments outperforming reasonable baselines across all problem instances

Weaknesses:
+ Scale (as noted by R2 and R3) to larger problem sizes, beyond the setting of less than a dozen.

I agree with some hesitation that the paper is narrow in scope (both in interest from the community and scale---and ultimately whether it would interest the overall quantum computing audience). However, I think the paper makes significant advances toward the area of adiabatic quantum computation.
Decision: Accept (Spotlight)