Understanding which subclasses of quantum circuits are efficiently classically simulable is fundamental to delineating the boundary between classical and quantum computation. In this context, it is well known that certain tasks based on permutation-equivariant unitaries-i.e.,
n-qubit circuits whose action commutes with the qubit-permuting representation of the symmetric group
Sn-can be simulated in polynomial time. However, existing approaches scale as
O(n7), and can rapidly become prohibitively expensive. In this work, we introduce a practical algorithm for simulating
Sn-equivariant circuits under the assumption that the gate generators are at most
k-local, with
k∈O(1). The resulting method runs in
O(nω+1) time for constant depth, where
ω is the matrix multiplication exponent, significantly lowering the polynomial degree compared to existing techniques. Finally, we numerically validate this scaling by simulating the dynamical evolution of the Lipkin-Meshkov-Glick model, and show that for
n=512 spins, a standard laptop can compute the concurrence of the evolved state in under two minutes.
Why quantum computing? As we all know very well, conventional (electronic) computers have enormous power which, moreover, is constantly increasing. With their help gigantic quantities of data can be handled and evaluated. This is of crucial importance, for instance, in modern high energy physics experiments. On the other hand, computers can be used to model very complex systems with the aim of predicting, for example, future developments in our environment, notably climatic changes. Thanks to their incredible speed computers are, of course, destined to treat mathematical problems for which specific algorithms exist very efficiently. To mention a simple example, the digits of π are readily evaluated up to a very high order. Last, but not least, their potential to solve differential equations numerically, even when they are nonlinear, makes computers indispensable in modern research. So, one might ask, is there any reason to look for fundamentally new ways of computing as they are seemingly offered by quantum processes? What advantages can be expected when the laws of quantum mechanics, rather than those of classical physics, are exploited for computation? Two answers were given: first, the simulation of complex quantum systems on classical computers meets serious difficulties that might be overcome with the help of quantum computers. This idea was suggested in 1982 by R. Feynman, and in the 1990s it was indeed shown by several groups of researchers that quantum mechanical systems for which no efficient simulation on a classical computer is known can be efficiently simulated on a quantum computer.
The ATLAS Physics challenge at the HL-LHC and ideas about Quantum Computing. 0:00:00 Slide 1 0:01:44 Slide 2 0:02:12 Slide 3 0:02:49 Slide 4 0:03:46 Slide 5 0:05:10 Slide 6 0:05:43 Slide 7 0:06:19 Slide 8 0:06:35 Slide 9 0:06:56 Slide 10 0:07:37 Slide 11 0:08:01 Slide 12 0:09:32 Slide 13 0:10:52 Slide 14 0:11:47 Slide 15 0:12:43 Slide 16 0:13:52 Slide 17 0:14:46 Slide 18 0:15:39 Slide 19 0:16:35 Slide 20 0:17:02 Slide 21 0:17:43 Slide 22 0:18:52 Slide 23 0:19:37 Slide 24 0:19:59 Slide 25 0:21:13 Slide 26 0:23:31 Slide 27 0:24:00 Slide 28 0:24:04 Slide 29
Quantum-selected configuration interaction (QSCI) utilizes an input quantum state on a quantum device to select important bases (electron configurations in quantum chemistry) that define a subspace in which to diagonalize a target Hamiltonian, i.e., perform selected configuration interaction, on classical computers. Previous proposals for preparing a good input state, which is crucial for the quality of QSCI, based on optimization of quantum circuits may suffer from optimization difficulty and require many runs of the quantum device. Here, we propose using a time-evolved state by the target Hamiltonian (for some initial state) as an input of QSCI. Our proposal is based on the intuition that the time evolution by the Hamiltonian creates electron excitations of various orders when applied to the initial state. We numerically investigate the accuracy of the energy obtained by the proposed method for quantum chemistry Hamiltonians describing electronic states of small molecules. Numerical results reveal that our method can yield sufficiently accurate ground-state energies for the investigated molecules. Systematic analysis when increasing the number of qubits in a hydrogen chain shows that the subspace size required for sufficiently accurate results is reasonable at system sizes that cannot be solved by naive classical diagonalization. Our proposal provides a systematic and optimization-free method to prepare the input state of QSCI and could contribute to practical applications of quantum computers in quantum chemistry calculations.