PDF《Exponentially more precise quantum》

500) molecules still seems prohibitively costly [9, 12, 13]. This limitation would preclude simulations of many important molecular systems, such as those in- volved in biological nitrogen ?xation and high-Tc super- conductivity [12, 13]. The canonical quantum algorithm for quantum chem- istry, based on the Trotter-Suzuki decomposition which was ?rst applied for universal quantum simulation in [14, 15], was introduced nearly one decade ago [16]. This approach was later re?ned for implementation with a set of universal quantum gates in [17]. With the exception of the adiabatic algorithm described in [18] and a clas- sical variational optimization strategy making use of a quantum wavefunction ansatz described in [19], all prior quantum algorithms for chemistry have been based on Trotterization [20C27]. Trotter-Suzuki approaches were also applied to simu- lation of evolution under sparse Hamiltonians with the entries given by an oracle [28, 29]. A related problem is the simulation of continuous query algorithms;

in 2009, Cleve et al. showed how to achieve such simulation with exponentially fewer discrete queries than Trotterization in terms of 1/ [30]. The algorithm of [30] still required a number of ancilla qubits that scaled polynomially in 1/ , but this limitation was overcome in [31] which demon- strated that the ancilla register in [30] could be com- pressed into exponentially fewer qubits. In [32, 33], Berry et al. combined the results of [28C31] to show exponen- tially more precise sparse Hamiltonian simulation tech- niques. A major contribution of [32] was to use oblivi- arXiv:1506.01020v2 [quant-ph]

28 Sep

2015 2 ous amplitude ampli?cation to make the algorithm from [30, 31] deterministic, whereas prior versions had relied on probabilistic measurement of ancilla qubits. An im- provement introduced in [33] was to show how to sim- ulate arbitrary Hamiltonians using queries that are not self-inverse (a requirement of the procedure in [32]). We focus on the methodology of [33] which is relatively self- contained. The algorithm of [33] approximates the propagator us- ing a Taylor series expansion rather than the Trotter- Suzuki decomposition. By dividing the desired evolution into a number of simulation segments proportional to the Hamiltonian norm, one can truncate the Taylor series at an order which scales logarithmically in the inverse of the desired precision [33]. The truncated Taylor series must be expressed as a weighted sum of unitary operators. To simulate the action of this operator, one ?rst initializes the system along with an ancilla register that indexes all terms in the Taylor series sum. The ancilla register is then put in a superposition state with amplitudes propor- tional to the coe?cients of terms in the Taylor series sum. Next, an operator is applied to the system which coher- ently executes a single term in the Taylor series sum that is selected according to the ancilla register in superposi- tion. Finally, by applying the transpose of the procedure which prepares the ancilla register, one probabilistically simulates evolution under the propagator. The algorithm is made deterministic using an oblivious amplitude am- pli?cation procedure from [32]. This is the ?rst paper of a two-paper series which ap- plies the algorithm of [33] to quantum chemistry simu- lation. The algorithms discussed in this paper employ a second quantized encoding of the Hamiltonian, where we dynamically perform the Jordan-Wigner transforma- tion [34, 35] on the quantum computer. In the second paper of this series, we use a compressed, ?rst quantized encoding of the wavefunction which requires a number of qubits that scales almost linearly with the number of electrons [36]. In the present paper we develop two new algorithms for the application of the Hamiltonians terms, which we refer to as the database algorithm and the on-the- ?y algorithm. In the database algorithm, the ancilla register'