Quantum Adiabatic Algorithm Design using Reinforcement Learning
Jian Lin Zhong Yuan Lai Xiaopeng Li






























 














apsrev













    ↑↓#1 5pt #1
        
        
        
        
        
        
        
        
        
        State Key Laboratory of Surface Physics, and Department of Physics, Fudan University, Shanghai 200433, ChinaInstitute of Nanoelectronics and Quantum Computing,  Fudan University, Shanghai 200433, China
        
        
        
        State Key Laboratory of Surface Physics, and Department of Physics, Fudan University, Shanghai 200433, ChinaInstitute of Nanoelectronics and Quantum Computing,  Fudan University, Shanghai 200433, China
        
        
        xiaopeng_li@fudan.edu.cn
        State Key Laboratory of Surface Physics, and Department of Physics, Fudan University, Shanghai 200433, ChinaInstitute of Nanoelectronics and Quantum Computing,  Fudan University, Shanghai 200433, China
        Collaborative Innovation Center of Advanced Microstructures, Nanjing 210093, ChinaShanghai Research Center for Quantum Sciences, Shanghai 201315, China
        Quantum algorithm design plays a crucial role in exploiting the computational advantage of quantum devices. 
         Here we develop a deep-reinforcement-learning based approach for quantum adiabatic algorithm design. Our approach is generically applicable to a class of problems with solution hard-to-find but easy-to-verify, e.g., searching and NP-complete problems. We benchmark this approach in Grover-search and 3-SAT problems, and find that the adiabatic-algorithm obtained by our RL approach leads to significant improvement in the resultant success probability.  In application to Grover search, our RL-design automatically produces an adiabatic quantum algorithm that has the quadratic speedup. 
         We find for all our studied cases that quantitatively the RL-designed algorithm has a better performance
         compared to the analytically constructed non-linear Hamiltonian path when the encoding Hamiltonian is solvable, and that this RL-design approach remains applicable even when the non-linear Hamiltonian path  is not analytically available. In 3-SAT, we find RL-design has fascinating transferability—the adiabatic algorithm obtained by training on a specific choice of clause number leads to better  performance consistently over the linear algorithm on different clause numbers. 
         These findings suggest the applicability of reinforcement learning for automated quantum adiabatic algorithm design. 
         Further considering the established complexity-equivalence of circuit and adiabatic quantum algorithms, we expect the RL-designed adiabatic algorithm to inspire novel circuit algorithms as well. Our approach is potentially applicable to different quantum hardwares from trapped-ions and optical-lattices to superconducting-qubit devices.
        Quantum Adiabatic Algorithm Design using Reinforcement Learning
            Xiaopeng Li
            December 30, 2023
        ===============================================================
        
        
        
        § INTRODUCTION
        
        Quantum simulation and quantum computing have received enormous efforts in the last two decades owing to their  advantageous computational power over classical machines <cit.>.  In the development of quantum computing, quantum algorithms with exponential speedups have long been providing driving forces for the field to advance, with the best known example from factorizing a large composite integer <cit.>.  In applications of quantum advantage to generic computational problems, quantum algorithm design plays a central role.  In recent years, both threads of gate-based <cit.> and adiabatic annealing models <cit.> of quantum computing have witnessed rapid progress in hardware developments such as superconducting <cit.>, photonic <cit.>
        and atomic <cit.> quantum devices. Computational complexity equivalence between the two approaches have been established in theory <cit.>.  
        
        
        
        
        In adiabatic quantum computing, the Hamiltonian can be written as a time-dependent combination of initial and final Hamiltonians, H_B and H_P <cit.>, as 
         H = (1-s(t/T))H_B + s(t/T)H_P , 
         
        with the computational problem encoded in the ground state of H_P. In this framework, the quantum algorithm design corresponds to the optimization of the Hamiltonian path or more explicitly the time sequence of s(t). Different choices for the path could lead to algorithms having dramatically different performance and even  in the complexity scaling. For example in Grover search, a linear function of s(t/T) leads to an algorithm with a linear complexity scaling to the search space dimension (N), whereas a nonlinear choice could reduce the complexity to √(N) <cit.>. This   implies an approach of automated quantum adiabatic algorithm design through searching for an optimal Hamiltonian path, which may lead to a generic approach of automated algorithm design given the established complexity equivalence between gate-based and adiabatic models <cit.>. The automated quantum algorithm design that is adaptable to moderate-qubit-numbers is particularly in current-demand considering near term applications of  noisy intermediate size quantum devices <cit.>. 
        
        
        
        
        
        
        
        
        
        Here, we propose a deep reinforcement learning (RL) architecture for automated design of quantum adiabatic algorithm. By encoding the computation problem in a Hamiltonian ground state problem, we find that the automated design of quantum algorithm can be reached by RL of the optimal Hamiltonian path. 
        Our RL architecture is most efficient to a class of problems with solutions easy-to-verify, e.g., searching, factorization, and NP-complete problems. 
        In application to the Grover search and 3-SAT problems, we find that the adiabatic algorithm designed by the machine has a better performance than linear algorithms in terms of computing efficiency or the success probability.
        
        For the Grover search, the RL-design automatically produces an adiabatic algorithm that takes as much time as the nonlinear path <cit.> when the Grover search Hamiltonian is solvable and the solution of nonlinear path is analytically available. And quantitatively, with the same amount of time the RL-designed algorithm reaches a higher success probability than the analytically constructed non-linear path. 
        When the analytical nonlinear path is unavailable in using a non-solvable Grover search Hamiltonian encoding, we still find  that RL-design 
         produces an adiabatic algorithm whose time resources scale as √(N).
         
         For the 3-SAT problem,   the RL-designed quantum algorithm is found to have  emergent transferability—the algorithm obtained by  training on a subset of problem instances is applicable to other very different ones while maintaining the  high computational performance. 
        This transferability is not only conceptually novel but also practically crucial in saving computation resources for training. 
        
        
        
        
        
        § REINFORCEMENT LEARNING ARCHITECTURE FOR QUANTUM ADIABATIC ALGORITHM DESIGN
        
        
         §.§ Adiabatic algorithm design as an optimization problem
        
        Given a computational problem, e.g., Grover search or 3-SAT, the form of the  Hamiltonian H_P encoding the problem is fixed.  For different problem instances, for example in targeting different states in Grover search or finding solutions for different choices of clauses in 3-SAT, the encoding Hamiltonian is different. We label different  problem instances by PI, and the encoding Hamiltonian is correspondingly labeled as H_PI. The designed Hamiltonian path in general would depend on the computational  problem, for example  whether it is Grover search or 3-SAT, but it should be required that the Hamiltonian path should be independent of the problem instance PI, in order for this Hamiltonian path design to make a   quantum adiabatic algorithm generically applicable. This makes it distinct from path optimization aiming for preparation of specific quantum states <cit.> or for  achieving robust or fast gate operations <cit.>.   
        
        We propose an approach for automated algorithm design based on reinforcement learning (see Fig. <ref> for an illustration). In the framework of quantum  adiabatic algorithm, the task of algorithm design reduces to the  exploration of the optimal path s(t/T), which we parameterize  as 
         s(t/T) = t/T + ∑_ m=1 ^C b _m  sin(mπ t/T). 
           
        Here C is a cutoff for high frequency components, and the parameters b_m form a vector b. This parametrization is asymptotically complete as the cutoff C approaches infinity. 
        
        To build an artificial intelligent agent that explores the path-space  of b, we introduce a set of action,  a, which are defined to update b as 
        a^(0) ( b) =  b and  [a^ (2m-1) ( b)] _n  = b_n  - Δ_0 δ_mn, [a ^(2m) ( b)] _n = b_n + Δ_0 δ_mn for m≥ 1, with Δ_0 to be referred to as maximal update per step and the Kronecker delta δ_mn.
        
        
        
        
        
        
        A unit reward, r, is collected by the agent if the solution out of  the adiabatic quantum computer is correct. 
        This approach then directly applies to adiabatic quantum hardwares such as D-wave machines <cit.> for the class of problems with solutions hard-to-solve but easy-to-verify. 
        
        To target an optimal adiabatic algorithm with robust performance to all problem instances, we sample PI and average over a certain number  of instances (MI)  in calculating the reward for an action a on b. 
        In the reinforcement learning approach, during an intermediate j-th step, the agent evaluates the action a on b  according to a Q-table 
         Q^⋆ ( b, a)=max_ P𝔼[ ∑_ i=0 ^∞γ^i r (  b (j+i) ) | P], 
        where γ∈ (0,1) is a discount factor that allows to account for future rewards of b (j+i), and P represents an action-selecting policy describing the probability of performing the action a on a path-state b. 
        
        
        Following the action selection,  we use a protocol analogous to simulated annealing and update the path state stochastically according to 
        a probability determined by the the corresponding action Q-value. The path state is updated in this way because our Hamiltonian path space is continuous, distinct from the Go-game where the reinforcement learning has already found a great success <cit.>. 
        Details of the state-update policy are described in Sec. <ref>. 
        
        
        
        The Q-table  can be solved by iteration according to the Bellman equation <cit.>. 
        
        
        
        
        
        
        
        Our method uses a deep neural network to approximate the Q-table, as Q^⋆ ( b,  a) ≈ Q( b,  a; θ), with θ  the network parameters determined in an iterative learning process.  To stabilize the  nonlinear iteration in learning, 
         we adopt an experience-replay approach <cit.> where the agent's experiences ( b, a,  r) are stored in a memory M with a capacity CAP.  
        We have a network Q( b, a; θ) trained  on-the-fly during  the agent exploring the path-state space. As for the training, the inputs and outputs are  
        b and  
        
        r + γ  max_a' Q(a(  b), a'; θ_-)
        respectively, 
        with b, r, and a drawn randomly from the memory M, 
        
        and the network parameter θ_-  updated to θ  every W steps.
        
        Given the limitations of quantum computing hardwares presently accessible, we simulate quantum computing on a classical computer and generate reward to train the RL network. In applications to a quantum computer,  our RL architecture for automated algorithm design is directly adaptable by collecting reward generated by a quantum adiabatic computer. 
        
        
        
         §.§  Neural network architecture 
        
        In Fig. <ref> we show the explicit learning protocol. The left-hand panel of Fig. <ref> shows a schematic of our RL framework. We use a two-network setup which is similar to that used in Ref. mnih2015humanlevel. These two networks are labeled `target_net' and `predict_net' in the schematic. 
        
        The `target_net' uses a previously-learned set of parameters and updates the parameters every W steps; the values of these parameters are directly copied from `predict_net'. This will reduce problems such as divergences and oscillations thus making the learning process more stable.
        The loss function calculates the expectation value of the difference between `target Q value' and `predict Q value' over different batches. 
        The right-hand panel shows the multi-layer fully-connected neural network used to represent the Q-table. The input to this network is the path state obtained at some learning step, while the output are the Q-values corresponding to the actions.
        
        
        
         §.§  Details of the state-update policy in the reinforcement learning 
         
        
        For the state-update policy, we used the ϵ greedy strategy, where the agent selects a random action with total probability 1-ϵ, and the action having the maximal Q-value with an additional probability ϵ.   We set the ϵ=0 initially and let  the agent explore the state space with no preference. The value of ϵ is increased gradually until a maximum value 90%  in the learning process. In this way, we try to maintain a balance between the agent's current knowledge to maximize reward and possibilities in exploring among other options, which in turn leads to a learning process with better performance. 
        
        
        
        
        In order to deal with the continuous state-space, we develop a continuous state-update protocol and combine with the ϵ-greedy method in the following way. 
        
        In our procedure, we use the ϵ-greedy strategy 
        to choose an action. After choosing the action, the agent sets a probability to accept the action which 
         we calculate from an acceptance probability functionP(e, Tem) = exp(e/Tem), where
        
        e = Q(a(𝐛),a;θ) - Q(𝐛,a;θ)/Δ_0 * Δ,      Δ∈ [0, Δ_0],
        Tem is a modifiable parameter commonly identified as the “temperature” of the system in the context of simulated annealing methods, 
        
        The “temperature" is annealed down every agent-exploration step (labeled by j), following Tem_j=Tem_j-1×10^-C_R, withe C_R the cooling rate. 
        
          We run cycles of this ϵ-greedy learning process to ensure convergence of the Q-table. 
        
        At each step of RL exploration, the neural network is trained by varying the  θ parameters to solve an iteration problem, 
         
        Q( b, a; θ) = r(a( b)) + γ  max_a'[ Q(a( b), a'; θ_-) ]. 
         
        The training data is generated from the memory M that stores the path-states b, actions a, and the corresponding rewards r(a ( b)) that the RL agent has explored. 
        The parameters θ_- are only updated to θ every W steps (W is set to be 50 here), to  deliberately slow down the iteration process for stabilization purpose. 
        This approach has been used in Ref. mnih2015humanlevel, and follows  a standard approach to stabilize nonlinear iteration problems.   When the iteration converges, Q( b, a; θ) satisfies the Bellman equation <cit.>.  
        
        
        
        The effect of P(e,Tem) can be better understood in context of the annealing procedure, which we outline below.
        At intermediate step j the agent evaluates the action a_j on the path state 𝐛_j, which then defines the path state 𝐛_j+1 and reward at step j+1. At this point we perform the following steps, 
        
          *  Fix Δ_0 to some constant; 
            
          *  Calculate (<ref>) with values of the parameters as obtained at step j;
            
          *  Generate a random number μ∈[0.0, 1.0]
            
          *  If μ≤exp(e/Tem)
          *  Accept corresponding action and accept the current value of Δ.
                 
          *  else choose action = 0 (corresponding to taking no action).
            
        
        In the learning process, we store the current path, action taken, reward resulting from action on path state and the corresponding next path state. 
        
        
        When the reward reaches a threshold of 99.9%—a maximal reward is 1 in our notation, as it resembles the success probability of the RL-designed adiabatic algorithm, 
        the value of ε_max  is set to 1, and the agent then uses the network to choose action.  
        In exploring the Hamiltonian path-state space, as the iteration step increases, it gets more frequent for the agent to 
        find a path that gives a higher success probability.
        
        
        After the Q-table converges, we let the agent update the path-state b until it stabilizes, according to the ϵ-greedy policy with ϵ increased from 90% to 100 % slowly with fixed annealing temperature and neural network parameters  
        
        
        
        
        
        
        § PERFORMANCE ON GROVER SEARCH
        
        
        
         §.§  Learning of easy Grover search
        
        
        
        In application of our RL approach to automated adiabatic algorithm design, we first show its performance on Grover search compared to known quantum algorithms. This search problem is to find an element in an array of length N as an input to a black-box function that produces a particular output value. This classical problem can be encoded as searching in the Hilbert space of n=log_2 N qubits for a target quantum state. These qubits are labeled by q in the following. A circuit-based quantum algorithm was firstly designed by Grover, which shows a quadratic quantum speedup over classical computing <cit.>. In adiabatic quantum  computing, the Hamiltonians in Eq. (<ref>) for Grover search are 
        H_B =1-|ψ_0⟩⟨ψ_0|, and H_P = 1-|m⟩⟨ m|, where  |m⟩ is a product state in Pauli-Z basis that encodes the search target, and |ψ_0⟩ is a product state in the Pauli-X basis with  all n eigenvalues equal to 1. The symbols X, Y, and Z refer to Pauli matrices in this work. A linear choice of s(t/T) (b = 0 in our notation), does not exhibit the quadratic  speedup. It was later pointed out in Ref. roland_quantum_2002  that the quantum speedup  is restored with a tailored nonlinear path choice of s(t/T). 
        
        
        
        
        In the Grover search problem, different problem instances correspond to different choices for the |m⟩ states, which are all connected to each other by a unitary transformation 
        
        which keeps H_B invariant. The reward RL-agent collects in the training process is thus exactly equivalent for different problem instances, which means averaging over PI is unnecessary for the Grover search. 
        Fig. <ref>  shows results of the RL-designed adiabatic Grover search algorithm. 
        In our RL design for adiabatic quantum algorithm, we scale up the adiabatic time T as T∝√(N) to benchmark against the best-known Grover search algorithm. 
        Then as expected, the linear adiabatic algorithm leads to a success probability completely unsatisfactory at large N. 
        We find that both the nonlinear <cit.> and the RL-designed adiabatic algorithms produce success probabilities very close to 1 (larger than 99.9%).  At large N≥ 2^4, the RL-designed algorithm outperforms the nonlinear one. 
        
        
        
        
        In Fig. <ref>, a quantitative comparison shows that the required adiabatic time T to  reach a  fixed  success probability is shorter from the RL-designed algorithm than the analytically constructed non-linear algorithm. 
        We want to emphasize here that in Fig. <ref> we scale up the total adiabatic time according to the √(N) = √(2^n) scaling. Having an eventual success probability close to 1 implies the the computational complexity of the RL-designed adiabatic algorithm follows the √(N) scaling, because otherwise the success probability would significantly decrease as we increase the qubit number from 1 to 10. 
        
        The √(N) scaling is already known to be optimal for Grover search <cit.>. 
        
        
        
        
        
        
        It is worth remarking that  the choice of H_B is made here for comparison purposes, as the nonlinear path to achieve the quadratic speedup is only analytically available with that specific Hamiltonian choice <cit.>. For physical realization of H_B, which can be rewritten as  H_B = 1-⊗_q [ 1+X_q]/2, it is experimentally challenging to construct this Hamiltonian with quantum annealing devices. A more suitable choice for H_B in that regard  is ∑_q [1-X_q]/2, for which  the analytically obtained nonlinear path <cit.> is then no longer applicable, but our RL design still produces high-performance adiabatic algorithms. 
        A common feature of the RL-learned path for s(t/T) is that there is a relatively flat region around s = 0.5 where the energy gap is minimal. This flat region has a tendency to grow as  we increase N (Fig. <ref>(a)). 
        
        
        
        
         §.§ Instantaneous energy spectrum for the easy Grover search
         
        
        In this section, we show the resultant instantaneous energy spectrum corresponding to the RL-designed algorithm for the easy-way Grover search.
        
        The instantaneous energy following the RL-designed algorithm lies on   the time-dependent ground state for both small and large number of qubits (Fig. <ref>(b,c)). The energy deviation is much smaller than the linear algorithm, and is very close to the tailored nonlinear algorithm. Therefore the RL-design approach  indeed automatically reveals a  quantum adiabatic algorithm as efficient as the improved nonlinear algorithm for Grover search <cit.>. 
        
        
        
        
        
         §.§ Hard Grover search
        
        
        In learning the adiabatic algorithm of the Grover search, we choose the analytical-solvable Hamiltonian as in Ref. roland_quantum_2002 for comparison purpose, where the quantum dynamics during the adiabatic procedure corresponds to an effective two-level system. 
        
        
        
        
        
        
        We  thus denote this as the “easy” Grover problem. Considering  physical realization,  a suitable choice for the encoding Hamiltonian H_B is 
        
        H_B = ∑_q[1-X_q]/2
        
        We denote this the “hard” Grover problem, for which the analytically obtained nonlinear path <cit.> does not carry over <cit.>. 
        We stress here that  our RL approach still produces an adiabatic algorithm with high success probability. 
        In this regard, our RL approach is more generic, and is particularly useful considering the present limitations of quantum hardwares. 
        
        
        In Fig. <ref>, we compare results obtained from the linear protocol with those obtained from the RL-learned protocol for the hard Grover problem. We show the success probabilities as obtained from the linear and RL designed path for different numbers of qubits. Similarly to our results in Fig. <ref>, the success probability is calculated by taking the square of wave function overlap between the dynamical and targeted ground state. Again, at large N the linear search algorithm fails to find the targeted state (the evolution time follows the  scaling of T∝√(N)), while the RL-designed algorithm  still produces an adiabatic algorithm with high performance. The comparison to the nonlinear path is not shown here simply because for the hard Grover search Hamiltonian used here, the nonlinear path is not analytically available. 
        
        In Fig. <ref> we plot the energy spectrum of the instantaneous Hamiltonian of the hard Grover problem for different numbers of qubits. The behavior of the ground and first excited states of the hard Grover problem is markedly different from those of the easy Grover case (Fig. <ref>). 
        As can be seen from the plots, the linear protocol apparently starts to fail for n= 6. 
        
        
        
        
        
        
        
        
        
        
        
        §  PERFORMANCE ON 3-SAT
        
        We  then apply the RL approach to the more complicated 3-SAT problem. Given a total number of N_b boolean bits (labeled by q), the problem is to find a boolean sequence z_q to satisfy 
        C = C_1  C_2  C_3  C_4 …
        with each C_i a clause containing three boolean bits, say q_i, k=1,2,3.  
        The total clause number will be denoted as N_C. The satisfiability condition of each clause C_i can be written into a truth table 
        z_iα ={ z^(1) , z ^(2) , z ^(3)}
         such that the binary sequence { z^(1) , z ^(2) , z ^(3)} belongs to this table if and only if C_i is satisfied. We use α to label all possibilities to satisfy the clause C_i.  To solve this problem with quantum adiabatic algorithm, we need to introduce N_b qubits, which are then also labeled by q. The corresponding qubit states are | z_1⟩⊗ |z_2⟩⊗…⊗ |z_N_b⟩. Introducing a compact notation | q_i;  z_iα⟩ for the qubits, q_i, 1, q_i, 2, and q_i, 3, in the quantum state |z^(1)⟩⊗| z^(2)⟩⊗ |  z^(3)⟩, the classical 3-SAT problem is formally encoded into a quantum ground state problem with a Hamiltonian 
         H_P ^ SAT = -∑_i=1^N_C∑_α   |  q_i ;  z _iα⟩⟨ q_i ;   z _iα  | . 
         
        A solution to the 3-SAT problem corresponds to a ground state of H_p^ SAT with energy -N_C. Different 3-SAT problem instances correspond to different choices of clause q_i and truth table z_iα. 
        The initial quantum state and Hamiltonian H_B are set to be |ψ_0⟩ and H_B = ∑_q [1-X_q]/2, respectively, where |ψ_0⟩ is the same initial state as in the Grover search problem.
        In our RL approach to design 3-SAT quantum algorithm, the reward  RL-agent collects is generated by randomly sampling q_i and z_iα (see Appendix <ref>), to make the learned algorithm generically applicable. 
         
        
        
        
        
        
        In Fig. <ref>, we show the performance of the RL-designed algorithm and compare with the linear algorithm. We put the RL-agent to work on a 10-bit 3-SAT problem. The RL-designed algorithm is obtained by training with clause number N_C = 3 only, where the stepwise reward is obtained by averaging over 100 random problem instances. We then test the RL algorithm on random 3-SAT problem instances that contain one-to-six clauses. The tested success probability in Fig. <ref>( a) is obtained by averaging over 10^5 random problem instances. It is evident that the RL-designed algorithm outperforms the linear algorithm with higher success probability.  Its advantage  becomes more significant in a systematic fashion as the clause number is increased, although the RL algorithm is trained on 3-SAT problems with clause number N_C = 3 only. This implies the emergent transferability of the RL-designed algorithm. 
        
        The success  over different clause numbers implies that this RL-learning approach has seized the intrinsic ingredients  to optimize the adiabatic quantum  algorithm because otherwise the RL-designed algorithm would not be transferable. 
        
        
        
        
        
        Besides the quantitative improvement in the RL-designed over the linear algorithm, we also emphasize that the outcome of the RL algorithm is qualitatively distinct in the resultant fidelity. In Fig. <ref>( b,   c), we show the distribution of the infidelity obtained from 10^5 random 3-SAT problem instances. The statistics is taken for different clause number separately. The infidelity is rescaled by taking its average as a unit. The distributions of this rescaled infidelity for different clause numbers are found to collapse onto a universal function, for both the RL (Fig. <ref>( b)) and linear (Fig. <ref>( c)) algorithms. It appears that infidelity distribution from the linear algorithm is close to a Wigner-Dyson (WD) distribution—the numerically obtained statistical second moment of the infidelity agrees with the  WD prediction within 10% difference.  
        To the contrast, the second moment of the infidelity from the RL algorithm deviates from the WD prediction, meaning the infidelity distribution for the RL algorithm is qualitatively distinctive from the linear case. 
         The physical implication of such qualitative difference in the infidelity distribution is left for future study. 
        
        
        
        
        
        
        § SCALABILITY OF THE REINFORCEMENT LEARNING IN QUANTUM ADIABATIC ALGORITHM DESIGN ON GROVER SEARCH
        
        In Fig. <ref> we show the results of applying a schedule learned on a 10-qubit easy Grover search problem to n-qubit problems with n>10. For the linear algorithm, the schedule is s(t/T) = t/T, and T scales according to √(2^n) as we increase the qubit number in Fig. <ref>. For the RL-designed algorithm, the schedule s(t/T) is obtained by a training process on a problem with qubit number n=10, and then the schedule is applied to problems having larger number of qubits (n = 11,…, 16), following the same rescaling T∝√(2^n) as the linear case. While the fidelity decreases as we increase the qubit number, it is evident that the RL-designed algorithm systematically out-performs the linear algorithm despite the simple rescaling applied. The comparison in the infidelity is explicitly given in Fig. <ref>. 
        
        To further demonstrate the scalability of the RL-learning, we provide the infidelity of the RL-designed algorithm trained on Grover search with qubit number n, and then applied successively on a problem with n +1 (see Fig. <ref>). 
        We use the number of training steps to quantify the resources spent on the RL-learning.  
        Assuming access to an actual quantum computer, the number of training steps multiplied by the parameter MI (see Section <ref> and Table <ref>) would be equal to the number of running times of the quantum computer.  
         
        We emphasize here that the number of  training steps for different qubit number n is fixed (see parameters of annealing protocol iteration L_SA and path state iteration L_PS in Table <ref>).
         The resultant infidelity in this iterative procedure remains close to 1%.  This further implies the schedule trained on relatively smaller-size problems has a rather large degree of transferability. 
        
        In order to explicitly show that the reinforcement learning is helpful in obtaining a new schedule from a prior guess as we alter the problem, we provide the infidelity during the training process in Fig. <ref>. We take the qubit number n = 11, and  compare two cases with and without pre-knowledge of the schedule. In Fig. <ref> (a), the training process starts from a trivial linear schedule s(t/T) = t/T, i.e., no pre-knowledge given, whereas in Fig. <ref> (b), the iteration starts from a Q-table already obtained through training on the problem with  n=10, i.e., with pre-knowledge.  It is evident that the reinforcement learning is indeed substantially helpful in quickly finding a new schedule from a prior guess even when the problem is altered—here the qubit number is changed from n=10 to 11. With pre-knowledge, our reinforcement learning is able to find a proper schedule with three times smaller of iteration steps. 
        
        
        
        
        
        § CONCLUSION
        
        In this work we report a reinforcement-learning-based approach for automated quantum adiabatic algorithm design. 
        Our devised approach is directly applicable to problems with solutions easy-to-verify such as searching, factorization, and NP-complete problems. 
        
        Through numerical simulations, we show that the RL approach automatically finds an adiabatic algorithm for Grover search with quadratic speedup. 
        
        In the application to the 3-SAT problems, we find  surprising transferability of the RL-designed algorithm which suggests the algorithm trained on  relatively-smaller size problems is applicable to larger sizes, which is both practically useful and theoretically inspiring in considering the complexity scaling. 
        
        
        The performance of our approach can be further improved by introducing additional Hamiltonian terms, which would easily fit into the framework proposed here. 
        
        
        
        
        § ACKNOWLEDGEMENT
        
        J.L. acknowledges helpful discussion with  Xiuzhe Luo. 
        This work is supported by National Program on Key Basic Research Project of China under Grant No. 2017YFA0304204, National Natural Science Foundation of China under Grants No. 11774067, 11934002,  and Natural Science Foundation of Shanghai City (Grant No. 19ZR1471500), Shanghai Municipal Science and Technology Major Project (Grant No.2019SHZDZX04). 
        XL would like to thank Department of Physics at Harvard University for hospitality during the completion of this work. 
        The first two authors J.L. and Z.Y.L. contribute equally to this work. 
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
         Appendix
        
        
        
        
        
        
        § PSEUDO CODE AND PARAMETERS OF REINFORCEMENT LEARNING 
        
        
        For completeness, the pseudo code and the parameters used in our RL architecture for Grover search and 3-SAT problems are shown in algorithm <ref> and Table <ref>.
        
        
        
        
        
        § SAMPLING OF 3-SAT PROBLEM INSTANCES 
        
        Given a total number N_b of boolean bits z_q, different 3-SAT problem instances correspond to different choices of three-bit combinations q_i in each clause C_i, and different choices of the truth table  of each clause defined to be z_iα = (z^(1) , z^(2), z^(3)) in the main text. Since we aim at a quantum adiabatic algorithm generically applicable, we randomly sample the problem instances { q_i,  z_i } according to the definition of 3-SAT problem. 
        
        It is worth noting here that the choice for the truth table is not completely random, and that for one clause in the 3-SAT problem, there are eight possibilities of choosing the truth table corresponding to the eight possibilities of constructing the clause. The size of the sampling space grows polynomially with N_b and exponentially with N_C. 
        
        
        
        
        
        
        
        
         Supplementary Information
        
        
        § NEURAL NETWORK ARCHITECTURE
        
        
        In Fig. <ref> we show the explicit learning protocol. The left-hand panel of Fig. <ref> shows a schematic of our RL framework. We use a two-network setup which is similar to that used in Ref. mnih2015humanlevel. These two networks are labeled `target_net' and `predict_net' in the schematic. 
        
        The `target_net' uses a previously-learned set of parameters and updates the parameters every W steps; the values of these parameters are directly copied from `predict_net'. This will reduce problems such as divergencies and oscillations thus making the learning process more stable.
        The loss function calculates the expectation value of the difference between outputs from `q_target' and `predict_net' over different batches. 
        The right-hand panel shows the multi-layer fully-connected neural network used to represent the Q-table. The input to this network is the path state obtained at some learning step, while the output are the Q-values corresponding to the actions.
        
        
        
        
        § DETAILS OF THE STATE-UPDATE POLICY IN THE REINFORCEMENT LEARNING
        
        For the state-update policy, we used the ϵ greedy strategy, where the agent selects a random action with total probability 1-ϵ, and the action having the maximal Q-value with an additional probability ϵ.   We set the ϵ=0 initially and let  the agent explore the state space with no preference. The value of ϵ is increased gradually until a maximum value 90%  in the learning process. In this way, we try to maintain a balance between the agent's current knowledge to maximize reward and possibilities in exploring among other options, which in turn leads to a learning process with better performance. 
        
        
        
        
        In order to deal with the continuous state-space, we develop a continuous state-update protocol and combine with the ϵ-greedy method in the following way. 
        
        In our procedure, we use the ϵ-greedy strategy 
        to choose an action. After choosing the action, the agent sets a probability to accept the action which 
         we calculate from an acceptance probability functionP(e, T) = exp(e/T), where
        
        e = Q(a(𝐛),a;θ) - Q(𝐛,a;θ)/Δ_0 * Δ,      Δ∈ [0, Δ_0],
        T is a modifiable parameter commonly identified as the “temperature” of the system in the context of simulated annealing methods, 
        
        The “temperature" is annealed down every agent-exploration step (labeled by j), following T_j=T_j-1×10^-C_R, withe C_R the cooling rate. 
        
          We run cycles of this ϵ-greedy learning process to ensure convergence of the Q-table. 
        
        At each step of RL exploration, the neural network is trained by varying the  θ parameters to solve an iteration problem, 
         
        Q( b, a; θ) = r(a( b)) + γ  max_a'[ Q(a( b), a'; θ_-) ]. 
         
        The training data is generated from the memory M that stores the path-states b, actions a, and the corresponding rewards r(a ( b)) that the RL agent has explored. 
        The parameters θ_- are only updated to θ every W steps (W is set to be 50 here), to  deliberately slow down the iteration process for stabilization purpose. 
        This approach has been used in Ref. mnih2015humanlevel, and follows  a standard approach to stabilize nonlinear iteration problems.   When the iteration converges, Q( b, a; θ) satisfies the Bellman equation <cit.>.  
        
        
        
        The effect of P(e,T) can be better understood in context of the annealing procedure, which we outline below.
        At intermediate step j the agent evaluates the action a_j on the path state 𝐛_j, which then defines the path state 𝐛_j+1 and reward at step j+1. At this point we perform the following steps, 
        
          *  Fix Δ_0 to some constant; 
            
          *  Calculate (<ref>) with values of the parameters as obtained at step j;
            
          *  Generate a random number μ∈[0.0, 1.0]
            
          *  If μ≤exp(e/T)
          *  Accept corresponding action and accept the current value of Δ.
                 
          *  else choose action = 0 (corresponding to taking no action).
            
        
        In the learning process, we store the current path, action taken, reward resulting from action on path state and the corresponding next path state. 
        When the reward reaches a threshold of 99.9%,  the value of ε_max  is set to 1, and the agent then uses the network to choose action. The convergence of the training process is confirmed in our calculation. 
        After the Q-table converges, we let the agent update the path-state b until it stabilizes, according to the ϵ-greedy policy with ϵ increased from 90% to 100 % slowly with fixed annealing temperature and neural network parameters. 
        
        
        § INSTANTANEOUS ENERGY SPECTRUM FOR THE EASY-WAY GROVER SEARCH
         
        In this section, we show the resultant instantaneous energy spectrum corresponding to the RL-designed algorithm for the easy-way Grover search (Fig. <ref>). A common feature of the RL-learned path for s(t/T) is that there is a relatively flat region around s = 0.5 where the energy gap is minimal (Fig. <ref>(a)). This flat region has a tendency to grow as  we increase N. 
        
        The instantaneous energy following the RL-designed algorithm lies on   the time-dependent ground state for both small and large number of qubits (Fig. <ref>(b,c)). The energy deviation is much smaller than the linear algorithm, and is very close to the tailored nonlinear algorithm. Therefore the RL-design approach  indeed automatically reveals a  quantum adiabatic algorithm as efficient as the improved nonlinear algorithm for Grover search <cit.>. 
        
        
        
        
        
        § THE HARD-WAY OF LEARNING GROVER SEARCH ALGORITHM
        
        
        In learning the adiabatic algorithm of the Grover search, we choose the analytical-solvable Hamiltonian as in Ref. roland_quantum_2002 for comparison purpose, where the quantum dynamics during the adiabatic procedure corresponds to an effective two-level system. 
        
        
        
        
        
        We  thus denote this as the “easy” Grover problem. Considering  physical realization,  a suitable choice for the encoding Hamiltonian H_B is 
        
        H_B = ∑_q[1-X_q]/2
        
        We denote this the “hard” Grover problem, for which the analytically obtained nonlinear path <cit.> does not carry over. 
        We stress here that  our RL approach still produces an adiabatic algorithm with high success probability. 
        In this regard, our RL approach is more generic, and is particularly useful considering the present limitations of quantum hardwares. 
        
        
        
        In  <ref>, we compare results obtained from the linear protocol with those obtained from the RL-learned protocol for the hard Grover problem. We show the success probabilities as obtained from the linear and RL designed path for different numbers of qubits. Similarly to our results in Fig. <ref> in the main text, the success probability is calculated by taking the wave function between the dynamical and targeted ground state. Again, at large N the linear search algorithm fails to find the targeted state (as in the main text,  the evolution time follows the  scaling of T∝√(N)), while the RL-designed algorithm  still produces an adiabatic algorithm with high performance. The comparison to the nonlinear path is not shown here simply because for the nonsolvable Hamiltonian used here, the nonlinear path is not analytically available. 
        
        In <ref> we plot the energy spectrum of the instantaneous Hamiltonian of the hard Grover problem for different numbers of qubits. The behavior of the ground and first excited states of the hard Grover problem is markedly different from those of the easy Grover case (Fig. <ref>). 
        As can be seen from the plots, the linear protocol apparently starts to fail for n= 6. 
        
        
        
        
        
        
        
        
        
        
        
        
        
        § SAMPLING 3-SAT PROBLEM INSTANCES
         
        Given a total number N_b of boolean bits z_q, different 3-SAT problem instances correspond to different choices of three-bit combinations q_i in each clause C_i, and different choices of the truth table  of each clause defined to be z_iα = (z^(1) , z^(2), z^(3)) in the main text. Since we aim at a quantum adiabatic algorithm generically applicable, we randomly sample the problem instances { q_i,  z_i } according to the definition of 3-SAT problem. 
        
        It is worth noting here that the choice for the truth table is not completely random, and that for one clause in the 3-SAT problem, there are eight possibilities of choosing the truth table corresponding to the eight possibilities of constructing the clause. The size of the sampling space grows polynomially with N_b and exponentially with N_C. 
        
        
        
        
        
        § PARAMETERS OF REINFORCEMENT LEARNING
        
        
        For completeness, the parameters used in our RL architecture for Grover search and 3-SAT problems are listed in Table <ref>.
