Practical quantum advantage on partially fault-tolerant quantum computer

Achieving quantum speedups in practical tasks remains challenging for current noisy intermediate-scale quantum (NISQ) devices. These devices always encounter significant obstacles such as inevitable physical errors and the limited scalability of current near-term algorithms. Meanwhile, assuming a typical architecture for fault-tolerant quantum computing (FTQC), realistic applications inevitably require a vast number of qubits, typically exceeding 10⁶.

In this work, to bridge the gap between the NISQ and FTQC eras, we propose an alternative approach to achieve practical quantum advantages on early-FTQC devices [1], based on the so-called Space-Time efficient Analog Rotation quantum computing (STAR) architecture [2]. This framework is based on partially fault-tolerant logical operations to minimize spatial overhead and avoids the costly distillation techniques typically required for executing non-Clifford gates. To this end, we develop a space-time efficient state preparation protocol to generate an ancillary non-Clifford state consumed for implementing an analog rotation gate with a signicantly high fidelity. Finally, we demonstrate that our framework allows us to perform the QPE for 8×8-site Hubbard model with fewer than 6.8×10⁴ qubits and an execution time shoter than recent classical estimation with tensor network techniques (DMRG and PEPS).

[1] R. Toshio et al., arXiv:2408.14848.

[2] Y. Akahoshi et al., PRX Quantum 5, 010337 (2024).