Electronic Structure Calculations and the Ising Hamiltonian

Electronic Structure Calculations and the Ising Hamiltonian ABSTRACT: Obtaining exact solutions to the Schrödinger equation for atoms, molecules, and extended systems continues to be a “Holy Grail” problem which the fields of theoretical chemistry and physics have been striving to solve since inception. Recent breakthroughs have been made in the development of hardware-efficient quantum optimizers and coherent Ising machines capable of simulating hundreds of interacting spins with an Ising-type Hamiltonian. One of the most vital questions pertaining to these new devices is, “Can these machines be used to perform electronic structure calculations?” Within this work, we review the general procedure used by these devices and prove that there is an exact mapping between the electronic structure Hamiltonian and the Ising Hamiltonian. Additionally, we provide simulation results of the transformed Ising Hamiltonian for H2 , He2 , HeH+, and LiH molecules, which match the exact numerical calculations. This demonstrates that one can map the molecular Hamiltonian to an Ising-type Hamiltonian which could easily be implemented on currently available quantum hardware. This is an early step in developing generalized methods on such devices for chemical physics. H(s) = (1 − s)HB + sHP (where s is a time evolution parameter, s ∈ [0, 1]). Adiabatic evolution is governed by the Schrödinger equation for the time-dependent Hamiltonian H(s(t)). Thus, permitting the system to evolve from HB to HP is a slow and smooth manner, such that the system remains in its ground eigenstate during the perturbative evolution. Hitherto, the largest scale implementation of AQC is by DWave Systems.16,17 In the case of the D-Wave device, the physical process acting as adiabatic evolution is more broadly called quantum annealing (QA). The quantum processors manufactured by D-Wave are essentially a transverse Ising model with tunable local fields and coupling coefficients: H = ∑i Δiσix + ∑i hiσiz + ∑i,j Jijσizσjz , where the parameters Δi , hi , and Jij are physically tunable. The qubits (quantum bits) are connected in a specified graph geometry; this design permits the embedding of arbitrary graphs. Zoller and co-workers presented a scalable architecture with full connectivity, yet it can only be implemented with local interactions.18 The adiabatic evolution is initialized at HB = −h∑i σix and evolves into the problem Hamiltonian: HP = ∑i hiσiz + ∑i,j Jijσizσjz. This equation describes a classical Ising model whose ground state isin the worst case NP-complete. Therefore, any combinatorial optimization NPhard problem may be encoded into the parameter assignments ({hi, Jij}) of HP and may exploit adiabatic evolution as a method D etermining solutions to the Schrödinger equation is a fundamentally challenging problem due to the exponential increase in the dimensionality of the corresponding Hilbert space with the number of particles in the system; this increase in computation system size requires a commensurate increase in computational resources. Modern quantum chemistryhampered by the difficulty associated with solving the Schrödinger equation to chemical accuracy (∼1 kcal/mol)has largely become an endeavor to find approximate methods and corrections. A few products of this effort include ab initio, density functional, density matrix, algebraic, quantum Monte Carlo, and dimensional scaling methods.1−8 All methods devised to date, however, face the insurmountable challenge of computational resource requirements as the calculation is extended either to higher accuracy or to larger systems. Computational complexity in electronic structure calculations suggests that these restrictions are a result of an inherent difficulty associated with simulating quantum systems.9−11 Electronic structure algorithms developed for quantum computers provide a promising new route to advance electronic structure calculations for large systems.12−14 Recently, there has been an attempt at using an adiabatic quantum computing modelas implemented on the D-Wave machineto perform electronic structure calculations.15 Fundamentally, the approach behind the adiabatic quantum computing (AQC) method begins by defining a problem Hamiltonian, HP, engineered to have its ground state encode the solution of a corresponding computational problem. The system is initialized in the ground state of a “beginning” Hamiltonian, HB , which is easily solved by classical methods. The system is then allowed to evolve adiabatically as A for reaching the ground state of HP. More recently, an optically based coherent Ising machine was developed and is capable of finding the ground state of an Ising Hamiltonian describing a set of several hundred coupled spin 1/2 particles.19−21 These challenging NP-hard problems are characterized by difficulty in devising a polynomial-time algorithm; therefore, solutions cannot be easily found using classical numerical algorithms in a reasonable time for large system sizes (N).19−21 Such special purpose machines may help in finding the solutions to some of the most difficult computational problems faced today. commonly used subdivisions, three- to two-body and k-body gadgets.28 Here we present a universal method of mapping an n-qubit Hamiltonian, H, which depends on σx, σy, σz to an rn-qubit Hamiltonian, H′, consisting of only products of σz. In this process, we increase the number of qubits from n to rn, where the integer r plays the role of a “variational parameter” to achieve the desired accuracy in the final step of energy calculations. With increasing r, which means the use of more qubits to calculate, we can achieve more accurate results; please see the Appendix for more details. We use two steps to complete this mapping. The first step is to generate a mapping between the eigenstates. In an original nqubit Hilbert, H, space, a general eigenstate is given by ψ = ∑i aiϕi; we can map this to the space of the rn-qubit Hamiltonian, H′, which increases the space from n qubits to rn qubits. The mapping method is to repeat the basis (ϕi) bi times, where bi is determined by ai defined through the relationship ■ RESULTS AND DISCUSSION The technical scheme for performing electronic structure calculations on such an Ising-type machine can be summarized in the following four steps: First, write down the electronic structure Hamiltonian in terms of creation and annihilation Fermionic operators, delivering the second quantization form. Second, use either the Jordan−Wigner or the Bravyi−Kitaev transformation to move from Fermionic operators to spin operators.13,22 Third, reduce the spin Hamiltonian (which is generally a k-local Hamiltonian) to a 2-local Hamiltonian.23 Finally, map this 2-local Hamiltonian to an Ising-type Hamiltonian. This general procedure begins with a second quantization description of a Fermionic system in which N single-particle states can be either empty or occupied by a spineless Fermionic particle.4,24 One may then use the tensor product of each individual spin orbital, written as |f 0, ..., f n⟩ to represent states in Fermionic systems where f j ∈ {0, 1} is the occupation number of orbital j. Any interaction within the Fermionic system can be expressed in terms of products of the creation and annihilation operators a†j and aj, for j ∈ {0, ..., N}. Thus, the molecular electronic Hamiltonian can be written as 1 Ĥ = ∑ hijai†aj + ∑ hijklai†aj†akal 2 i,j i ,j ,k ,l (1) ai ≈ ∑ hαi σαi + ∑ hαβij σαi σβj + ∑ i,α ijαβ ijkαβγ ∑m bm 2 , where ∑i bi = r. S(bi) is a sign function associated with bi, as ai can be positive and negative and repeat time can only be positive. If ai is positive, we have S(bi) = 1, and if ai is negative, we have S(bi) = −1. After this procedure, we get a new eigenstate i |Φ⟩ ⊗i ⊗bj=1 |ϕi⟩. This procedure is represented in Figure 1. Figure 1. Example of mapping σx2 between different bases from a state 1 1 |Φ⟩ = 2 |000⟩ + 2 |010⟩ to state |000010⟩, where 0 represents spin up and 1 represents spin down. The spin operators act on the second qubit in the original Hamiltonian basis and on the second and fifth qubits in the mapped Hamiltonian basis. The above coefficients hij and hijkl are the one- and two-electron integrals which can be precomputed in a classical way used as inputs to the quantum simulation. The next step is to develop and employ a Pauli matrix representation of the creation and annihilation operators. This can be done by employing the Bravyi−Kitaev transformationor the Jordan−Wigner transformationto map between the second quantization operators and the Pauli matrices {σx, σy, σz}.22,25 The molecular Hamiltonian now takes the general form13 H= biS(bi) The second step is the mapping between the Hamiltonians, H → H′. By mapping the eigenstate, we have a corresponding way to map the spin operator (Ii , σix , σiy , σiz) on the ith qubit in nqubit space to rn-qubit space by ijk i j k hαβγ σασβσγ + ... (2) where the index α = x, y, z notes the Pauli matrix and the index i designates the spin orbital. Now, after having developed a k-local spin Hamiltonian (many-body interactions), one should use a general procedure to reduce the Hamiltonian to a 2-local (twobody interactions) spin Hamiltonian form;26,27 this is a requirement, since the proposed computational devices are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating a quantum many-body Hamiltonian up to an arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, for example, offer a systematic procedure to address this requirement. Recently, we have employed analytical techniques resulting in a reduction of the resource scaling as a function of spectral error for the most σxi → 1 − σzijσzik σ ik − σzij S′(j)S′(k) σyi → i z S′(j)S′(k) 2 2 σzi → σzij + σzik S′(j)S′(k) 2 Ii → 1 + σzijσzik S′(j)S′(k) 2 (3) σ means acting on the ith qubit in jth n qubits in |Ψ⟩ (or the spin operator σ acting on the [(j − 1)n + i] qubit). In addition, S′(j), S′(k) represents the sign of the jth, kth of the n qubits in the new state of the rn-qubit space. The introduction of S′(j) is the same as the introduction of S(bi). Now, the newly transformed Hamiltonian, H′, includes only products of σz and I, and is therefore diagonal (details of the transformation are presented with examples in the Appendix). So far, we are able to transform our Hamiltonian to a k-local Hamiltonian including only products of σz terms. It is then ij B Figure 2. Comparing the numerical results of ground state energy of the Ising Hamiltonian with the exact STO-6G calculations of the ground state of H2, He2, HeH+, and LiH molecules as one varies the internuclear distance R. straightforward to transform the Hamiltonian to 2-local by using ancilla qubits, as the following example illustrating the transformation from 3-local to 2-local Ising Hamiltonian. H′ = ∑ hi′σzi + ∑ Jij′σziσzj i ij (5) To estimate the efficiency of this proposed method, we here derive the number of qubits required by constructing the final 2local Hamiltonian in eq 5. Suppose we start with an original Hamiltonian in the second quantization representation containing n orbitals. The first step of the transformation into the Pauli operator representation requires O(n) qubits and O(n4) terms. The second step of mapping the form containing all of the Pauli operators to the form containing only σz requires O(rn) qubits and O(2nr2n4) terms. The final step of reduction to 2-local requires O(2nr2n7) qubits. Due to the computational costs of the current method, it is feasibly useful for small and medium size molecular systems. To push this method to a large size molecular system, we propose to combine our method with a recent approach by Chan and co-workers.32 Instead of encoding the wave function using n Gaussian orbitals, leading to Hamiltonians with O(n4) second-quantized terms, Chan et al. utilize a dual form of the plane wave basis which diagonalizes the potential operator, leading to a Hamiltonian representation with O(n2) second-quantized terms. Moreover, one can repeat our initial calculations using the new procedure with O(n2) secondquantized terms. This will clearly save computational resources. There is of course much space for improvement, and one should continue to explore new ideas to further optimize the proposed method. min(± x1x 2x3) = min(± x4x3 + x1x 2 − 2x1x4 − 2x 2x4 + 3x4) x1, x 2 , x3 , x4 ∈ {0, 1} (4) Here, we see how, by including x4, one can show that minimizing 3-local is equivalent to minimizing the sum of 2-local terms. We can apply this technique in our reduction from k-local to 2-local terms, as shown in the Appendix.29 Finally, we succeed in transforming our initial complex electronic structure Hamiltonian from the second-quantization form to an Ising-type Hamiltonian which can be solved using existing quantum computing hardware.14,19,30,31 To illustrate the proposed method (details are in the Appendix), we present in Figure 2 the calculations for the hydrogen molecule (H2), the helium dimer (He2), the hydrogen−helium molecular cation (HeH+), and lithium hydride (LiH). First, we used the Bravyi−Kitaev transformation and the Jordan−Wigner transformation to convert the diatomic molecular Hamiltonian in the minimal basis set (STO-6G) to the spin Hamiltonian of (σx, σy, σz). We then used our transformed Hamiltonian in rn-qubit space to obtain a diagonal k-local Hamiltonian constructed of σz terms. Finally, we reduced the locality to obtain a 2-local Ising Hamiltonian of the general form C Figure 3. Left: If the 2-qubit state is |ψ ⟩ = 1 2 |00⟩ + S(b2) = 1. Middle: If the 2-qubit state is |ψ ⟩ = 1 2 1 2 |11⟩, then the 4-qubit state is |Ψ⟩ = |0011⟩ with S′(1) = S′(2) = 1, r = 2, b1 = b2 = 1, and S(b1) = |00⟩ − 1 2 1 2 |11⟩, then the 4-qubit state is |Ψ⟩ = |0011⟩ with S′(1) = −S′(2) = 1, r = 2, b1 = b2 = 1, and 1 |00⟩ − 2 |11⟩, then the 8-qubit state is |Ψ⟩ = |00111111⟩ with S′(1) = S′(2) = S′(3) = −S′(4) S(b1) = −S(b2) = 1. Right: If the 2-qubit state is |ψ ⟩ = = 1, r = 4, b1 = b2 = 1, and S(b1) = S(b2) = 1. (S′(3) and S′(4) cancel out, and thus, S(b2) = 1). ■ CONCLUSION We have developed a general procedure of mapping the original complex electronic structure Hamiltonian to a diagonal Hamiltonian in terms of a σz basis, which is experimentally implementable via today’s Ising-type machines. Presently, implementation of σz, σx, and σy is not possible on current Ising machines nor while using quantum annealing as on the DWave machine. Our generalized procedure provides an opportunity to begin to utilize the current generation of quantum computing devicesof about 2000 connected spinsfor important computational tasks in chemical physics. Incidentally, recent experimental results presented by the IBM group on few-electron diatomic molecules have shown that a hardware-efficient optimizer implemented on a 6-qubit superconducting quantum processor is capable of reproducing the potential energy surface for such systems.30 The development of efficient quantum hardware and the possibility of mapping the electronic structure problem into an Ising-type Hamiltonian may grant efficient ways to obtain exact solutions to the Schrödinger equation, thus providing a solution path to one of the most daunting computational problems in both chemistry and physics. Moreover, this study might open the possibility to connect with the rich field of statistical mechanics of he Ising model describing phase transitions.33−37 Notation 1: We designate the ith qubit within the kth n-qubit subspace of the rn state space of |Ψ⟩ as ik. Notation 2: We use b(j) to represent the jth n-qubit in the space of |Ψ⟩, which is in the basis |ϕb(j)⟩. bi may only be non-negative, yet ai may be positive or negative. For a negative ai, we will introduce a function S(bi) containing the sign information to account for bi being non-negative. The mapping is described by the following rules: • S(bi) is the sign associated with the bi coefficient which is negative if ai is negative and is positive if ai is positive. • For the rn-qubit state |Ψ⟩, we can use a function S′(i) to record the sign associated with each n qubits in the rnqubit space. S′(i) represents the sign of the ith n qubits in the rn-qubit space. Thus, bi = |∑|ϕb(j)⟩=|ϕi⟩ S′(j)| and S(bi) is the sign of ∑|ϕb(j)⟩=|ϕi⟩ S′(j). • As before, bi is the integer which approximates ai by biS(bi) ∑m bm ■ bi ∑m bm 2 biS(bi) . If r is large enough, we can just view ai ≈ ∑m bm 2 . i |ϕi⟩ and r = ∑ri=1 |S′(i)|. • |Ψ⟩ can be written as |Ψ⟩ = ⊗i ⊗bj=1 Figure 3 shows the details about the mapping. Theorem 1: With the mapping between |ψ⟩ and |Ψ⟩ as described above, we can find a mapping between the Hamiltonian in the space of |ψ⟩ to the space of |Ψ⟩. i 1 + σzjσzik |Ψ⟩, 2 i 1 + σzjσzik which means Ii in the space of |ψ⟩ can be mapped to in the 2 Theorem 2: ⟨ϕb(j)| ⊗i Ii|ϕb(k)⟩ is equal to ⟨Ψ| ∏i APPENDIX Here, we present a procedure to construct a diagonal Hamiltonian with a minimum eigenvalue corresponding to the ground state of a given initial Hermitian Hamiltonian. For a given initial Hermitian Hamiltonian, an eigenstate |ψ⟩ can be expanded in a basis set |ϕi⟩ as |ψ⟩ = ∑i ai|ϕi⟩. This basis set consists of different combinations of spin-up and -down qubits. First, we will assume that all expansion coefficients, ai, are nonnegative and will map the state to a new state |Ψ⟩ according to the following rules: i • |Ψ⟩ can be written as |Ψ⟩ = ⊗i ⊗bj=1 |ϕi⟩ and r = ∑i bi. • If the original state |ψ⟩ exists within an n-qubit subspace, the new state |Ψ⟩ should be in an rn-qubit space, where r is the number of times we must replicate the n qubits to achieve an arbitrary designated accuracy. • The number of times, bi, we repeat the basis |ψ⟩ in an rnqubit state, |Ψ⟩, approximates ai by 2 space of |Ψ⟩. Proof: Clearly, Ii in the space of |ψ⟩ is to observe if ith digits of | ϕb(j)⟩ and |ϕb(k)⟩ are the same or not. If they are the same, it yields ij i k 1; otherwise, 0. On the other hand, 1 + σz σz in the space of |Ψ⟩ is 2 to check if the ith digits of the jth n-qubit subspace (|ϕb(j)⟩) and the kth n-qubit subspace (|ϕb(k)⟩) are the same or not. If they are ij i k the same, it yields 1; otherwise, 0. (For 1 − σz σz , we omit the 2 operators for other digits which are the identity I.) Thus, we get ⟨ϕb(j)| ⊗ Ii|ϕb(k)⟩ = ⟨Ψ| ∏ i 1 + σzijσzik |Ψ⟩ 2 (6) If and only if all digits of |ϕb(j)⟩ and |ϕb(k)⟩ are the same, the left and right results are equal to 1; otherwise, they are equal to 0. Theorem 3: ⟨ϕb(j)| ⊗im Ii|ϕb(k)⟩ is equal to . If r is large enough, bi is proportional to ai or we can just view i ⟨Ψ| ∏i < m b i ai ≈ , where ∑m bm 2 is the normalization factor. ∑m bm 2 Here we introduce notation to be used throughout the remaining text: 1 + σzjσzik 2 m × 1 + σz jσzmk 2 i means σix in the space of |ψ⟩ can be space of |Ψ⟩. D 1 − σzjσzik |Ψ⟩, w h i 2 ij i k mapped as 1 − σz σz in 2 × ∏i > m ch the Chart 1 Proof: Clearly, σix in the space of |ψ⟩ is to check if the ith digits of |ϕb(j)⟩ and |ϕb(k)⟩ are the same or not. If they are the same, it j≠k ,j,k≤r ∑ ⟨Ψ| i σzjσzik in the space |Ψ⟩ is to yields 0; otherwise, 1. Similarly, 1 − 2 verify if the ith digits of the jth n-qubit subspace (|ϕb(j)⟩) and the kth n-qubit subspace (|ϕb(k)⟩) are identical. If they are the same, it j≠k ,j,k≤r = ⟨Ψ| ∏ 1+ 2 im 1− σix j ≠ k , j , k ≤ 2n × 1+ j ≠ k , j , k ≤ 2n × 2 Xi(j , j) = (7) Zi(j , j) = subspace and the kth n-qubit subspace in |Ψ⟩, i Y(j,k) i , as as and Proof: If H can be written as H= ⊗a σxa ⊗b σyb ⊗c σzc 1 + σzjσzik 2 as 1− 2 = c 2 =0 =I (12) ∑ ⟨ϕb(j)|H|ϕb(j)⟩S′(j)S′(j) j = ∑ bj 2⟨ϕj|H|ϕj⟩ j j ≤ 2n = as X(j,k) i , ∑ bm ∑ aj 2⟨ϕj|H|ϕj⟩ 2 m (13) j Combining the two together, we can get ⟨Ψ| (8) j , k ≤ 2n ∑ H(j , k)S′(j)S′(k)|Ψ⟩ = ∑ bm2 j,k m ∑ ajak⟨ϕj|H |ϕk⟩ j,k (14) d We construct a matrix, C, in the space of |Ψ⟩, which has elements ∑m bm2 as (9) ⎛ ⎞2 1 ± σk n • C = ∑± ⎜∑i ∏ki= 1 2 z S′(i)⎟ i ⎝ ⎠ • ∑± over all combinations of positive and negative signs of each digit in each ith of the n-qubit in space |Ψ⟩. ( It can be verified following the rules above that ⟨Ψ|H(′j , k)|Ψ⟩ = ⟨ϕb(j)|H |ϕb(k)⟩ 1+ i i σzjσzj j,k≤r ⊗d Id b = σzij Ii(j , j) = 2 i σzj − σzj 2 j ≤ 2n I(j,k) i . ∏ Xa(j ,k) ∏ Yb(j ,k) ∏ Zc(j ,k) ∏ Id(j ,k) a i i σzj + σzj i = 0 Y i(j , j) = i j≤r We can write the mapped H′(j,k) as H(′j , k) = i j have the same function in different ϕb(j)⟩. Also, and spaces to check the ith digits of |ϕb(j)⟩ and |ϕb(j)⟩. This can be easily verified by the above discussion. Theorem 4: Any Hermitian Hamiltonian in the space of |ψ⟩ can be written in the form of Pauli and identity matrices, which can be mapped to the space of |Ψ⟩ as described above. Notation 3: We denote the mapping between the jth n-qubit i σzjσzik i 1 − σzjσzj 2 j≤r i i (11) ⟨Ψ| ∑ H(j , j)S′(j)S′(j)|Ψ⟩ σzj + σzik 2 σzik − σzj Z(j,k) i ,i 2 ajak ⟨ϕj|H |ϕk ⟩ j,k Thus, as before, we can also get i σzj Also, σiy and i z 2 have the same function in different spaces. These operators are used to check the ith digits of |ϕb(j)⟩ and | i ∑ Also, in the same basis, we have and have the same function in different space to check 2 the digits of |ϕb(j)⟩ and |ϕb(j)⟩. σzj + σzik 2 ∑ bm 2 m i σzjσzik σiz bjS(bj)bk S(bk )⟨ϕj|H |ϕk ⟩ j,k = σzmjσzmk 1 − σzijσzik |Ψ⟩ 2 σ ik − ∑ = ⊗i > m Ii|ϕb(k)⟩ σzijσzik ⟨ϕb(j)|H |ϕb(k)⟩S′(j)S′(k) j,k ij i k ⟨ϕb(j)| ⊗i < m Ii ⊗ ∑ = gives 0; otherwise, 1. (For 1 − σz σz , we omit operators for other 2 digits which are the identity I.) Thus, we get σxm H(j , k)S′(j)S′(k)|Ψ⟩ j,k (10) Thus, if we add the sign functions S′(j) and S′(k), we achieve E ) discuss the entanglement for H2 molecule.38 The general Hamiltonian for such a system is given by • ∑i over all n-qubit collection in |Ψ⟩ to check whether each n qubits is in a certain state. i • ∏nk=1 over each qubits of ith n qubits in |Ψ⟩. i • 1 ± σzk 2 J J H = − (1 + γ )σx1σx 2 − (1 − γ )σy1σy 2 − Bσz1 − Bσz 2 2 2 is to check whether kth qubits of ith n-qubit subspace is in a certain state. 1 + σzk 2 (16) is 1 when the kth qubits are where γ is the degree of anisotropy. In the {|00⟩, |10⟩, |01⟩, |11⟩} basis, the eigenvectors can be written as (here we just use the eigenvectors to show how we map the Hamiltonian, but in an actual calculation, we do not know the eigenvectors) present in the basis |0⟩ or 0 otherwise. ± is to go over combination by ∑±. So far, we have established a mapping between |ψ⟩ and |Ψ⟩. The j,k≤r Hamiltonian H in the space of |ψ⟩ and ∑(j,k) H(j,k) ′ in the space of |Ψ⟩. Also, we have constructed a matrix C to compute ∑m bm2 corresponding to |Ψ⟩. Thus, we have the final results: j , k ≤ 2n j,k≤r ⟨Ψ| ∑ j,k H(j , k)S′(j)S′(k)|Ψ⟩ = ∑ bm2 m ∑ ajak⟨ϕj|H |ϕk⟩ j,k |ξ1⟩ = 1 (|10⟩ + |01⟩) 2 |ξ2⟩ = 1 (|10⟩ − |01⟩) 2 |ξ3⟩ = α − 2B |11⟩ + 2α α + 2B |00⟩ 2α |ξ4⟩ = α + 2B |11⟩ − 2α α − 2B |00⟩ 2α (15) ∑j,k≤r ′ (j,k) H(j,k) Here, we present an algorithm combining and C to calculate the ground state of the initial Hamiltonian H. Notation 4: We mark the eigenvalue of |ψ⟩ for H as λ′. According to the relationship above, the eigenvalue of |Ψ⟩ for H′ is ∑m bm2λ′. Thus, if we choose a λ and construct a Hamiltonian, H′ − λC. The eigenvalue of |Ψ⟩ for H′ − λC is ∑m bm2(λ′ − λ). Theorem 5: The algorithm shown in Chart 1 converges to the minimum eigenvalue of H by finite iterations. Proof: Monotonic Decreasing If we can find an eigenstate |Ψ⟩ of H′ − λC with eigenvalue ∑m bm2(λ′ − λ) < 0. Because ∑m bm2 ≥ 0, we get λ′ − λ < 0. This means we can find an eigenstate |ψ⟩ of H with an eigenvalue λ′ and λ′ − λ < 0. Thus, each time λ decreases monotonically. The minimum eigenvalue: Here we prove that the minimum eigenvalue of H is achievable and the loop will converge when we obtain the minimum eigenvalue. According to Monotonic Decreasing, each time the eigenvalue we get will decrease. Because we have a finite number of eigenvalues, this means we will finally come to the minimum eigenvalue. Also, if we set λ to be the minimum eigenvalue of H, H′ − λC = ∑m bm2(λ′ − λ) ≥ 0 because ∑m bm2 ≥ 0 and λ′ − λ ≥ 0. Also, if λ′ is just the minimum eigenvalue, we get λ′ − λ = 0 and the loop stops. Thus, we prove that the eigenvalue decreases and finally converges to the minimum eigenvalue of H. Theorem 6: To account for the sign, we just need to set i from r 0 to ⎢⎣ 2 ⎥⎦ and set signs of the first ith n-qubit to be negative and the others to be positive in |Ψ⟩. Proof: If we have n qubits in the |Ψ⟩ space with negative sign, where |Ψ⟩ has total i n qubits with negative sign. If these n qubits are not in the first i n qubits, we can rearrange them to the first i n qubits by exchanging them with n qubits in the first i n qubits which have positive sign. Thus, all combinations can be reduced to the combination stated in Theorem 6. Thus, we have established a transformation from an initial Hermitian Hamiltonian to a diagonal Hamiltonian and presented an algorithm to calculate the minimum eigenvalue of the initial Hamiltonian using the diagonal Hamiltonian. (17) where α = 4B2 + J 2 γ . If we set r = 2, for example, if |ψ⟩ = |ξ1⟩, |Ψ⟩ = |10⟩ ⊗ |01⟩ with S′(1) = 1 and S′(2) = 1. If |ψ⟩ = |ξ2⟩, |Ψ⟩ = |10⟩ ⊗ |01⟩ with S′(1) = −1 and S′(2) = 1. Abiding by the previous mapping, the mapped Hamiltonian H′ and matrix C can be written as (this is illustrated in Figure 4) ′ = − Bσz1 − Bσz 2 H(1,1) ′ = − Bσz 3 − Bσz 4 H(2,2) 1 − σz1σz 3 1 − σz 2σz 4 J ′ = − (1 + γ ) H(1,2) 2 2 2 σz1 − σz 3 σz 4 − σz 2 J − (1 − γ ) 2 2 2 σz1 + σz 3 1 + σz 2σz 4 −B 2 2 σz 2 + σz 4 1 + σz1σz 3 −B 2 2 ′ = H(1,2) ′ H(2,1) (18) ⎛1 + σ 1 1 + σ 2 ⎞2 1 + σz1 1 + σz 2 z z C=⎜ S′(1) + S′(2)⎟ 2 2 2 ⎝ 2 ⎠ ⎛1 + σ 1 1 − σ 2 ⎞2 1 + σz1 1 − σz 2 z z +⎜ S′(1) + S′(2)⎟ 2 2 2 ⎝ 2 ⎠ ⎛1 − σ 1 1 + σ 2 ⎞2 1 − σz1 1 + σz 2 z z +⎜ S′(1) + S′(2)⎟ 2 2 2 ⎝ 2 ⎠ ⎛1 − σ 1 1 − σ 2 ⎞2 1 − σz1 1 − σz 2 z z +⎜ S′(1) + S′(2)⎟ 2 2 2 ⎝ 2 ⎠ Example To illustrate the above procedure, we give details of the transformation for the simple model of two spin- 1 electrons with 2 an exchange coupling constant J in an effective transverse magnetic field of strength B. This simple model has been used to (19) If S′(1) = S′(2) = 1, we have F T J Figure 4. Mapped Hamiltonian − 2 (1 + γ )σx1σx 2 between different bases. j,k≤2 H′ = ∑ H(′j , k)S′(j)S′(k) j,k ′ + H(2,2) ′ + H(1,2) ′ + H(2,1) ′ = H(1,1) (20) Figure 5. Comparing the ground state energy from exact (atomic units) of the original Hamiltonian H, eq 16, as a function of the internuclear distance, R (solid line), with the results of the transformed Hamiltonian H′, eqs 20 and 21. We can write matrix C as ⎡4 ⎢ 0 C=⎢ ⎢0 ⎢⎣ 0 0 2 0 0 0 0 2 0 0⎤ ⎥ 0⎥ 0⎥ ⎥ 4⎦ Thus, the 3-local x1x2x3 can be transformed to 2-local by setting x4 = x1x2: If −S′(1) = S′(2) = 1, we have min(x1x 2x3) = min(x4x3 + x1x 2 − 2x1x4 − 2x 2x4 + 3x4) j,k≤2 H′ = ∑ H(′j , k)S′(j)S′(k) x1 , x 2 , x3 , x4 ∈ {0, 1} j,k ′ + H(2,2) ′ − H(1,2) ′ − H(2,1) ′ = H(1,1) (21) min(− x1x 2x3) = min(− x4x3 + x1x 2 − 2x1x4 − 2x 2x4 + 3x4) We can write C in the matrix format: ⎡0 ⎢ 0 C=⎢ ⎢0 ⎢⎣ 0 0 2 0 0 0 0 2 0 x1, x 2 , x3 , x4 ∈ {0, 1} 0⎤ ⎥ 0⎥ 0⎥ ⎥ 0⎦ n ⎛ ⎞ ⎛ 1 + σ 1 1 + σ 2 1 + ∏n σ i i=3 z z z min⎜⎜σz1σz 2 ∏ σzi⎟⎟ = min⎜⎜8 2 2 2 ⎠ ⎝ ⎝ i=3 Reduce Locality of the Transformed Hamiltonian Here we present the procedure to reduce the locality of H′ from a k-local to a 2-local Ising-type Hamiltonian. For x, y, z ∈ {0, 1},29 1 + σz1 + σz 2 + ∏i = 3 σzi + σz1σz 2 + σz1 ∏i = 3 σzi + σz 2 ∏i = 3 σzi ⎞ ⎟⎟ 8 ⎠ n −8 ⎛ = min⎜⎜7 + ⎝ (22) n n n n+1 n ∏ σzi − 3σz1 − 3σz 2 + 6σzn+ 1 + 2 ∏ σzi − σz1 ∏ σzi i=3 ⎞ − σz 2 ∏ σzi − 4σz1σzn + 1 − 4σz 2σzn + 1 + σz1σz 2⎟⎟ ⎠ i=3 and xy ≠ z if xy − 2xz − 2yz + 3z > 0 (25) We can prove that min(x1x2x3 + f(x) = g1(x)) = min(x4x3 + x1x2 − 2x1x4 − 2x2x4 + 3x4 + f(x) = g2(x, x4)), where f(x) is the polynomial of all variables (including x1, x2, x3, and other variables, excluding x4). If there exists x′, this makes g1(x′) be the minimum, and we can always make g2(x′, x4) = g1(x′) by choosing x4 = x1x2. Then, if there exists x″, this makes g2(x″, x4) be the minimum, and then g1(x″) ≤ g2(x″): 1. If x4 = x1x2, g1(x″) = x1x2x3 + f(x″) = x4x3 + x1x2 − 2x1x4 − 2x2x4 + 3x4 + f(x″) = g2(x″,x4). 2. If x4 ≠ x1x2, g2(x″, x4) = x4x3 + x1x2 − 2x1x4 − 2x2x4 + 3x4 + f(x″) ≥ x4x3 + 1 + f(x″) ≥ x1x2x3 + f(x″) = g1(x″) because x4x3 − x1x2x3 ≥ −1. Thus, we have g1(x′) = g2(x′, x4) ≥ g2(x″, x4) ≥ g1(x″) ≥ g1(x′). Thus, we have g1(x′) = g2(x′, x4) = g2(x″, x4) = g1(x″), or all x makes g1(x) minimum would also makes g2(x,x4) minimum and vice versa. Thus, we obtain For −S′(1) = S′(2) = 1, we here display a procedural representation of our algorithm (we set B = 0.001, J = −0.1, and γ = 0): 1. First, when we choose λ = 100, we get that the minimum eigenvalue of H′ − 100C is −400 with |Ψ⟩ = |0000⟩. Thus, we get ∑m bm2 = 4 and λ′ = 0. 2. When we set λ = 0, we get that the minimum eigenvalue of H′ + 0C is −0.2 with |Ψ⟩ = |0110⟩. Thus, we get ∑m bm2 = 2 and λ′ = −0.1. 3. When we set λ = −0.1, we get that the minimum eigenvalue of H′ + 0.1C is 0 with |Ψ⟩ = |0110⟩. We stop here and get that the minimum eigenvalue of H is −0.1. Here we present the result of mapping the above Hamiltonian, eq 12, with B = 0.001, J = −0.821R5/2e−2R, and γ = 038 in Figure 5. xy = z if xy − 2xz − 2yz + 3z = 0 (24) i=3 i=3 n (23) G (26) Table 1. Comparing the Exact Ground Energy (au) and the Simulated Ground Energy (au) (Simulated by 4 × 2 qubits) as a Function of the Intermolecule Distance R (au) R g0 g1 g2 g3 g4 exact simulated 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1.0 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.5 1.55 1.6 1.65 1.7 1.75 1.8 1.85 1.9 1.95 2.0 2.05 2.1 2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 1.5943 1.4193 1.2668 1.1329 1.0144 0.909 0.8146 0.7297 0.6531 0.5836 0.5204 0.4626 0.4098 0.3613 0.3167 0.2755 0.2376 0.2024 0.1699 0.1397 0.1116 0.0855 0.0612 0.0385 0.0173 −0.0023 −0.0208 −0.0381 −0.0543 −0.0694 −0.0837 −0.0969 −0.1095 −0.1213 −0.1323 −0.1427 −0.1524 −0.1616 −0.1703 0.5132 0.5009 0.4887 0.4767 0.465 0.4535 0.4422 0.4313 0.4207 0.4103 0.4003 0.3906 0.3811 0.37200 0.3631 0.3546 0.3463 0.3383 0.3305 0.32299 0.3157 0.3087 0.3018 0.2952 0.2888 0.2826 0.2766 0.2707 0.2651 0.2596 0.2542 0.249 0.244 0.2391 0.2343 0.2297 0.2252 0.2208 0.2165 −1.1008 −1.0366 −0.9767 −0.9208 −0.8685 −0.8197 −0.774 −0.7312 −0.691 −0.6533 −0.6178 −0.5843 −0.5528 −0.523 −0.4949 −0.4683 −0.4431 −0.4192 −0.3966 −0.3751 −0.3548 −0.3354 −0.317 −0.2995 −0.2829 −0.267 −0.252 −0.2376 −0.2238 −0.2108 −0.1983 −0.1863 −0.1749 −0.1639 −0.1536 −0.1436 −0.1341 −0.125 −0.1162 0.6598 0.6548 0.6496 0.6444 0.639 0.6336 0.6282 0.6227 0.6172 0.6117 0.6061 0.6006 0.5951 0.5897 0.5842 0.5788 0.5734 0.5681 0.5628 0.5575 0.5524 0.5472 0.5422 0.5371 0.5322 0.5273 0.5225 0.5177 0.513 0.5084 0.5039 0.4994 0.495 0.4906 0.4864 0.4822 0.478 0.474 0.47 0.0809 0.0813 0.0818 0.0824 0.0829 0.0835 0.084 0.0846 0.0852 0.0859 0.0865 0.0872 0.0879 0.0886 0.0893 0.09 0.0907 0.0915 0.0922 0.09300 0.0938 0.0946 0.0954 0.0962 0.09699 0.0978 0.0987 0.0995 0.1004 0.1012 0.1021 0.10300 0.1038 0.1047 0.1056 0.1064 0.1073 0.1082 0.109 −0.5617 −0.6785 −0.7720 −0.8472 −0.9078 −0.9569 −0.9974 −1.0317 −1.0595 −1.0820 −1.0999 −1.1140 −1.1249 −1.1330 −1.1389 −1.1427 −1.1448 −1.1454 −1.1448 −1.1431 −1.1404 −1.1370 −1.1329 −1.1281 −1.1230 −1.1183 −1.1131 −1.1076 −1.1018 −1.0958 −1.0895 −1.0831 −1.0765 −1.0699 −1.0630 −1.0581 −1.0533 −1.0484 −1.0433 −0.5703 −0.6877 −0.7817 −0.8575 −0.9188 −0.9685 −1.0088 −1.0415 −1.0678 −1.0889 −1.1056 −1.1186 −1.1285 −1.1358 −1.1409 −1.1441 −1.1457 −1.1459 −1.145 −1.1432 −1.1405 −1.1371 −1.1332 −1.1287 −1.1239 −1.1187 −1.1133 −1.1077 −1.1019 −1.0961 −1.0901 −1.0842 −1.0782 −1.0723 −1.0664 −1.0605 −1.0548 −1.0492 −1.0437 n ⎛ ⎞ ⎛ 1 + σ 1 1 + σ 2 1 + ∏n σ i i=3 z z z min⎜⎜ −σz1σz 2 ∏ σzi⎟⎟ = min⎜⎜ −8 2 2 2 ⎝ ⎠ ⎝ i=3 |χ1 ⟩ = |Ψg ⟩|α⟩ = 1 + σz1 + σz 2 + ∏i = 3 σzi + σz1σz 2 + σz1 ∏i = 3 σzi + σz 2 ∏i = 3 σzi ⎞ ⎟⎟ +8 8 ⎠ n ⎛ = min⎜⎜5 − ⎝ n n n+1 i=3 n ⎞ + σz 2 ∏ σzi − 4σz1σzn + 1 − 4σz 2σzn + 1 + 3σz1σz 2⎟⎟ ⎠ i=3 |α ⟩ 2(1 + S) (28) n |χ2 ⟩ = |Ψg ⟩|β⟩ = n ∏ σzi − σz1 − σz 2 + 2σzn+ 1 − 2 ∏ σzi + σz1 ∏ σzi i=3 |Ψ1s⟩1 + |Ψ1s⟩2 |Ψ1s⟩1 + |Ψ1s⟩2 |β ⟩ 2(1 + S) (29) i=3 |χ3 ⟩ = |Ψu⟩|α⟩ = (27) By repeating this, we can reduce the k-local in σz terms to a 2|χ4 ⟩ = |Ψu⟩|β⟩ = local Hamiltonian. Mapping the H2 Hamiltonian to an Ising-Type Hamiltonian |Ψ1s⟩1 − |Ψ1s⟩2 |α ⟩ 2(1 − S) |Ψ1s⟩1 − |Ψ1s⟩2 2(1 − S) (30) |β ⟩ (31) where |Ψ1s⟩1 and |Ψ1s⟩2 are the spatial functions for the two atoms, respectively, |α⟩ and |β⟩ are spin up and spin down, and S = 1⟨Ψ1s|Ψ1s⟩2 is the overlap integral.39 The one- and two-electron integrals are given by Here, we treat the hydrogen molecule in a minimal basis STO6G. By considering the spin functions, the four molecular spin orbitals in H2 are H ⎛ ⎞ ∫ d r χ⃗ i*( r ⃗)⎝− 12 ∇ − Zr ⎠χj ( r ⃗) hij = ⎜ hijkl = By applying the mapping method described above, we can get the Hamiltonian H′ consisting of only σz (where i1 and i2 mean the 1 and 2 qubits of ith 2 qubits): ⎟ (32) ∫ dr→⎯1dr⎯→2 χi*(r→⎯1)χj*(r⎯→2 ) r1 χk (r⎯→2 )χl (r→⎯1) H′ = (33) 12 + h0110a0†a1†a1a0 + h2332a 2†a3†a3a 2 + h0330a0†a3†a3a0 + (h0220 − (σzi2 + σz(j ,2))(1 + σzi1σzj1) S′(i)S′(j) 4 (σ i1 + σzj1)(σzi2 + σzj2) + g3 z S′(i)S′(j) 4 (1 + σzi1σzi1)(1 + σzi2σzj2) + g4 S′(i)S′(j) 4 ⎤ (σ i1 − σzi1)(σzj2 − σzi2) + g4 z S′(i)S′(j)⎥ ⎥⎦ 4 + g2 h0202)a0†a 2†a 2a0 + (h1331 − h1313)a1†a3†a3a1 + h0132(a0†a1†a3a 2 + a 2†a3†a1a0) + h0312(a0†a3†a1a 2 + a 2†a1†a3a0) (34) 25 By using the Bravyi−Kitaev transformation, we have 1 3 1 0 σx σx (σx − iσy 0) 2 1 a1† = (σx 3σx1σz 0 − iσx 3σy1) 2 1 † a 2 = σx 3(σx 2 − iσy 2)σz1 2 1 3 2 1 † a3 = (σx σz σz − iσy 3) 2 a0† = + g2σzi2 + g3σzi1σzi2 ⎡ (σ i1 + σzj1)(1 + σzi2σzj2) + ∑ ⎢g1 z S′(i)S′(j) ⎢ 4 i≠j ⎣ HH2 = h00a0†a0 + h11a1†a1 + h22a 2†a 2 + h33a3†a3 + 1 i Thus, we can write the second-quantization Hamiltonian of H2: h1221a1†a 2†a 2a1 ∑ g1σzi 1 3 1 0 σx σx (σx + iσy 0) 2 1 a1 = (σx 3σx1σz 0 + iσx 3σy1) 2 1 a 2 = σx 3(σx 2 + iσy 2)σz1 2 1 3 2 1 a3 = (σx σz σz + iσy 3) 2 a0 = According to the scheme for reducing locality, if we want to reduce H′ − λC, we can reduce H′ and C separately. By applying the method for reducing locality, we can get a 2-local Ising-type Hamiltonian, H″. Here we show the example of all signs being positive, where akij, k = 1, 2, 3, ..., 6, are the indices of the new qubits we introduce to reduce locality. (35) ⎡ Thus, the Hamiltonian of H2 takes the following form: H″ = + + f6 σx 0σz1σx 2 + f6 σy 0σz1σy 2 + + g3 f7 σz 0σz1σz 2 i≠j σzj1)(σzi2 + + σzj2) 4 (36) + g4 We can utilize the symmetry that qubits 1 and 3 never flip to reduce the Hamiltonian to the following form which just acts on only two qubits a 1 a 1 7 + σzi2σzj2 − 3σzi1 − 3σzj1 + 6σz ij − 4σzi1σz ij − 4σzj1σz ij + σzi1σzj1 4 a 2 a 3 a2 a3 14 + σzi1 + σzj1 − 6(σzi2 + σzj2) + 6(σz ij + σz ij ) + 2(σzi1σz ij + σzj1σz ij ) 4 + (g1 − g4 ) a2 = g 0 1 + H0 a3 −4(σzi2 + σzj2)(σz ij + σz ij ) − (σzi1 + σzj1)(σzi2 + σzj2) + 2σzi2σzj2 4 (37) g3 = 2(f4 + f7 ) 1 + σzi1σzj1 + σzi2σzj2 4 + (g1 − g4 ) HH2 = g01 + g1σz 0 + g2σz1 + g3σz 0σz1 + g4 σx 0σx1 + g4 σy 0σy1 g2 = 2f3 + g4 a 1 + f6 σy 0σz1σy 2σz 3 + f7 σz 0σz1σz 2σz 3 g1 = 2f1 (σzi1 (σ i1 − σzj ,1))(σzi2 − σzj2) + g4 z 4 + f4 σz 0σz 2σz 3 + f3 σz1σz 2σz 3 + f6 σx 0σz1σx 2σz 3 g0 = f0 σzi1 + σzj1 σ i2 + σzj2 + g2 z 4 4 ⎣⎢ ∑ g1σzi1 + g2σzi2 + g3σzi1σzi2 + ∑ ⎢⎢g1 i HH2 = f0 1 + f1 σz 0 + f2 σz1 + f3 σz 2 + f1 σz 0σz1 + f4 σz 0σz 2 f5 σz1σz 3 (40) + g2 g4 = 2f6 a 4 (38) a 5 a 4 a 5 10 − σzi2 − σzj2 − 2(σzi1 + σzj1) + 2(σz ij + σz ij ) − 2(σzi2σz ij + σzj2σz ij ) 4 g0 = 1.0h00 + 0.5h0000 − 0.5h0022 + 1.0h0220 + 1.0h22 a 4 + g2 + 0.5h2222 + 1.0/R a 5 −4(σzi1 + σzj1)(σz ij + σz ij ) + (σzi1 + σzj1)(σzi2 + σzj2) + 6σzi1σzj1 4 a 1 a 6 a 1 a 6 7 + σz ij − 3σzi2 − 3σzj2 + 6σz ij + 2σz ij σz ij + g4 2 g1 = − 1.0h00 − 0.5h0000 + 0.5h0022 − 1.0h0220 g2 = 0.5h0022 − 1.0h0220 − 1.0h22 − 0.5h2222 + g4 g3 = − 1.0h00 − 0.5h0000 + 0.5h0022 − 1.0h0220 g4 = 0.5h0022 ⎤ a 1 a 1 a 6 a 6 −σzi2σz ij − σzj2σz ij − 4σzi2σz ij − 4σzj2σz ij + σzi2σzj2 ⎥ ⎥ 2 ⎦⎥ (41) We can write the corresponding count term C as (39) 2 ⎛ (1 ± σzi1)(1 ± σzi2) ⎞ ⎟⎟ C = ∑ ⎜⎜∑ 4 ⎠ ± ⎝ i where {gi} depends on the fixed bond length of the molecule. In Table 1, we present the numerical values of {gi} as a function of the internuclear distance in the minimal basis set STO-6G. I (42) Figure 6. Results of the simulated transformed Ising-type Hamiltonian with 2 × 2 qubits and 4 × 2 qubits compared with the exact numerical results for the ground state of the H2 molecule. The set of parameters f i is related to the one- and two-electron integrals: By applying the method of reducing locality, the 2-local corresponding count term is C′ = ⎧ 7 7 1⎪ ⎨∑ [7 + σzi2σzj2 − 3σzi1 − 3σzj1 + 6σzaij − 4σzi1σzaij 4⎪ ⎩ i≠j 7 f0 = 1.0h00 + 0.25h0000 − 0.5h0022 + 1.0h0220 + 1.0h22 + 0.25h2222 + 4.0/R f1 = −0.5h00 − 0.25h0000 + 0.25h0022 − 0.5h0220 7 − 4σzj1σzaij + σzi1σzj1 + 2(7 + σzaij − 3σzi2 − 3σzj2 8 1 8 7 + 6σzaij + 2σzaij σz aij ) + 2( −σzi2σzaij − σzj2σzaij 8 f2 = −0.25h0000 + 0.25h0022 − 0.5h0220 − 0.5h00 7 f3 = 0.25h0022 − 0.5h0220 − 0.5h22 − 0.25h2222 8 − 4σzi2σzaij − 4σzj2σzaij + σzi2σzj2) + 14 + σzi1 + σzj1 9 f4 = 0.25h0022 − 0.5h0220 − 0.25h2222 − 0.5h22 1 − 6(σzi2 + σzj2) + 6(σz aij + σzaij 0) 9 aij10 9 aij10 + 2(σzi1σzaij + σzj1σz ) − 4(σzi2 + σzj2)(σzaij + σz ) f5 = 0.25h0000 − (σzi1 + σzj1)(σzi2 + σzj2) + 2σzi2σzj2 + 1 + σzi1σzj1 ⎫ ⎪ (1 + σzi1) + (1 + σzi2) i 2 j2 + σz σz ]⎬ + ∑ ⎪ 4 i ⎭ (43) f6 = −0.25h0022 + 0.25h0220 f7 = 0.25h0220 f8 = 0.25h0220 f9 = 0.25h2222 As stated in the section “Reduce Locality of the Transformed Hamiltonian”, a change in the locality would not change the state when calculating the ground state energy. Thus, we can still use C on certain qubits to calculate ∑i ai2, and the algorithm we present above can still be used for the reduced Hamiltonian. In Figure 6, we show our results from the transformed Isingtype Hamiltonian of 2 × 2 to 4 × 2 qubits compared with the exact numerical values. By increasing the number of qubits via r = 2, we increased the accuracy and the result matches very well with the exact results. Table 1 shows the numerical results. f10 = −0.25h0022 f11 = 0.25h0022 f12 = 0.25h0022 f13 = −0.25h0022 (45) We can also use the mapping and reduction of locality as before to get the final Ising Hamiltonian. Here we just present the mapping result of some terms for illustration. For σz1, the Hamiltonian between different bases can be mapped as Mapping the Hamiltonian for the He2 Molecule to the Ising-Type Hamiltonian As shown above for transforming the Hamiltonian associated with the H2 molecule, we repeat the procedure for the helium molecule in a minimal basis STO-6G using the Jordan−Wigner transformation. The molecular spin Hamiltonian has the form 1 2 3 4 HHe2 = f0 1 + f1 σz + f2 σz + f3 σz + f4 σz + ∑ i≠j (46) f5 σz1σz 2 For σz1σz2, the Hamiltonian between different bases can be mapped as + f6 σz1σz 3 + f7 σz1σz 4 + f8 σz 2σz 3 + f8 σz 2σz 4 + f9 σz 3σz 4 + f10 σx1σx 2σy 3σy 4 + f11 σx1σy 2σy 3σx 4 + f12 σy1σx 2σx 3σy 4 + f13 σy1σy 2σx 3σx 4 (σzi1 + σzj1)(1 + σzi2σzj2)(1 + σzi3σzj3)(1 + σzj4σzi4) S′(i)S′(j) 16 ∑ i≠j (44) (σzi1 + σzj1)(σzi2 + σzj2)(1 + σzi3σzj3)(1 + σzj4σzi4) S′(i)S′(j) 16 (47) J For σx1σx2σy3σy4, the Hamiltonian between different bases can be mapped as ∑ (1 − σzi1σzj1)(1 − σzi2σzj2)(σzi3 − σzj3)(σzj4 − σzi4) 16 i≠j ⎛ ∑ ⎜⎜⎜ i≠j ⎝ σzi1 + σzj1 4 a 1 a 1 2 2 14 + σzi1 + σzj1 − 6(σzi2 + σzj2) + 6(σz ij + σz aij ) + 2(σzi1σz ij + σzj1σz aij ) + 4 ⎞ aij1 aij 2 i1 i2 j2 − 4(σz + σz )(σz + σz ) − (σz + σzj1)(σzi2 + σzj2) + 2σzi2σzj2 ⎟ + ⎟⎟ 4 ⎠ S′(i)S′(j) (48) By reducing locality, we can get the 2-local Ising-type Hamiltonian. However, even just for σx1σx2σy3σy4, the final 2local Ising Hamiltonian would have about 1000 terms. (53) Mapping the Molecular Hamiltonian of LiH to an Ising Hamiltonian + Mapping the Hamiltonian of HeH to an Ising Hamiltonian Similar to H2 and other molecules, next we treat the LiH molecule with four electrons in a minimal basis STO-6G and use the Jordan−Wigner transformation. Using the technique defined above,41 we can reduce the locality to a Hamiltonian with 558 terms on 8 qubits. We just use 16 qubits for the simulations. Similar to H2 and He2 molecules, next we treat the HeH+ molecule in the minimal basis STO-6G using the Jordan− Wigner transformation. Using the technique defined above,40 we can reduce the locality to Computation Complexity and Error Analysis HHeH+ = f0 1 + f1 σz1 + f2 σz 2 + f3 σx1 + f4 σz1σz 2 + f5 σx1σz 2 f7 = 0.25h0002 + 0.25h0020 − 0.5h0222 Specifying the required amount of qubit resources can be derived throughout the multistep process of constructing the final Hamiltonian. As an example, let us consider a Hamiltonian with n total orbitals; transforming this Hamiltonian from second quantization to Pauli operators requires O(n) qubits and a series of O(n4) expansion terms. This is due to the need to use twobody operator and four-body operator terms in formulating the second quantization Hamiltonian. Thus, the number of terms in the second quantization form of the Hamiltonian should be O(n4), yielding O(n4) terms to be described in the Pauli operator representation of the Hamiltonian. Mapping the Hamiltonian from a Pauli operator representation to a diagonal matrix requires an additional O(rn) factor of qubits, and thereby O(2nr2n4) qubits. This is due to the fact that, for each term in the Pauli operator representation of the Hamiltonian, we now have O(2nr2) terms in the diagonal Hamiltonian. This process leads us to the O(r2n4) mapping, which doesin facthave O(2nr2n4) terms. Reducing the representation down to 2-local interactions requires O(rn + 2nr2n7) qubits. Within this form, we do not know r. Consider that the qubit requirement during the reduction from a k-local to 2-local is given by f(k). We have found that f8 = 0.25h0002 + 0.25h0020 + 0.5h0222 f (k) < 10f + f6 σz1σx 2 + f7 σx1σx 2 + f8 σy1σy 2 (49) The set of parameters f i is related to the one- and two-electron integrals: f0 = 1.0h00 + 0.25h0000 + 0.5h0220 + 1.0h22 + 0.25h2222 + 2.0/R f1 = − 0.25h0000 + 0.5h0220 − 0.25h2222 f2 = 0.25h0000 + 0.5h00 − 0.25h2222 − 0.5h22 f3 = − 0.25h0002 − 0.25h0020 + 0.5h0222 f4 = − 0.5h00 − 0.25h0000 + 0.5h22 + 0.25h2222 f5 = − 0.25h0002 − 0.25h0020 − 0.5h0222 f6 = − 1.0h0022 We can also use the mapping and reducing locality as before to get the final Ising Hamiltonian. Again, here we just present the mapping result of some terms for illustration: For σz1σz2, the Hamiltonian between different bases can be mapped as i≠j (σzi1 + σzj1)(σzi2 + σzj2) S′(i)S′(j) 4 (51) For σz1σx2, the Hamiltonian between different bases can be mapped as ∑ i≠j (σzi1 + σzj1)(1 − σzi2σzj2) S′(i)S′(j) 4 log10 3 ) or O(n3) by the master theorem. Thus, for all terms, we finally have O(rn + 2nr2n7) qubits. However, we cannot clearly give a relationship between r and the desired accuracy in the solution. Similarly to the variation method trying to optimize results under particular conditions, this mapping tries to approach the optimal value of the desired ground eigenstate via a new state a by repetition of terms r times. Thus, we cannot calculate the errors associated with our optimal result compared to the exact result, because exact results are unknown within the varational method. Through repeated scaled calculation, we can see that in increasing r we obtain greater accuracy. This is likely due to the fact that by increasing r we increase the number of repetitious terms providing the necessary corrections allowing bi to approach ai. (50) ∑ ( 23 k) which gives us f(k) = O(n ■ AUTHOR INFORMATION Corresponding Author (52) *E-mail: kais@purdue.edu. And if the coefficient of mapping term is positive, we can get the 2-local term as ORCID Sabre Kais: 0000-0003-0574-5346 K Notes (25) Seeley, J. T.; Richard, M. J.; Love, P. J. The Bravyi-Kitaev Transformation for Quantum Computation of Electronic Structure. J. Chem. Phys. 2012, 137, 224109. (26) Kempe, J.; Kitaev, A. Y.; Regev, O. The Complexity of the Local Hamiltonian Problem. SIAM. J. Comput 2006, 35, 1070−1097. (27) Jordan, S. P.; Farhi, E. Perturbative Gadgets at Arbitrary Orders. Phys. Rev. A: At., Mol., Opt. Phys. 2008, 77, 062329. (28) Cao, Y.; Babbush, R.; Biamonte, J.; Kais, S. Hamiltonian Gadgets with Reduced Resource Requirements. Phys. Rev. A: At., Mol., Opt. Phys. 2015, 91, 012315. (29) Bian, Z.; Chudak, F.; Macready, W. G.; Clark, L.; Gaitan, F. Experimental Determination of Ramsey Numbers. Phys. Rev. Lett. 2013, 111, 130505. (30) Kandala, A.; Mezzacapo, A.; Temme, K.; Takita, M.; Chow, J. M.; Gambetta, J. M. Hardware-efficient Quantum Optimizer for Small Molecules and Quantum Magnets. arXiv preprint arXiv:1704.05018, 2017. (31) Smith, J.; Lee, A.; Richerme, P.; Neyenhuis, B.; Hess, P. W.; Hauke, P.; Heyl, M.; Huse, D. A.; Monroe, C. Many-body Localization in a Quantum Simulator with Programmable Random Disorder. Nat. Phys. 2016, 12, 907−911. (32) Babbush, R.; Wiebe, N.; McClean, J.; McClain, J.; Neven, H.; Chan, G. K. Low Depth Quantum Simulation of Electronic Structure. arXiv preprint arXiv:1706.00023, 2017. (33) Lidar, D. A.; Biham, O. Simulating Ising Spin Glasses on a Quantum Computer. Phys. Rev. E: Stat. Phys., Plasmas, Fluids, Relat. Interdiscip. Top. 1997, 56, 3661. (34) Kim, K.; Korenblit, S.; Islam, R.; Edwards, E. E.; Chang, M. S.; Noh, C.; Carmichael, H.; Lin, G. D.; Duan, L. M.; Wang, C. C. J.; Freericks, J. K.; Monroe, C. Quantum Simulation of the Transverse Ising Model with Trapped Ions. New J. Phys. 2011, 13, 105003. (35) Fisher, M. E. The Theory of Equilibrium Critical Phenomena. Rep. Prog. Phys. 1967, 30, 615. (36) Widom, B. Statistical Mechanics: a Concise Introduction for Chemists; Cambridge University Press: Cambridge, U.K., 2002. (37) Kais, S.; Serra, P. Finite-size Scaling for Atomic and Molecular Systems. Adv. Chem. Phys. 2003, 125, 1−100. (38) Huang, Z.; Kais, S. Entanglement as Measure of Electron-electron Correlation in Quantum Chemistry Calculations. Chem. Phys. Lett. 2005, 413, 1−5. (39) Muller, R. P. Python Quantum Chemistry (Pyquante) Program. http://pyquante.sourceforge.net/, 2007. (40) Moll, N.; Fuhrer, A.; Staar, P.; Tavernelli, I. Optimizing Qubit Resources for Quantum Chemistry Simulations in Second Quantization on a Quantum Computer. J. Phys. A: Math. Theor. 2016, 49, 295301. (41) Bravyi, S.; Gambetta, J. M.; Mezzacapo, A.; Temme, K. Tapering off Qubits to Simulate Fermionic Hamiltonians. arXiv preprint arXiv:1701.08213, 2017. The authors declare no competing financial interest. ■ ACKNOWLEDGMENTS We would like to thank Dr. Ross D. Hoehn for both discussion and critical reading of the manuscript. ■ REFERENCES (1) Herschbach, D. R.; Avery, J. S.; Goscinski, O. Dimensional Scaling in Chemical Physics; Springer Science & Business Media: Berlin, 2012. (2) Iachello, F.; Levine, R. D. Algebraic Theory of Molecules; Oxford University Press on Demand: Oxford, U.K., 1995. (3) Kais, S. Quantum Information and Computation for Chemistry; Advances in Chemical Physics; Wiley Online Library: NJ, 2014; Vol. 154, p 224109. (4) Szabo, A.; Ostlund, N. S. Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory; Courier Corporation: MA, 1989. (5) Head-Gordon, M.; Artacho, E. Chemistry on the Computer. Phys. Today 2008, 61, 58. (6) Parr, R. G.; Yang, W. Density-Functional Theory of Atoms and Molecules; Oxford Science Publications: New York, 1989. (7) Mazziotti, D. A. Reduced-Density-matrix Mechanics with Applications to Many-electron Atoms and Molecules. Adv. Chem. Phys. 2007, 134, 1. (8) Nightingale, M. P.; Umrigar, C. J. Quantum Monte Carlo Methods in Physics and Chemistry. NATO Sci. Ser. 1998, 525. (9) Whitfield, J. D.; Love, P. J.; Aspuru-Guzik, A. Computational Complexity in Electronic Structure. Phys. Chem. Chem. Phys. 2013, 15 (2), 397−411. (10) Schuch, N.; Verstraete, F. Computational Complexity of Interacting Electrons and Fundamental Limitations of Density Functional Theory. Nat. Phys. 2009, 5, 732−735. (11) Whitfield, J. D.; Zimborás, Z. On the NP-completeness of the Hartree-Fock Method for Translationally Invariant Systems. J. Chem. Phys. 2014, 141, 234103. (12) Lloyd, S. Universal Quantum Simulators. Science 1996, 273, 1073. (13) Whitfield, J. D.; Biamonte, J.; Aspuru-Guzik, A. Simulation of Electronic Structure Hamiltonians Using Quantum Computers. Mol. Phys. 2011, 109, 735−750. (14) O’Malley, P. J. J.; Babbush, R.; Martinis, J. Scalable Quantum Simulation of Molecular Energies. Phys. Rev. X 2016, 6, 031007. (15) Babbush, R.; Love, P. J.; Aspuru-Guzik, A. Adiabatic Quantum Simulation of Quantum Chemistry. Sci. Rep. 2015, 4, 6603. (16) Boixo, S.; Rønnowand, T. F.; Troyer, M. Evidence for Quantum Annealing with More Than One Hundred Qubits. Nat. Phys. 2014, 10, 218−224. (17) Johnson, M. W.; Amin, M. H. S.; Bunyk, P. Quantum Annealing with Manufactured Spins. Nature 2011, 473, 194−198. (18) Lechner, W.; Hauke, P.; Zoller, P. A Quantum Annealing Architecture with All-to-all Connectivity from Local Interactions. Sci. Adv. 2015, 1, e1500838. (19) McMahon, P. L.; Marandi, A.; Aihara, K. A Fully-programmable 100-spin Coherent Ising Machine with All-to-all Connections. Science 2016, 354, 614−617. (20) Inagaki, T.; Haribara, Y.; Enbutsu, K. A Coherent Ising Machine for 2000-node Optimization Problems. Science 2016, 354, 603−606. (21) Inagaki, T.; Inaba, K.; Takesue, H. Large-scale Ising Spin Network Based on Degenerate Optical Parametric Oscillators. Nat. Photonics 2016, 10, 415−419. (22) Bravyi, S. B.; Kitaev, A. Y. Fermionic Quantum Computation. Ann. Phys. 2002, 298, 210−226. (23) Biamonte, J. D.; Love, P. J. Realizable Hamiltonians for Universal Adiabatic Quantum Computers. Phys. Rev. A: At., Mol., Opt. Phys. 2008, 78, 012352. (24) McWeeny, R.; Sutcliffe, B. T. Methods of Molecular Quantum Mechanics; Academic Press: MA, 1969; Vol. 2. L