Search

In this work, we report, for the first time, an implementation of fermionic auxiliary-field quantum Monte Carlo (AFQMC) using matrix product state (MPS) trial wavefunctions, dubbed MPS-AFQMC. Calculating overlaps between an MPS trial and arbitrary Slater determinants up to a multiplicative error, a crucial subroutine in MPS-AFQMC, is proven to be #P-hard. Nonetheless, we tested several promising heuristics in successfully improving fermionic phaseless AFQMC energies. We also proposed a way to evaluate local energy and force bias evaluations free of matrix product operators. This allows for larger basis set calculations without significant overhead. We showcase the utility of our approach on one- and two-dimensional hydrogen lattices, even when the MPS trial itself struggles to obtain high accuracy. Our work offers a new set of tools that can solve currently challenging electronic structure problems with future improvements.

Finding the ground-state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. While the theory of QMA-completeness has been instrumental in understanding the complexity of finding ground states in many-body quantum systems, prior to this work it has been unknown whether or not the special form of the Hamiltonian for the electronic structure of molecules can be exploited to find ground states efficiently or whether the problem remains hard for this special case. We prove that the electronic-structure problem, when restricted to a fixed single-particle basis and a fixed number of electrons, is QMA-complete. In our proof, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian. In contrast, Schuch and Verstraete have proved hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis, by encoding a local Hamiltonian on qubits in the site-specific magnetic field. We also show that estimation of the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is nondeterministic polynomial time (NP)-complete for the electronic-structure Hamiltonian in a fixed basis.

Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions and solved with backtracking tree search augmented with logical inference. In this paper, we show how quantum algorithms can accelerate CP, at both the levels of inference and search. Leveraging existing quantum algorithms, we introduce a quantum-accelerated filtering algorithm for the $\texttt{alldifferent}$ global constraint and discuss its applicability to a broader family of global constraints with similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, including a novel hybrid classical-quantum backtracking search method. This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.

All-electron electronic structure methods based on the linear combination of atomic orbitals method with Gaussian basis set discretization offer a well established, compact representation that forms much of the foundation of modern correlated quantum chemistry calculations—on both classical and quantum computers. Despite their ability to describe essential physics with relatively few basis functions, these representations can suffer from a quartic growth of the number of integrals. Recent results have shown that, for some quantum and classical algorithms, moving to representations with diagonal two-body operators can result in dramatically lower asymptotic costs, even if the number of functions required increases significantly. We introduce a way to interpolate between the two regimes in a systematic and controllable manner, such that the number of functions is minimized while maintaining a block-diagonal structure of the two-body operator and desirable properties of an original, primitive basis. Techniques are analyzed for leveraging the structure of this new representation on quantum computers. Empirical results for hydrogen chains suggest a scaling improvement from O ( N ^4.5 ) in molecular orbital representations to O ( N ^2.6 ) in our representation for quantum evolution in a fault-tolerant setting, and exhibit a constant factor crossover at 15 to 20 atoms. Moreover, we test these methods using modern density matrix renormalization group methods classically, and achieve excellent accuracy with respect to the complete basis set limit with a speedup of 1–2 orders of magnitude with respect to using the primitive or Gaussian basis sets alone. These results suggest our representation provides significant cost reductions while maintaining accuracy relative to molecular orbital or strictly diagonal approaches for modest-sized systems in both classical and quantum computation for correlated systems.

Variational algorithms for strongly correlated chemical and materials systems are one of the most promising applications of near-term quantum computers. We present an extension to the variational quantum eigensolver that approximates the ground state of a system by solving a generalized eigenvalue problem in a subspace spanned by a collection of parametrized quantum states. This allows for the systematic improvement of a logical wavefunction ansatz without a significant increase in circuit complexity. To minimize the circuit complexity of this approach, we propose a strategy for efficiently measuring the Hamiltonian and overlap matrix elements between states parametrized by circuits that commute with the total particle number operator. This strategy doubles the size of the state preparation circuits but not their depth, while adding a small number of additional two-qubit gates relative to standard variational quantum eigensolver. We also propose a classical Monte Carlo scheme to estimate the uncertainty in the ground state energy caused by a finite number of measurements of the matrix elements. We explain how this Monte Carlo procedure can be extended to adaptively schedule the required measurements, reducing the number of circuit executions necessary for a given accuracy. We apply these ideas to two model strongly correlated systems, a square configuration of H _4 and the π -system of hexatriene (C _6 H _8 ).

The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.’s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.

Many NP-hard problems can be seen as the task of finding a ground state of a disordered highly connected Ising spin glass. If solutions are sought by means of quantum annealing, it is often necessary to represent those graphs in the annealer’s hardware by means of the graph-minor embedding technique, generating a final Hamiltonian consisting of coupled chains of ferromagnetically bound spins, whose binding energy is a free parameter. In order to investigate the effect of embedding on problems of interest, the fully connected Sherrington-Kirkpatrick model with random ±1 couplings is programmed on the D-Wave Two^{TM} annealer using up to 270 qubits interacting on a Chimera-type graph. We present the best embedding prescriptions for encoding the Sherrington-Kirkpatrick problem in the Chimera graph. The results indicate that the optimal choice of embedding parameters could be associated with the emergence of the spin-glass phase of the embedded problem, whose presence was previously uncertain. This optimal parameter setting allows the performance of the quantum annealer to compete with (and potentially outperform, in the absence of analog control errors) optimized simulated annealing algorithms.