Recent advances in quantum hardware are bringing fault-tolerant quantum computing (FTQC) closer to reality. In the early stage of FTQC, however, the numbers of available logical qubits and high-fidelity T gates remain limited, making it crucial to optimize the quantum resource usage. In this work, we aim to study the simulation cost of general quantum states under the constraint that only k T gates can be used, alongside an unlimited number of Clifford gates. Inspired by the notion of robustness of magic (RoM) which quantifies the cost of quantum-circuit simulation using stabilizer states (k = 0), we introduce its generalization, which we call Clifford+kT robustness, treating Clifford+kT states as free resources. We explore theoretical properties of Clifford+kT robustness and in particular derive a lower bound that reveals the (in)efficiency of quantum-circuit simulation using Clifford+kT states. Through numerical computations, we also evaluate Clifford+kT robustness for key resource states for universal quantum computation, such as tensor products of the magic states. Our results allow to assess the sampling-cost reduction achieved by the use of Clifford+kT states instead of stabilizer states, providing practical guidance for efficient resource usage in the early-FTQC era.

We introduce a novel non-equilibrium phase -- the quantum many-body scar (QMBS) phase -- that emerges in non-Hermitian many-body dynamics when scarred wavefunctions are selectively stabilized via non-Hermitian driving. Projective measurements, or non-Hermitian counterparts, preferentially reinforce QMBS, counteracting the entropy growth that drives thermalization. As a result, atypical, high-energy scarred wavefunctions that are negligible in the long-time dynamics of closed systems become non-equilibrium steady states. We establish the existence of the QMBS phase and its sharp, first-order phase transition from an ergodic thermal phase, through both analytical arguments and numerical simulations of three representative models: a random quantum circuit model, the SU(q) spin model, and the paradigmatic spin-1 XY model.

We present a unifying framework for quantum power-method-based algorithms through the lens of generalized quantum signal processing (GQSP): we apply GQSP to realize quantum analogues of classical power iteration, power Lanczos, inverse iteration, and folded spectrum methods, all within a single coherent framework. Our approach is efficient in terms of the number of queries to the block encoding of a Hamiltonian. Also, our approach can avoid Suzuki-Trotter decomposition. We constructed quantum circuits for GQSP-based quantum power methods, estimated the number of queries, and numerically verified that this framework works. We additionally benchmark various quantum power methods with molecular Hamiltonians and demonstrate that Quantum Power Lanczos converges faster and more reliably than standard Quantum Power Iteration, while Quantum Inverse Iteration outperforms existing inverse iteration variants based on time-evolution operators. We also show that the Quantum Folded Spectrum Method can obtain excited states without variational optimization. Overall, our results indicate that GQSP-based implementations of power methods combine scalability, flexibility, and robust convergence, paving the way for practical initial state preparations on fault-tolerant quantum devices.

Quantum computing promises to revolutionize many-body simulations for quantum chemistry, but its potential is constrained by limited qubits and noise in current devices. In this work, we introduce the Lossy Quantum Selected Configuration Interaction (Lossy-QSCI) framework, which combines a lossy subspace Hamiltonian preparation pipeline with a generic QSCI selection process. This framework integrates a chemistry-inspired lossy Random Linear Encoder (Chemical-RLE) with a neural network-assisted Fermionic Expectation Decoder (NN-FED). The RLE leverages fermionic number conservation to compress quantum states, reducing qubit requirements to O(N log M) for M spin orbitals and N electrons, while preserving crucial ground state information and enabling self-consistent configuration recovery. NN-FED, powered by a neural network trained with minimal data, efficiently decodes these compressed states, overcoming the measurement challenges common in the approaches of the traditional QSCI and its variants. Through iterative quantum sampling and classical post-processing, our hybrid method refines ground state estimates with high efficiency. Demonstrated on the C2 and LiH molecules, our framework achieves chemical accuracy with fewer qubits and basis states, paving a scalable pathway for quantum chemistry simulations on both near-term and fault-tolerant quantum hardware.

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.