Significant advances have been made in the study of quantum advantage both in theory and experiment, although these have mostly been limited to artificial setups. In this work, we extend the scope to address quantum advantage in tasks relevant to chemistry and physics. Specifically, we consider the unitary cluster Jastrow (UCJ) ansatz-a variant of the unitary coupled cluster ansatz, which is widely used to solve the electronic structure problem on quantum computers-to show that sampling from the output distributions of quantum circuits implementing the UCJ ansatz is likely to be classically hard. More specifically, we show that there exist UCJ circuits for which classical simulation of sampling cannot be performed in polynomial time, under a reasonable complexity-theoretical assumption that the polynomial hierarchy does not collapse. Our main contribution is to show that a class of UCJ circuits can be used to perform arbitrary instantaneous quantum polynomial-time (IQP) computations, which are already known to be classically hard to simulate under the same complexity assumption. As a side result, we also show that UCJ equipped with post-selection can generate the class post-BQP. Our demonstration, worst-case nonsimulatability of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics using unitary coupled cluster type ansatzes, such as the variational quantum eigensolver and quantum-selected configuration interaction.

Quasiparticle band structures are fundamental for understanding strongly correlated electron systems. While solving these structures accurately on classical computers is challenging, quantum computing offers a promising alternative. Specifically, the quantum subspace expansion (QSE) method, combined with the variational quantum eigensolver (VQE), provides a quantum algorithm for calculating quasiparticle band structures. However, optimizing the variational parameters in VQE becomes increasingly difficult as the system size grows, due to device noise, statistical noise, and the barren plateau problem. To address these challenges, we propose a hybrid approach that combines QSE with the quantum-selected configuration interaction (QSCI) method for calculating quasiparticle band structures. QSCI may leverage the VQE ansatz as an input state but, unlike the standard VQE, it does not require full optimization of the variational parameters, making it more scalable for larger quantum systems. Based on this approach, we demonstrate the quantum computation of the quasiparticle band structure of a silicon using 16 qubits on an IBM quantum processor.

Quantum-selected configuration interaction (QSCI) is a novel quantum-classical hybrid algorithm for quantum chemistry calculations. This method identifies electron configurations having large weights for the target state using quantum devices and allows CI calculations to be performed with the selected configurations on classical computers. In principle, the QSCI algorithm can take advantage of the ability to handle large configuration spaces while reducing the negative effects of noise on the calculated values. At present, QSCI calculations are limited by qubit noise during the input state preparation and measurement process, restricting them to small active spaces. These limitations make it difficult to perform calculations with quantitative accuracy. The present study demonstrates a computational scheme based on multireference perturbation theory calculations on a classical computer, using the QSCI wavefunction as a reference. This method was applied to ground and excited state calculations for two typical aromatic molecules, naphthalene and tetracene. The incorporation of the perturbation treatment was found to provide improved accuracy. Extension of the reference space based on the QSCI-selected configurations as a means of further improvement was also investigated.

We study the Hamiltonian algebra of Jordan-Wigner-transformed interacting fermion models and its fast-forwardability. We prove that the dimension of the Hamiltonian algebra of the fermion model with single-site Coulomb interaction is bounded from below by the exponential function of the number of sites, and the circuit depth of the Cartan-based fast-forwarding method for such model also exhibits the same scaling. We apply this proposition to the Anderson impurity model and the Hubbard model and show that the dimension of the Hamiltonian algebra of these models scales exponentially with the number of sites. These behaviors of the Hamiltonian algebras imply that the qubit models obtained by the Jordan-Wigner transformation of these fermion models cannot be efficiently simulated using the Cartan-based fast-forwarding method.

We present a comprehensive study of the commute time kernel method via the effective resistance framework analyzing the quantum complexity of the originally classical approach. Our study reveals that while there is a trade-off between accuracy and computational complexity, significant improvements can be achieved in terms of runtime efficiency without substantially compromising on precision. Our investigation highlights a notable quantum speedup in calculating the kernel, which offers a quadratic improvement in time complexity over classical approaches in certain instances. In addition, we introduce methodical improvements over the original work on the commute time kernel and provide empirical evidence suggesting the potential reduction of kernel queries without significant impact on result accuracy. Benchmarking our method on several chemistry-based datasets: AIDS, NCL1, PTC−MR, MUTAG, PROTEINS - data points previously unexplored in existing literature, shows that while not always the most accurate, it excels in time efficiency. This makes it a compelling alternative for applications where computational speed is crucial. Our results highlight the balance between accuracy, computational complexity, and speedup offered by quantum computing, promoting further research into efficient algorithms for kernel methods and their applications in chemistry-based datasets.