(Section VIII.1)
$\sum_{n^{\prime}}c_{n^{\prime}}\ket{\phi_{n^{\prime}}(0)}$, $|c_{n}|\geq\gamma$ | $\ket{\phi_{n}(t)}+\order{\delta}$ | $\frac{\alpha T+\log(1/\Delta)}{\gamma\Delta}\log\left(\frac{1}{\delta}\right)\log\left(\frac{1}{\gamma\delta}\right)$ | $\frac{1}{\gamma}\log\left(\frac{1}{\delta}\right)$
| Floquet, $H(t)$
---
(Section VIII.2)
$\sum_{n^{\prime}}c_{n^{\prime}}\ket{\phi_{n^{\prime}}(0)}$, $|c_{n}|\geq\gamma$ | $\ket{\Phi_{n}}+\order{\delta}$ | $\frac{\alpha T+N+\log(1/\Delta\gamma\delta)}{\gamma\Delta}\log\left(\frac{1}{\delta}\right)\log\left(\frac{1}{\gamma\delta}\right)$ | $\frac{1}{\gamma}\log\left(\frac{1}{\delta}\right)$
Table 2: Cost of eigenstate preparation for time-independent and time-periodic
Hamiltonians under a promised gap $\Delta$. A preferable Floquet eigenstate,
either $\ket{\phi_{n}(t)}\in\mathcal{H}$ or
$\ket{\Phi_{n}}\in\mathcal{H}^{\infty}$ can be prepared in nearly optimal
query complexity in the parameters. The difference from time-independent cases
is at most logarithmic corrections in all the parameters
$\gamma,\Delta,\delta$.

###  VIII.2 Eigenstate preparation of $\ket{\Phi_{n}}$

The preparation of a preferable Floquet eigenstate $\ket{\Phi_{n}}$ living in
the Sambe space is also formulated by the Floquet QPE. Let us assume without
loss of generality that the preferable quasienergy $\epsilon_{n}$ is located
in $[(-1/2+\Delta)\omega,(1/2-\Delta)\omega)$ (If not, we move the origin of
the BZ by multiplying a global phase). Then, we can use the Floquet QPE
without rounding promise in Section VII.4, where the parameters are chosen by
$\varepsilon\leftarrow\Delta/2$ and $\delta\leftarrow\gamma\delta$. We get a
unitary operation $U_{\mathrm{FQPE}}^{\mathrm{Sambe}}$ such that

$\displaystyle
U_{\mathrm{FQPE}}^{\mathrm{Sambe}}\ket{0}_{g}\ket{0}_{b}\ket{0}_{f}\ket{\psi}=$
$\displaystyle\qquad\sum_{n^{\prime}}c_{n^{\prime}}\left(\sum_{i=0,1}p_{i}^{n^{\prime}}\ket{g_{i}^{n^{\prime}}}_{g}\ket{(\epsilon_{n^{\prime}})_{bi}}_{b}\right)\ket{\Phi_{n^{\prime}}}+\order{\gamma\delta}.$

The promised gap $\Delta$ and the accuracy of the Floquet QPE ensure that the
projection $\Pi_{n,\Delta}\otimes I_{g}\otimes I_{f}$ by Eq. (155) keeps only
the preferable component with $\ket{\Phi_{n}}$ in the above state, and it
allows us to form the block-encoding $U_{\mathrm{FQPE}}^{\mathrm{Sambe}}$ like
Eq. (157). Again, we can run QAA based on QSVT, which does the transformation,

$\ket{\psi}\to\left(\sum_{i=0,1}p_{i}^{n^{\prime}}\ket{g_{i}^{n}}_{g}\ket{(\epsilon_{n})_{bi}}_{b}\right)\otimes\ket{\Phi_{n}}+\order{\delta}.$
(160)

Discarding the ancilla systems other than $f$ completes the accurate
preparation of the preferable Floquet eigenstate $\ket{\Phi_{n}}$ (or more
presicely, the eigenstate of the truncated Floquet Hamiltonian).

The cost is evaluated in a similar way as in Section VIII.1. The query
complexity in $C[O_{H_{m}}]$ or its inverse amounts to the product of that of
the Floquet QPE,

$\order{\frac{\alpha
T+N+\log(1/\Delta\gamma\delta)}{\Delta}\log(1/\gamma\delta)},$ (161)

and that of QAA, $\order{q}=\order{\gamma^{-1}\log(1/\delta)}$. The query
complexity in the state preparation unitary $U_{\psi}$ or its inverse, which
are used for the counterpart of the parametrized unitary
$R_{\Pi_{\psi}}(\theta)$, is $\order{q}=\order{\gamma^{-1}\log(1/\delta)}$.
These results are summarized in the last row of Table 2. Like the preparation
of $\ket{\phi_{n}(t)}$ in Section VIII.1, the preparation of $\ket{\Phi_{n}}$
can also be performed in nearly optimal query complexity. The scaling in the
gap $\Delta$ is $\order{\Delta^{-1}\log\Delta^{-1}}$ and that in the overlap
$\gamma$ is $\order{\gamma^{-1}\log^{2}\gamma^{-1}}$, both of which differ
from the optimal algorithm for time-independent cases by at most logarithmic
corrections.

##  IX Conclusion and Discussion

Throughout the paper, we have focused on the problem of computing quasienergy
and Floquet eigenstates under time-periodic Hamiltonians, and have organized
efficient quantum algorithms for it. Our algorithms can output pairs of
accurate quasienergy and a Floquet eigenstate in a coherent way, referred to
as “Floquet quantum phase estimation (Floquet QPE)”, and also
deterministically prepare a preferable gapped Floquet eigenstate based on the
Floquet QPE. Time-periodic systems have the difficulty of time-dependency or
equivalently infinite-dimensionality of the Sambe space compared to time-
independent cases. Nevertheless, these quantum algorithms achieve nearly
optimal query complexity whose difference from the optimal algorithms for
time-independent cases is at most logarithmic in all the parameters. Note that
this efficiency comes from the interplay of nonequilibrium many-body physics
and quantum algorithms; The guaranteed accuracy is derived from the Sambe
space formalism in Floquet theory, and the Lieb-Robinson bound or the
localization of Floquet eigenstates. The computational resources increased by
the Sambe space can be small in quantum algorithms according to the QPE and
the QAA, which allows us to solve the time-dependent problems almost as
efficiently as the time-independent problems.

The computation of energy eigenvalues and eigenstates has been a central
problem in fundamental quantum many-body physics, and offers various
applications in condensed matter physics and quantum chemistry. Our quantum
algorithms first achieve nearly optimal query complexity for its natural
extension to time-periodic systems, which will provide a deep insight into the
complexity of nonequilibrium systems like the sampling complexity of time-
periodic systems [66]. We also expect that it will provide a powerful tool for
exploring nonequilibrium phases of matter: For instance, in Floquet time
crystalline phases [6, 7, 8], every low-entangled state (e.g. product state)
becomes a superposition of Floquet eigenstates which are vulnerable to noise
and measurement (e.g. cat states). Since these Floquet eigenstates have
equally large weight and a quasienergy gap $\omega/n$ ($n=2,3,\ldots$), our
quantum algorithms will be useful for the identification of time crystals by
confirming their properties. Similarly, various nonequilibrium phenomena such
as Floquet many-body localization [14, 15, 16, 17] and Floquet quantum many-
body scars [19, 20] are characterized by Floquet eigenstates, and hence they
are also in the scope. On the other hand, generic nonintegrable time-periodic
Hamiltonians are believed to satisfy Floquet eigenstate thermalization
hypothesis [67, 68], where every Floquet eigenstate is locally
indistinguishable from a trivial infinite temperature state. Although this is
an undesired phenomenon in condensed matter physics, which is known as
heating, our quantum algorithms for nearly optimal Floquet eigenstate
preparation will serve as a source of randomness appearing in time-periodic
Hamiltonians [66].

## Acknowledgment

We thank T. N. Ikeda for fruitful discussion. We also thank S. Kitamura for
giving us some useful information about Floquet theory. K. M. is supported by
JST PRESTO Grant No. JPMJPR235A.

## References

  * Oka and Aoki [2009] T. Oka and H. Aoki, Photovoltaic hall effect in graphene, Phys. Rev. B 79, 081406 (2009).
  * Oka and Kitamura [2019] T. Oka and S. Kitamura, Floquet Engineering of Quantum Materials, Annual Review of Condensed Matter Physics 10, 387 (2019).
  * Kitagawa  _et al._ [2010] T. Kitagawa, E. Berg, M. Rudner, and E. Demler, Topological characterization of periodically driven quantum systems, Phys. Rev. B: Condens. Matter Mater. Phys. 82, 235114 (2010).
  * Rudner  _et al._ [2013] M. S. Rudner, N. H. Lindner, E. Berg, and M. Levin, Anomalous edge states and the bulk-edge correspondence for periodically driven two-dimensional systems, Physical Review X 3, 031005 (2013).
  * Harper  _et al._ [2019] F. Harper, R. Roy, M. S. Rudner, and S. L. Sondhi, Topology and Broken Symmetry in Floquet Systems, arXiv:1905.01317 [cond-mat.str-el] (2019).
  * Khemani  _et al._ [2016] V. Khemani, A. Lazarides, R. Moessner, and S. L. Sondhi, Phase Structure of Driven Quantum Systems, Phys. Rev. Lett. 116, 250401 (2016).
  * Else  _et al._ [2016] D. V. Else, B. Bauer, and C. Nayak, Floquet Time Crystals, Phys. Rev. Lett. 117, 090402 (2016).
  * Khemani  _et al._ [2019] V. Khemani, R. Moessner, and S. L. Sondhi, A Brief History of Time Crystals, arXiv:1910.10745 [cond-mat.str-el] (2019).
  * Abanin  _et al._ [2015] D. A. Abanin, W. De Roeck, and F. Huveneers, Exponentially slow heating in periodically driven Many-Body systems, Phys. Rev. Lett. 115, 256803 (2015).
  * Mori  _et al._ [2016] T. Mori, T. Kuwahara, and K. Saito, Rigorous Bound on Energy Absorption and Generic Relaxation in Periodically Driven Quantum Systems, Phys. Rev. Lett. 116, 120401 (2016).
  * Kuwahara  _et al._ [2016] T. Kuwahara, T. Mori, and K. Saito, Floquet–Magnus theory and generic transient dynamics in periodically driven many-body quantum systems, Ann. Phys. 367, 96 (2016).
  * Abanin  _et al._ [2017a] D. Abanin, W. De Roeck, W. W. Ho, and F. Huveneers, A Rigorous Theory of Many-Body Prethermalization for Periodically Driven and Closed Quantum Systems, Commun. Math. Phys. 354, 809 (2017a).
  * Abanin  _et al._ [2017b] D. A. Abanin, W. De Roeck, W. W. Ho, and F. Huveneers, Effective hamiltonians, prethermalization, and slow energy absorption in periodically driven many-body systems, Phys. Rev. B Condens. Matter 95, 014112 (2017b).
  * Ponte  _et al._ [2015] P. Ponte, Z. Papić, F. m. c. Huveneers, and D. A. Abanin, Many-body localization in periodically driven systems, Phys. Rev. Lett. 114, 140401 (2015).
  * Lazarides  _et al._ [2015] A. Lazarides, A. Das, and R. Moessner, Fate of many-body localization under periodic driving, Phys. Rev. Lett. 115, 030402 (2015).
  * Abanin  _et al._ [2016] D. A. Abanin, W. De Roeck, and F. Huveneers, Theory of many-body localization in periodically driven systems, Ann. Phys. 372, 1 (2016).
  * Bordia  _et al._ [2017] P. Bordia, H. Lüschen, U. Schneider, M. Knap, and I. Bloch, Periodically driving a many-body localized quantum system, Nat. Phys. 13, 460 (2017).
  * Mukherjee  _et al._ [2020] B. Mukherjee, S. Nandy, A. Sen, D. Sen, and K. Sengupta, Collapse and revival of quantum many-body scars via Floquet engineering, Phys. Rev. B 101, 245107 (2020).
  * Sugiura  _et al._ [2021] S. Sugiura, T. Kuwahara, and K. Saito, Many-body scar state intrinsic to periodically driven system, Phys. Rev. Res. 3, L012010 (2021).
  * Mizuta  _et al._ [2020] K. Mizuta, K. Takasan, and N. Kawakami, Exact Floquet quantum many-body scars under Rydberg blockade, Phys. Rev. Res. 2, 033284 (2020).
  * Abrams and Lloyd [1999] D. S. Abrams and S. Lloyd, Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors, Phys. Rev. Lett. 83, 5162 (1999).
  * Aspuru-Guzik  _et al._ [2005] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Simulated quantum computation of molecular energies, Science 309, 1704 (2005).
  * Sambe [1973] H. Sambe, Steady states and quasienergies of a quantum-mechanical system in an oscillating field, Phys. Rev. A 7, 2203 (1973).
  * Guérin and Jauslin [2003] S. Guérin and H. R. Jauslin, Control of quantum dynamics by laser pulses: Adiabatic Floquet theory, in  _Advances in chemical physics_ (John Wiley & Sons, Inc., 2003) pp. 147–267.
  * Mikami  _et al._ [2016] T. Mikami, S. Kitamura, K. Yasuda, N. Tsuji, T. Oka, and H. Aoki, Brillouin-Wigner theory for high-frequency expansion in periodically driven systems: Application to Floquet topological insulators, Phys. Rev. B 93, 144307 (2016).
  * Rodriguez-Vega  _et al._ [2018] M. Rodriguez-Vega, M. Lentz, and B. Seradjeh, Floquet perturbation theory: formalism and application to low-frequency limit, New J. Phys. 20, 093022 (2018).
  * Fauseweh and Zhu [2023] B. Fauseweh and J.-X. Zhu, Quantum computing Floquet energy spectra, Quantum 7, 1063 (2023).
  * Mizuta and Fujii [2023] K. Mizuta and K. Fujii, Optimal Hamiltonian simulation for time-periodic systems, Quantum 7, 962 (2023).
  * Eckstein  _et al._ [2023] T. Eckstein, R. Mansuroglu, P. Czarnik, J.-X. Zhu, M. J. Hartmann, L. Cincio, A. T. Sornborger, and Z. Holmes, Large-scale simulations of Floquet physics on near-term quantum computers, arXiv:2303.02209 [quant-ph] (2023).
  * Mizuta [2023] K. Mizuta, Optimal and nearly optimal simulation of multiperiodic time-dependent hamiltonians, Phys. Rev. Res. 5, 033067 (2023).
  * Lloyd [1996] S. Lloyd, Universal Quantum Simulators, Science 273, 1073 (1996).
  * Low and Chuang [2017] G. H. Low and I. L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing, Phys. Rev. Lett. 118, 010501 (2017).
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  * Yu. Kitaev [1995] A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026 [quant-ph] (1995).
  * Cleve  _et al._ [1998] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 339 (1998).
  * Poulin and Wocjan [2009a] D. Poulin and P. Wocjan, Preparing ground states of quantum many-body systems on a quantum computer, Phys. Rev. Lett. 102, 130503 (2009a).
  * Ge  _et al._ [2019] Y. Ge, J. Tura, and J. I. Cirac, Faster ground state preparation and high-precision ground energy estimation with fewer qubits, J. Math. Phys. 60, 022202 (2019).
  * Lin and Tong [2020] L. Lin and Y. Tong, Near-optimal ground state preparation, Quantum 4, 372 (2020).
  * Poulin and Wocjan [2009b] D. Poulin and P. Wocjan, Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer, Phys. Rev. Lett. 103, 220502 (2009b).
  * Bilgin and Boixo [2010] E. Bilgin and S. Boixo, Preparing thermal states of quantum systems by dimension reduction, Phys. Rev. Lett. 105, 170405 (2010).
  * Riera  _et al._ [2012] A. Riera, C. Gogolin, and J. Eisert, Thermalization in nature and on a quantum computer, Phys. Rev. Lett. 108, 080402 (2012).
  * Chowdhury and Somma [2016] A. N. Chowdhury and R. D. Somma, Quantum algorithms for Gibbs sampling and hitting-time estimation (2016), arXiv:1603.02940 [quant-ph] .
  * Gilyén  _et al._ [2019] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics, in  _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) pp. 193–204.
  * Rall [2021] P. Rall, Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation, Quantum 5, 566 (2021).
  * Martyn  _et al._ [2021] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand Unification of Quantum Algorithms, PRX Quantum 2, 040203 (2021).
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
  * Brassard  _et al._ [2002] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Information , 53–74 (2002).
  * Kitaev  _et al._ [2002] A. Y. Kitaev, A. Shen, and M. N. Vyalyi,  _Classical and Quantum Computation_ (American Mathematical Soc., 2002).
  * Zener [1934] C. Zener, A theory of the electrical breakdown of solid dielectrics, Proc. R. Soc. Lond. A 145, 523 (1934).
  * Wannier [1960] G. H. Wannier, Wave functions and effective hamiltonian for bloch electrons in an electric field, Phys. Rev. 117, 432 (1960).
  * Hone  _et al._ [1997] D. W. Hone, R. Ketzmerick, and W. Kohn, Time-dependent floquet theory and absence of an adiabatic limit, Phys. Rev. A 56, 4045 (1997).
  * Lindner  _et al._ [2017] N. H. Lindner, E. Berg, and M. S. Rudner, Universal chiral quasisteady states in periodically driven many-body systems, Phys. Rev. X 7, 011018 (2017).
  * Rudner and Lindner [2020] M. S. Rudner and N. H. Lindner, The floquet engineer’s handbook, arXiv:2003.08252 [cond-mat.mes-hall] (2020).
  * Bhatia [2013] R. Bhatia,  _Matrix Analysis_ (Springer Science & Business Media, 2013).
  * Levante  _et al._ [1995] T. O. Levante, M. Baldus, B. H. Meier, and R. R. Ernst, Formalized quantum mechanical Floquet theory and its application to sample spinning in nuclear magnetic resonance, Mol. Phys. 86, 1195 (1995).
  * Lieb and Robinson [1972] E. H. Lieb and D. W. Robinson, The finite group velocity of quantum spin systems, Commun. Math. Phys. 28, 251 (1972).
  * Nachtergaele and Sims [2006] B. Nachtergaele and R. Sims, Lieb-Robinson bounds and the exponential clustering theorem, Commun. Math. Phys. 265, 119 (2006).
  * Gong and Hamazaki [2022] Z. Gong and R. Hamazaki, Bounds in nonequilibrium quantum dynamics, International Journal of Modern Physics B 36, 2230007 (2022).
  * Childs  _et al._ [2021] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Theory of trotter error with commutator scaling, Phys. Rev. X 11, 011020 (2021).
  * Berry  _et al._ [2017] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Exponential improvement in precision for simulating sparse Hamiltonians, Forum of Mathematics, Sigma 5, e8 (2017).
  * Grover [1997] L. K. Grover, Quantum Mechanics Helps in Searching for a Needle in a Haystack, Phys. Rev. Lett. 79, 325 (1997).
  * Høyer [2000] P. Høyer, Arbitrary phases in quantum amplitude amplification, Phys. Rev. A 62, 052304 (2000).
  * Long [2001] G. L. Long, Grover algorithm with zero theoretical failure rate, Phys. Rev. A 64, 022307 (2001).
  * Note [1] $R_{\Pi_{0}}(\theta)$ is implemented by $\order{\log L}$ Toffoli gates, $\order{\log L}$ additional qubits, and one controlled-phase gate. The implementation of $R_{\Pi_{1}}(\theta)$ exploits the quantum comparator, which transforms $\mathinner{|{x}\rangle}\mathinner{|{0}\rangle}\to\mathinner{|{x}\rangle}\mathinner{|{\mathrm{bool}(x>m)}\rangle}$ for a $b$-bit variable $x$ and a constant $m$.
  * Note [2] We note that the factor $\log(1/\delta)$ is added to the query complexity in Ref. [38] for fair comparison. While Ref. [38] executes the QAA so that they can succeed in the state preparation with some constant property, we require the success probability to be greater than $1-\order{\delta}$. The cost of achieving it by QAA appears as an additional factor of $\log(1/\delta)$.
  * Tangpanitanon  _et al._ [2023] J. Tangpanitanon, S. Thanasilp, M.-A. Lemonde, N. Dangniam, and D. G. Angelakis, Signatures of a sampling quantum advantage in driven quantum many-body systems, Quantum Sci. Technol. 8, 025019 (2023).
  * D’Alessio and Rigol [2014] L. D’Alessio and M. Rigol, Long-time behavior of isolated periodically driven interacting lattice systems, Phys. Rev. X 4, 041048 (2014).
  * Lazarides  _et al._ [2014] A. Lazarides, A. Das, and R. Moessner, Equilibrium states of generic quantum systems subject to periodic driving, Phys. Rev. E 90, 012110 (2014).
  * Sachdeva [2013] S. Sachdeva, Faster algorithms via approximation theory, Found. Trends Theor. Comput. Sci. 9, 125 (2013).

Appendix

##  Appendix A Exponential tails of Floquet eigenstates

Theorem 3 in the main text states the exponential decay of every Fourier
component $\ket{\phi_{n}^{l}}$ in $l\in\mathbb{Z}$ of Floquet eigenstates.
This is related to the localization on one-dimensional lattice under linear
potential, where the Fourier index $l\in\mathbb{Z}$ plays a role of the
coordinate. While several references such as Refs. [51, 52, 53] mention about
the exponential decay in Floquet eigenstates, we cannot find an explicit bound
that fits our setup. For this paper to be self-contained, we provide a
rigorous proof of Theorem 3. The theorem is restated as follows.

######  Theorem 3.

(Tails of Floquet eigenstates)

Suppose that a Floquet eigenstate $\ket{\phi_{n}(t)}$ or equivalently
$\ket{\Phi_{n}}$ has quasienergy
$\epsilon_{n}\in\mathrm{BZ}=[-\omega/2,\omega/2)$ under the Hamiltonian, Eq.
(27). Then, every Fourier component exponentially decays as

$\norm{\ket{\phi_{n}^{l}}}\leq\exp\left(-\frac{|l|-1/2}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right).$ (162)

The proof consists of three main steps. In the first step, we show the
exponential decay in each eigenstate of the truncated Floquet Hamiltonian
$H_{\mathrm{F}}^{L}$ instead of the exact one (Proposition A1). The second
step is to show that the eigenspace of the truncated Floquet Hamiltonian well
approximates the subspace spanned by the exact Floquet eigenstates
(Proposition A2). Finally, we combine them and prove that the Floquet
eigenstates must also show exponential decay as Theorem 3. We hereby provide
the first step and its derivation.

######  Proposition A1.

(Truncated Floquet eigenstates)

Let $\ket{\tilde{\Phi}_{n}^{L}}\in\mathcal{H}^{L}$ be an eigenstate of the
truncated Floquet Hamiltonian $H_{\mathrm{F}}^{L}$ as
$H_{\mathrm{F}}^{L}\ket{\tilde{\Phi}_{n}^{L}}=\tilde{\epsilon}_{n}^{L}\ket{\tilde{\Phi}_{n}^{L}}$.
We define projections to a certain Fourier index $l\in\mathbb{Z}$ and an
eigenspectra $E\subset\mathbb{R}$ respectively by

$\displaystyle P_{l}$ $\displaystyle=$ $\displaystyle\ket{l}\bra{l}_{f}\otimes
I,$ (163) $\displaystyle\tilde{P}^{L}(E)$ $\displaystyle=$
$\displaystyle\sum_{n:\tilde{\epsilon}_{n}^{L}\in
E}\ket{\tilde{\Phi}_{n}^{L}}\bra{\tilde{\Phi}_{n}^{L}}.$ (164)

Then, for arbitrary $l\in[L]$,

$\norm{P_{l}\tilde{P}^{L}(E)}\leq\exp\left(-\frac{|l|-\epsilon_{\mathrm{max}}/\omega}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right)$ (165)

is satisfied with $\epsilon_{\mathrm{max}}=\max_{\epsilon\in E}(|\epsilon|)$.

Proof of Proposition A1.— We start with the case $l\geq 0$. For arbitrary
$\lambda\in\mathbb{R}$, we obtain the following inequality:

$\displaystyle\norm{P_{l}\tilde{P}^{L}(E)}$ $\displaystyle=$
$\displaystyle\norm{P_{l}e^{\lambda H_{\mathrm{F}}^{L}}e^{-\lambda
H_{\mathrm{F}}^{L}}\tilde{P}^{L}(E)}$ (166) $\displaystyle\leq$
$\displaystyle\norm{P_{l}e^{\lambda
H_{\mathrm{F}}^{L}}}\cdot\norm{\sum_{\tilde{\varepsilon}_{n}\in
E}e^{-\lambda\tilde{\varepsilon}_{n}}\ket{\tilde{\Phi}_{n}^{L}}\bra{\tilde{\Phi}_{n}^{L}}}$
$\displaystyle\leq$ $\displaystyle e^{\max_{\varepsilon\in
E}(|\lambda\varepsilon|)}\sqrt{\norm{\braket{l}{e^{2\lambda
H_{\mathrm{F}}^{L}}}{l}_{f}}}.$

We should evaluate a bound on $\norm{\braket{l}{e^{2\lambda
H_{\mathrm{F}}^{L}}}{l}_{f}}$. By splitting the Floquet Hamiltonian into
$H_{\mathrm{F}}^{L}=H_{\mathrm{Add}}^{L}-H_{\mathrm{LP}}^{L}$ with

$\displaystyle H_{\mathrm{Add}}^{L}$ $\displaystyle=$
$\displaystyle\sum_{|m|\leq
M}\sum_{l\in[L];l+m\in[L]}\ket{l+m}\bra{l}_{f}\otimes H_{m},$ (167)
$\displaystyle H_{\mathrm{LP}}^{L}$ $\displaystyle=$
$\displaystyle\sum_{l\in[L]}l\omega\ket{l}\bra{l}_{f}\otimes I,$ (168)

we use an interaction picture based on $H_{\mathrm{LP}}^{L}$. The imaginary-
time evolution $e^{2\lambda H_{\mathrm{F}}^{L}}$ is rewritten by

$\displaystyle e^{2\lambda H_{\mathrm{F}}^{L}}$ $\displaystyle=$
$\displaystyle e^{-2\lambda
H_{\mathrm{LP}}^{L}}\mathcal{T}\exp\left(\int_{0}^{2\lambda}H_{\mathrm{Add},I}^{L}(\tau)\differential\tau\right).$
(169)

Here, $H_{\mathrm{Add},I}^{L}(\tau)$ denotes the interaction Hamiltonian
described by

$\displaystyle H_{\mathrm{Add},I}^{L}(\tau)$ $\displaystyle=$ $\displaystyle
e^{\tau H_{\mathrm{LP}}^{L}}H_{\mathrm{Add}}^{L}e^{-\tau H_{\mathrm{LP}}^{L}}$
$\displaystyle=$ $\displaystyle\sum_{|m|\leq
M}\sum_{l\in[L];l+m\in[L]}\ket{l+m}\bra{l}_{f}\otimes e^{m\omega\tau}H_{m}.$

and its norm is bounded by

$\displaystyle\norm{H_{\mathrm{Add},I}^{L}(\tau)}$ $\displaystyle\leq$
$\displaystyle\sum_{|m|\leq M}e^{m\omega\tau}\alpha$ (171) $\displaystyle=$
$\displaystyle\frac{\sinh(2M+1)\omega\tau/2}{\sinh(\omega\tau/2)}\alpha$
$\displaystyle\leq$ $\displaystyle(2M+1)\alpha\sinh 1,$

for $\tau\in[0,2/\\{(2M+1)\omega\\}]$. Finally, by setting
$\lambda=1/\\{(2M+1)\omega\\}$, we get the bound,

$\norm{\braket{l}{e^{2\lambda
H_{\mathrm{F}}^{L}}}{l}_{f}}\leq\exp\left(\frac{-2l\omega+2(2M+1)\alpha\sinh
1}{(2M+1)\omega}\right),$ (172)

and combining this inequality with Eq. (166) immediately implies the upper
bound, Eq. (165). We get the same statement for a negative integer $l$ by
inserting $e^{-\lambda H_{\mathrm{F}}^{L}}e^{\lambda H_{\mathrm{F}}^{L}}$
instead of $e^{\lambda H_{\mathrm{F}}^{L}}e^{-\lambda H_{\mathrm{F}}^{L}}$ in
Eq. (166). $\quad\square$

For a single eigenstate $\ket{\tilde{\Phi}_{n}^{L}}$, this proposition gives
the inequality for $\ket{\tilde{\phi}_{n}^{l,L}}=(\bra{l}_{f}\otimes
I)\ket{\tilde{\Phi}_{n}^{L}}$,

$\norm{\ket{\tilde{\phi}_{n}^{l,L}}}\leq\exp\left(-\frac{|l|-\tilde{\epsilon}_{n}^{L}/\omega}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right),$ (173)

which gives rise to the exponential decay. Although we would like to prove a
similar statement for the Floquet Hamiltonian $H_{\mathrm{F}}$, we note that
the truncation is essential in the above proof. In Eq. (166), we insert the
exponential functions $e^{\pm\lambda H_{\mathrm{F}}^{L}}$, and they are well
defined only when the exponent is bounded. To extend this result to the
Floquet eigenstates, we next show that the eigenspace of the truncated Floquet
Hamiltonian approximates the exact one as follows. We also prove Theorem 3
following to this.

######  Proposition A2.

(Relation of eigenspaces)

For every Floquet eigenstate $\ket{\Phi_{n}}$ having quasinergy
$\epsilon_{n}\in\mathrm{BZ}$,

$\lim_{L\to\infty}(1-\tilde{P}^{L}(\mathrm{BZ}^{\varepsilon}))\ket{\Phi_{n}}=0,$
(174)

is satisfied for arbitrary $\varepsilon>0$, where $\mathrm{BZ}^{\varepsilon}$
is defined by

$\mathrm{BZ}^{\varepsilon}=[-(1/2+\varepsilon)\omega,(1/2+\varepsilon)\omega).$
(175)

Proof of Proposition A2.— From the definition of the projection, Eq. (164),
the norm is represented by

$\norm{(1-\tilde{P}^{L}(\mathrm{BZ}^{\varepsilon}))\ket{\Phi_{n}}}=\sqrt{\sum_{n^{\prime}:\epsilon_{n^{\prime}}\notin\mathrm{BZ}^{\varepsilon}}|\braket{\tilde{\Phi}_{n^{\prime}}^{L}}{\Phi_{n}}|^{2}}.$
(176)

We evaluate an upper bound on each inner product
$|\braket{\tilde{\Phi}_{n^{\prime}}^{L}}{\Phi_{n}}|$. Plugging the truncated
Floquet Hamiltonian into it, we obtain

$\displaystyle|\braket{\tilde{\Phi}_{n^{\prime}}^{L}}{\Phi_{n}}|$
$\displaystyle\leq$
$\displaystyle\frac{|\braket{\tilde{\Phi}_{n^{\prime}}^{L}}{H_{\mathrm{F}}^{L}}{\Phi_{n}}-\epsilon_{n}\braket{\tilde{\Phi}_{n^{\prime}}^{L}}{\Phi_{n}}|}{|\tilde{\epsilon}_{n^{\prime}}^{L}-\epsilon_{n}|}$
(177) $\displaystyle\leq$
$\displaystyle\frac{\norm{(H_{\mathrm{F}}^{L}-\epsilon_{n})\ket{\Phi_{n}}}}{\varepsilon\omega},$

where $\tilde{\epsilon}_{n^{\prime}}^{L}\in\mathrm{BZ}^{\varepsilon}$ denotes
an eigenvalue corresponding to $\ket{\tilde{\Phi}_{n^{\prime}}^{L}}$. The
denominator can be evaluated by

$\displaystyle(H_{\mathrm{F}}^{L}-\epsilon_{n})\ket{\Phi_{n}}$
$\displaystyle=\sum_{m}\sum_{\begin{subarray}{c}l\in[L]\\\
;l+m\in[L]\end{subarray}}\ket{l+m}_{f}H_{m}\ket{\phi_{n}^{l}}-\sum_{l\in[L]}(\epsilon_{n}+l\omega)\ket{l}_{f}\ket{\phi_{n}^{l}}$
$\displaystyle=\sum_{l\in[L]}\ket{l}_{f}\left(\sum_{m}H_{m}\ket{\phi_{n}^{l-m}}-(\epsilon_{n}+l\omega)\ket{\phi_{n}^{l}}\right)$
$\displaystyle\qquad+\sum_{|m|\leq M}\left(\sum_{\begin{subarray}{c}l\in[L]\\\
;l+m\in[L]\end{subarray}}-\sum_{l\in-m+[L]}\right)\ket{l+m}_{f}H_{m}\ket{\phi_{n}^{l}}.$
(178)

The first term is exactly zero due to the eigenvalue equation, Eq. (9), for
Floquet eigenstates. In the second term, we use integration by part based on
the analyticity of $\ket{\phi_{n}(t)}$, which implies

$\displaystyle\norm{\ket{\phi_{n}^{l}}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{(|l|\omega)^{2}}\max_{t\in[0,T]}\left(\norm{\derivative[2]{t}\ket{\phi_{n}(t)}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{((2M+1)\alpha+\omega/2)^{2}+M(2M+1)\omega\alpha}{(|l|\omega)^{2}}.$

In the second inequality, we use
$\ket{\phi_{n}(t)}=e^{i\epsilon_{n}t}U(t;0)\ket{\phi_{n}(0)}$ and the
relations, $\norm{H(t)}\leq(2M+1)\alpha$, $\norm{H^{\prime}(t)}\leq
M(2M+1)\omega\alpha$, and $\epsilon_{n}\in\mathrm{BZ}$. As a result, we arrive
at the inequality,

$\displaystyle\norm{(H_{\mathrm{F}}^{L}-\epsilon_{n})\ket{\Phi_{n}}}$
$\displaystyle\leq$ $\displaystyle\sum_{|m|\leq M}\sum_{|l|\geq
L-M}\norm{H_{m}\ket{\phi_{n}^{l}}}$ (180) $\displaystyle\leq$
$\displaystyle\mathrm{Const.}\times\sum_{l=L-M}^{\infty}l^{-2}$
$\displaystyle\leq$ $\displaystyle\frac{\mathrm{Const.}}{L-M}.$

In the above, the constant does not depend on the cutoff $L$, but includes
$M$, $\alpha$, and $\omega$. Combining this with Eqs. (176) and (177), we
finally obtain the following relation,

$\displaystyle\norm{(1-\tilde{P}^{L}(\mathrm{BZ}^{\varepsilon}))\ket{\Phi_{n}}}$
$\displaystyle\leq$
$\displaystyle\frac{\mathrm{Const.}}{\varepsilon}\sqrt{\frac{2L\cdot\mathrm{dim}(\mathcal{H})}{(L-M)^{2}}}$
(181) $\displaystyle\begin{subarray}{c}\to\\\ L\to\infty\end{subarray}$
$\displaystyle 0,$

where the coefficient in the first line comes from the dimension of the
truncated Sambe space. This completes the proof of Proposition A2.
$\quad\square$

Proof of Theorem 3.— For an eigenstate in the Sambe space $\ket{\Phi_{n}}$,
corresponding to a Floquet eigenstate $\ket{\phi_{n}(t)}$, we choose a
arbitrarily large cutoff $L$ such that $l\in[L]$. Then, the norm of each
Fourier component is evaluated by

$\displaystyle\norm{\ket{\phi_{n}^{l}}}$ $\displaystyle=$
$\displaystyle\norm{P_{l}\ket{\Phi_{n}}}$ $\displaystyle\leq$
$\displaystyle\norm{\tilde{P}^{L}(\mathrm{BZ}^{\varepsilon})P_{l}}+\norm{(1-\tilde{P}^{L}(\mathrm{BZ}^{\varepsilon}))P_{l}\ket{\Phi_{n}}}.$

The first term is bounded by Eq. (165) regardless of $L$ from Proposition A1.
The second term goes to zero by $L\to\infty$ from Proposition A2. As a result,
the inequality

$\norm{\ket{\phi_{n}^{l}}}\leq\exp\left(-\frac{|l|-1/2-\varepsilon}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right)$ (183)

holds for arbitrary $\varepsilon>0$, and this completes the proof of Theorem
3. $\quad\square$

##  Appendix B Approximate Floquet eigenstate from the truncated Sambe space

In Section IV, we show that the state
$\ket{\tilde{\Phi}_{n}^{L}}\in\mathcal{H}^{L}$, an eigenstate of the truncated
Floquet Hamiltonian $H_{\mathrm{F}}^{L}$, becomes an approximate eigenstate of
the Floquet Hamiltonian $H_{\mathrm{F}}$ by Proposition 5. Namely, the
truncated Sambe space provides an accurate estimate for each Floquet
eigenstate on the Sambe space, $\ket{\Phi_{n}}\in\mathcal{H}^{\infty}$. Here,
we prove that it also gives an accurate estimate on each Floquet eigenstate on
the physical space, $\ket{\phi_{n}(t)}$.

Let $\tilde{\epsilon}_{n}^{L}$ be an eigenvalue of $H_{\mathrm{F}}^{L}$ for
the eigenstate $\ket{\tilde{\Phi}_{n}^{L}}\in\mathcal{H}^{L}$. From the exact
relation between $\ket{\phi_{n}(t)}$ and $\ket{\Phi_{n}}$ shown in Eqs. (5)
and (8), the Floquet eigenstate in the physical space is expected to be
reproduced by

$\ket{\tilde{\phi}_{n}^{L}(t)}\equiv
e^{i\tilde{\epsilon}_{n}^{L}t}U(t;0)\sum_{l\in[L]}(\bra{l}_{f}\otimes
I)\ket{\tilde{\Phi}_{n}^{L}}$ (184)

Each Floquet eigenstate $\ket{\phi_{n}(t)}$ is characterized as an eigenstate
of the time-evolution operator $U(t+T;t)$ with the eigenvalue
$e^{-i\epsilon_{n}T}$. The state $\ket{\tilde{\phi}_{n}^{L}(t)}$ provides an
accurate estimate on the exact Floquet eigenstate $\ket{\phi_{n}(t)}$ in that
it becomes an approximate eigenstate of $U(t+T;t)$, as mentioned in Section
II.2. We prove this fact by the following theorem, based on the coincidence of
the cutoff $L$ for Floquet eigenstates (Theorem 2) and the Lieb-Robinson bound
in the Sambe space [Eq. (57)].

######  Proposition B1.

We define a state $\ket{\tilde{\phi}_{n}^{L}(t)}\in\mathcal{H}$ by Eq. (184)
with the eigenvalue $\tilde{\epsilon}_{n}^{L}$ and the eigenstate
$\ket{\tilde{\Phi}_{n}^{L}}$ of the truncated Floquet Hamiltonian
$H_{\mathrm{F}}^{L}$. Then, it can be an approximate eigenstate of the time-
evolution $U(t+T;t)$ with an error $\varepsilon\in(0,1)$ by

$\frac{\norm{\left(U(t+T;t)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(t)}}}{\norm{\ket{\tilde{\phi}_{n}^{L}(t)}}}\leq\varepsilon$
(185)

under the choice of the cutoff $L\in\Theta(\alpha
T+|\tilde{\epsilon}_{n}^{L}|/\omega+\log(1/\varepsilon))$.

We first focus on the case $t=0$, where the state is given by

$\ket{\tilde{\phi}_{n}^{L}(0)}=\sum_{l\in[L]}\ket{\tilde{\phi}_{n}^{l,L}},\quad\ket{\tilde{\phi}_{n}^{l,L}}\equiv(\bra{l}_{f}\otimes
I)\ket{\tilde{\Phi}_{n}^{L}},$ (186)

and show that this gives an approximate eigenstate of the Floquet operator
$U(T;0)$. Applying the Floquet operator in the Sambe space formalism by Eq.
(55) to $\ket{\tilde{\phi}_{n}^{L}(0)}$, the numerator of Eq. (185) can be
transformed into

$\displaystyle
U(T;0)\ket{\tilde{\phi}_{n}^{L}(0)}-e^{-i\tilde{\epsilon}_{n}^{L}T}\ket{\tilde{\phi}_{n}^{L}(0)}$
$\displaystyle\quad=\sum_{l\in\mathbb{Z}}\sum_{l^{\prime}\in[L]}\bra{l}\left(e^{-iH_{\mathrm{F}}T}-e^{-iH_{\mathrm{F}}^{L}T}\right)\ket{l^{\prime}}_{f}\ket{\tilde{\phi}_{n}^{l^{\prime},L}}.$
(187)

Before going to the proof of Proposition B1, we provide two propositions: One
is about the numerator associated with the Lieb-Robinson bound (Proposition
B2), and the other is about the denominator, i.e., the norm of
$\ket{\tilde{\phi_{n}^{L}}(0)}$ (Proposition B3). The first proposition says
that each amplitude
$\bra{l}\left(e^{-iH_{\mathrm{F}}T}-e^{-iH_{\mathrm{F}}^{L}T}\right)\ket{l^{\prime}}_{f}$
in Eq. (185) is exponentially suppressed in the distance between $l$ and
$l^{\prime}$.

######  Proposition B2.

Consider a time-periodic Hamiltonian $H(t)$, satisfying Eq. (27). For a
Fourier index $l^{\prime}\in[L]$, the inequality

$\norm{\braket{l}{(e^{-iH_{\mathrm{F}}t}-e^{-iH_{\mathrm{F}}^{L}t})}{l^{\prime}}_{f}}\leq
2e^{(2M+1)e\alpha t-d(l,l^{\prime})/M}$ (188)

is satisfied, where $d(l,l^{\prime})$ is defined by

$d(l,l^{\prime})=\begin{cases}2L-|l|-|l^{\prime}|&(l\in[L])\\\
|l|-|l^{\prime}|&(l\notin[L]).\end{cases}$ (189)

Proof of Proposition B2.— We use an interaction picture based on
$H_{\mathrm{LP}}=\sum_{l\in\mathbb{Z}}l\omega\ket{l}\bra{l}_{f}\otimes I$.
Using the Dyson series expansion under the interaction Hamiltonian
$H_{\mathrm{Add},I}(t)=\sum_{|m|\leq
M}\sum_{l\in\mathbb{Z}}\ket{l+m}\bra{l}_{f}\otimes e^{im\omega t}H_{m}$,

$U_{\mathrm{Add},I}(t)=\sum_{n=0}^{\infty}\int_{0}^{t}\differential
t_{1}\ldots\int_{0}^{t_{n-1}}\differential
t_{n}\prod_{i=1}^{n}H_{\mathrm{Add},I}(t_{i})$ (190)

and that for the truncated Floquet Hamiltonian, we get the relation,

$(\text{l.h.s of Eq.
(\ref{A_Eq:Lieb_Robinson_difference})})=\norm{\braket{l}{U_{\mathrm{Add},I}(t)-U_{\mathrm{Add},I}^{L}(t)}{l^{\prime}}_{f}}.$
(191)

By plugging the completeness
$\sum_{l_{i}\in\mathbb{Z}}\ket{l_{i}}\bra{l_{i}}_{f}\otimes I$ into the Dyson
series for $i=1,2,\ldots,n-1$, each term of the right-hand side represents the
transition amplitude via the path $l^{\prime}\equiv l_{n}\to
l_{n-1}\to\ldots\to l_{1}\to l_{0}\equiv l$ as

$\displaystyle\braket{l}{U_{\mathrm{Add},I}(t)}{l^{\prime}}_{f}$
$\displaystyle\quad=\sum_{n=0}^{\infty}\int_{0}^{t}\differential
t_{1}\ldots\int_{0}^{t_{n-1}}\differential
t_{n}\prod_{i=1}^{n}\bra{l_{i-1}}H_{\mathrm{Add},I}(t_{i})\ket{l_{i}}_{f}.$

Each transition $l_{i}\to l_{i-1}$ is allowed only when $|l_{i}-l_{i-1}|\leq
M$ is satisfied due to the assumption. The difference from the truncated one
appears when the path goes across the region $\mathbb{Z}\backslash[L]$, i.e.,
low order terms with $n<d(l,l^{\prime})$ in the Dyson series vanish.
Considering the bound on the interaction Hamiltonian
$\norm{H_{\mathrm{Add},I}(t)}\leq\max_{t\in[0,T]}\norm{H(t)}\leq(2M+1)\alpha$
and that for the truncated one [28], we arrive at the inequality,

$\displaystyle(\text{l.h.s of Eq. (\ref{A_Eq:Lieb_Robinson_difference})})$
$\displaystyle\leq$ $\displaystyle 2\sum_{n=\lceil
d(l,l^{\prime})/M\rceil}^{\infty}\frac{t^{n}}{n!}((2M+1)\alpha)^{n}$
$\displaystyle\leq$ $\displaystyle 2\exp\left((2M+1)e\alpha
t-\frac{d(l,l^{\prime})}{M}\right).$

In the last line, we use the relation $\sum_{n=n_{0}}^{\infty}(x/n)^{n}\leq
e^{ex-n_{0}}$ for arbitrary $x\geq 0$. $\quad\square$

We substitute $t=T$ in the above proposition to evaluate the numerator of Eq.
(185) later. Note that this bound comes from the Lieb-Robinson bound in the
Sambe space [28], i.e., the decay of the propagation in Fourier indices.
Indeed, when the distance $d(l,l^{\prime})$ is greater than
$L_{\mathrm{LR}}\in\Theta(\alpha t+\log(1/\varepsilon))$, the transition
amplitude becomes smaller than $\varepsilon$. Next, we prove the second
proposition, which provides the norm of the state
$\ket{\tilde{\phi}_{n}^{L}(t)}$ in the denominator of Eq. (185).

######  Proposition B3.

The state
$\ket{\tilde{\phi}_{n}^{L}(0)}=\sum_{l\in[L]}\ket{\tilde{\phi}_{n}^{l,L}}$ is
approximately normalized in the sense that

$1-\varepsilon_{\mathrm{norm}}^{L}\leq\norm{\ket{\tilde{\phi}_{n}^{L}(0)}}\leq
1+\varepsilon_{\mathrm{norm}}^{L}$ (194)

is satisfied. Here, the value $\varepsilon_{\mathrm{norm}}^{L}$ is defined by

$\displaystyle\varepsilon_{\mathrm{norm}}^{L}$ $\displaystyle=$ $\displaystyle
6(2M+1)^{2}\alpha T\log(2eL)$ (195)
$\displaystyle\times\exp\left(-\frac{L-|\tilde{\epsilon}_{n}^{L}|/\omega}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right),$

whose scaling is $e^{-\Theta(L-|\tilde{\epsilon}_{n}^{L}|/\omega-\alpha T)}$.

Proof of Proposition B3.— As we define the equivalent Floquet eigenstate under
translation by $\ket{\Phi_{n}^{l}}=\mathrm{Add}_{l}\ket{\Phi_{n}}$ [See Eq.
(15)], we organize its approximate counterpart by

$\ket{\tilde{\Phi}_{n}^{l,L}}=\mathrm{Add}_{l}\ket{\tilde{\Phi}_{n}^{L}}=\sum_{l^{\prime}\in[L]}\ket{l^{\prime}+l}_{f}\ket{\tilde{\phi}_{n}^{l^{\prime},L}}.$
(196)

Then, the norm of the state $\ket{\tilde{\phi}_{n}^{L}(0)}$ is evaluated by

$\displaystyle\braket{\tilde{\phi}_{n}^{L}(0)}{\tilde{\phi}_{n}^{L}(0)}$
$\displaystyle=$
$\displaystyle\sum_{k,l\in\mathbb{Z}}\braket{\tilde{\Phi}_{n}^{L}}{(\ket{k}\bra{l}_{f}\otimes
I)}{\tilde{\Phi}_{n}^{L}}$ (197) $\displaystyle=$
$\displaystyle\sum_{k,l\in\mathbb{Z}}\braket{\tilde{\Phi}_{n}^{L}}{P_{k}\mathrm{Add}_{k-l}}{\tilde{\Phi}_{n}^{L}}$
$\displaystyle=$ $\displaystyle
1+\sum_{l\in\mathbb{Z}\backslash\\{0\\}}\braket{\tilde{\Phi}_{n}^{L}}{\tilde{\Phi}_{n}^{l,L}}.$

We derive the approximate orthogonality of $\ket{\tilde{\Phi}_{n}^{L}}$ and
$\ket{\tilde{\Phi}_{n}^{l,L}}$ for $l\neq 0$ based on the fact that they are
approximate eigenvectors of $H_{\mathrm{F}}$ with different eigenvalues. As
discussed in Proposition 5, the error
$\norm{(H_{F}-\tilde{\epsilon}_{n}^{L})\ket{\tilde{\Phi}_{n}^{L}}}$ is
suppressed up to $e^{-\Theta(L-|\tilde{\epsilon}_{n}^{L}|/\omega-\alpha T)}$
by Eq. (52). In addition, the translation symmetry of the Floquet Hamiltonian,
$\mathrm{Add}_{l}^{\dagger}H_{\mathrm{F}}\mathrm{Add}_{l}=H_{\mathrm{F}}-l\omega$,
implies the relation,

$\norm{(H_{F}-\tilde{\epsilon}_{n}^{L}+l\omega)\ket{\tilde{\Phi}_{n}^{L,l}}}=\norm{(H_{\mathrm{F}}-\tilde{\epsilon}_{n}^{L})\ket{\tilde{\Phi}_{n}^{L}}},$
(198)

which gives the same upper bound as Eq. (52). The inner products appearing in
Eq. (197) can be evaluated by

$\displaystyle|\braket{\tilde{\Phi}_{n}^{L}}{\tilde{\Phi}_{n}^{l,L}}|$
$\displaystyle=$
$\displaystyle\frac{\left|\braket{\tilde{\Phi}_{n}^{L}}{(\tilde{\epsilon}_{n}^{L}-l\omega-\tilde{\epsilon}_{n}^{L})}{\tilde{\Phi}_{n}^{l,L}}\right|}{|l|\omega}$
(199) $\displaystyle\leq$
$\displaystyle\frac{\norm{(H_{\mathrm{F}}-\tilde{\epsilon}_{n}^{L})\ket{\tilde{\Phi}_{n}^{L}}}}{|l|\omega},$

for $l\in[2L]\backslash\\{0\\}$. We note
$\braket{\tilde{\Phi}_{n}^{L}}{\tilde{\Phi}_{n}^{l,L}}=0$ for
$l\in\mathbb{Z}\backslash[2L]$ by definition. Using the inequality
$\sum_{l=1}^{2L}l^{-1}\leq 1+\log(2L)$, we arrive at the inequality,

$\displaystyle\left|1-\norm{\ket{\tilde{\phi}_{n}(0)}}^{2}\right|$
$\displaystyle\leq$ $\displaystyle
2\log(2eL)\times\frac{\norm{(H_{\mathrm{F}}-\tilde{\epsilon}_{n}^{L})\ket{\tilde{\Phi}_{n}^{L}}}}{\omega}$
$\displaystyle=$ $\displaystyle 6(2M+1)^{2}\alpha T\log(2eL)$
$\displaystyle\times\exp\left(-\frac{L-|\tilde{\epsilon}_{n}^{L}|/\omega}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right).$

This immediately implies the relation of Eqs. (194) and (195). $\quad\square$

Now, we are ready for proving Proposition B1. We go back to showing that the
state $\ket{\tilde{\phi}_{n}^{L}(0)}$ organized by the truncated Sambe space
appropriately provides an approximate eigenstate of the Floquet operator
$U(T;0)$. The proof for generic $t\in\mathbb{R}$ follows it.

Proof of Proposition B1.— Beginning with Eq. (187), we evaluate the bound on
its norm given by

$\displaystyle\norm{\left(U(T;0)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(0)}}$
$\displaystyle\quad\leq\sum_{l\in\mathbb{Z}}\sum_{l^{\prime}\in[L]}\norm{\bra{l}\left(e^{-iH_{\mathrm{F}}T}-e^{-iH_{\mathrm{F}}^{L}T}\right)\ket{l^{\prime}}_{f}}\cdot\norm{\ket{\tilde{\phi}_{n}^{l^{\prime},L}}}.$

Let us first focus on the summation over $l\in[L]$ in the above. The bound
from Proposition B2 and the one for the state $\ket{\tilde{\phi}_{n}^{l,L}}$
by Eq. (173) indicates the inequality

$\displaystyle\sum_{l\in[L]}\sum_{l^{\prime}\in[L]}\norm{\bra{l}\left(e^{-iH_{\mathrm{F}}T}-e^{-iH_{\mathrm{F}}^{L}T}\right)\ket{l^{\prime}}_{f}}\cdot\norm{\ket{\tilde{\phi}_{n}^{l^{\prime},L}}}$
$\displaystyle\quad\leq 8\sum_{l,l^{\prime}=0}^{L}\exp\left((2M+1)e\alpha
T-\frac{2L-l-l^{\prime}}{M}\right)$
$\displaystyle\qquad\qquad\qquad\times\exp\left(-\frac{l^{\prime}-|\tilde{\epsilon}_{n}^{L}|/\omega}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right)$ $\displaystyle\quad\leq
16(2M+1)^{2}\exp\left(-\frac{L-|\tilde{\epsilon}_{n}^{L}|/\omega}{2M+1}+2(M+1)e\alpha
T\right).$ (202)

The sum over $l\in\mathbb{Z}\backslash[L]$ in Eq. (187) is evaluated in a
similar way, and results in the same form as Eq. (202). Therefore,
$\ket{\tilde{\phi}_{n}^{L}(0)}$ is an approximate eigenstate of $U(T;0)$ in a
sense that

$\displaystyle\norm{\left(U(T;0)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(0)}}$
$\displaystyle\quad\leq
32(2M+1)^{2}\exp\left(-\frac{L-|\tilde{\epsilon}_{n}^{L}|/\omega}{2M+1}+2(M+1)e\alpha
T\right)$

holds. The right hand side scales as
$e^{-\Theta(L-|\tilde{\epsilon}_{n}^{L}/\omega|-\alpha T)}$. Since the norm of
$\ket{\tilde{\phi}_{n}^{L}(0)}$ scales as
$\norm{\ket{\tilde{\phi}_{n}^{L}(0)}}=1+e^{-\Theta(L-|\tilde{\epsilon}_{n}^{L}|/\omega-\alpha
T)}$ by Proposition B3, we can achieve

$\frac{\norm{\left(U(T;0)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(0)}}}{\norm{\ket{\tilde{\phi}_{n}^{L}(0)}}}\leq\varepsilon$
(204)

under the choice of the cutoff $L\in\Theta(\alpha
T+|\tilde{\epsilon}_{n}^{L}|/\omega+\log(1/\varepsilon))$. This completes the
proof of Proposition B1 for $t=0$.

Proposition B1 for generic time $t\in[0,T)$ is easily proved by the result for
$t=0$. The state $\ket{\tilde{\phi}_{n}^{L}(t)}$ organized from the truncated
Sambe space by Eq. (184) is related to $\ket{\tilde{\phi}_{n}^{L}(0)}$ by
$\ket{\tilde{\phi}_{n}^{L}(t)}=e^{i\tilde{\epsilon}_{n}^{L}t}U(t;0)\ket{\tilde{\phi}_{n}^{L}(0)}$.
Using the relation $U(t+T;t)U(t;0)=U(t;0)U(T;0)$, which is valid for a time-
periodic Hamiltonian $H(t)$, the equality

$\displaystyle\norm{\left(U(t+T;t)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(t)}}$
$\displaystyle\qquad\qquad\quad=\norm{\left(U(T;0)-e^{-i\tilde{\epsilon}_{n}^{L}T}\right)\ket{\tilde{\phi}_{n}^{L}(0)}}$
(205)

is derived. The approximate normalization of $\ket{\tilde{\phi}_{n}^{L}(t)}$
follows immediately from
$\norm{\ket{\tilde{\phi}_{n}^{L}(t)}}=\norm{\ket{\tilde{\phi}_{n}^{L}(0)}}$.
Thus, the bound on Eq. (185) for generic time $t$ is exactly the same as the
case of $t=0$. $\quad\square$

##  Appendix C Block-encoding of Floquet Hamiltonian

In the Sambe space formalism, we often use the truncated Floquet Hamiltonian
$H_{\mathrm{F}}^{L}$ defined by

$H_{\mathrm{F}}^{L}=\sum_{|m|\leq
M}\sum_{l\in[L];l+m\in[L]}\ket{l+m}\bra{l}_{f}-\sum_{l\in[L]}l\omega\ket{l}\bra{l}_{f}\otimes
I,$ (206)

and the main text follows this definition. However, for block-encoding toward
QSVT, another truncated Floquet Hamiltonian $H_{\mathrm{F,pbc}}^{L}$ by

$\displaystyle H_{\mathrm{F,pbc}}^{L}$ $\displaystyle=$
$\displaystyle\sum_{|m|\leq M}\mathrm{Add}_{m}^{[L]}\otimes
H_{m}-\sum_{l\in[L]}l\omega\ket{l}\bra{l}_{f}\otimes I,$
$\displaystyle\mathrm{Add}_{m}^{[L]}$ $\displaystyle=$
$\displaystyle\sum_{l\in[L]}\ket{(l\oplus m)_{[L]}}\bra{l}_{f},$ (208)

is rather feasible, as shown in Section V.2. Here, we provide an efficient
block-encoding of $H_{\mathrm{F,pbc}}^{L}$, and prove that using either
$H_{\mathrm{F}}^{L}$ or $H_{\mathrm{F,pbc}}^{L}$ results in the same
eigenvalues and eigenstates with negligible errors. Namely, the discussion
based on $H_{\mathrm{F}}^{L}$ in the main text is valid, while the actual
quantum algorithms run with queries to block-encoding of
$H_{\mathrm{F,pbc}}^{L}$ by $C[O_{H_{m}}]$.

###  C.1 Block-encoding under periodic boundary conditions

We briefly review the block-encoding of $H_{\mathrm{F,pbc}}^{L}$ in Ref. [28],
and how Proposition 6 in the main text is confirmed. The block-encoding
unitaries for the first and the second terms in Eq. (LABEL:A_Eq:modified_H_F)
are constructed separately and their combination forms the one for
$H_{\mathrm{F,pbc}}^{L}$. Preparing a $\order{1}$-ancilla qubits expressed by
$\\{\ket{m}_{M}\\}_{|m|\leq M}$, the block-encoding of the first term $O_{1}$
is provided by

$\displaystyle O_{1}=G_{M}^{\dagger}\left(\sum_{|m|\leq
M}\ket{m}\bra{m}\otimes\mathrm{Add}_{m}^{[L]}\otimes O_{H_{m}}\right)G_{M},$

with a unitary gate $G_{M}$ on this anclla system such that

$G_{M}\ket{0}_{M}=\sum_{|m|\leq
M}\sqrt{\frac{\alpha_{m}}{\sum_{|m^{\prime}|\leq
M}\alpha_{m^{\prime}}}}\ket{m}_{M}.$ (210)

The block-encoding $O_{1}$ embeds the first term of Eq.
(LABEL:A_Eq:modified_H_F),

$(\bra{0}_{M}\bra{0}_{a})O_{1}(\ket{0}_{M}\ket{0}_{a})=\frac{\sum_{|m|\leq
M}\mathrm{Add}_{l}^{[L]}\otimes H_{m}}{\sum_{|m|\leq M}\alpha_{m}},$ (211)

requiring one query respectively for $C[O_{H_{m}}]$ and at most $\order{\log
L}$ primitive gates. The second term of Eq. (LABEL:A_Eq:modified_H_F) has a
block-encoding $O_{2}$ such that

$\braket{0}{O_{2}}{0}_{f^{\prime}}=\frac{-\sum_{l\in[L]}l\omega\ket{l}\bra{l}_{f}\otimes
I}{L\omega},$ (212)

with a $\Theta(\log L)$ ancilla qubit system $f^{\prime}$, where we use only
$\Theta(\log L)$ primitive gates [28].

The block-encoding of $H_{\mathrm{F,pbc}}^{L}$ is organized one query
respectively to $O_{1}$ and $O_{2}$. Introducing additional two qubits $c$, it
is defined by

$\displaystyle O_{H_{\mathrm{F,pbc}}^{L}}$ $\displaystyle=$ $\displaystyle
G_{c}^{\dagger}\biggl{(}\ket{00}\bra{00}_{c}\otimes
O_{1}+\ket{01}\bra{01}\otimes O_{2}\biggr{.}$
$\displaystyle\qquad+(\ket{10}\bra{11}+\ket{11}\bra{10})_{c}\otimes
I\biggl{.}\biggr{)}G_{c},$ $\displaystyle G_{c}\ket{00}_{c}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{\sum_{|m|\leq
M}\alpha_{m}}{\tilde{\alpha}}}\ket{00}_{c}+\sqrt{\frac{L\omega}{\tilde{\alpha}}}\ket{00}_{c}$
(214) $\displaystyle\quad+\sqrt{\frac{\tilde{\alpha}-\sum_{|m|\leq
M}\alpha_{m}-L\omega}{\tilde{\alpha}}}\ket{10}_{c},$

where some identity matrices are omitted. The above block-encoding is well-
defined for arbitrary $\tilde{\alpha}\geq(2M+1)\alpha+L\omega$, which is
ensured to be larger than $\sum_{|m|\leq M}\alpha_{m}+L\omega$. By summarizing
the ancilla system $a$ and the additional $\order{\log L}$ qubits as
$a^{\prime}$, this embeds the truncated Floquet Hamiltonian
$H_{\mathrm{F,pbc}}^{L}$ with the denominator $\tilde{\alpha}$ as Proposition
6. Therefore, QSVT algorithms working with the query complexity $q$ in
$O_{H_{\mathrm{F,pbc}}^{L}}$ (e.g., the standard QPE based on the truncated
Floquet Hamiltonians in the main text) can be executed by
$\order{qM}=\order{q}$ queries to $C[O_{H_{m}}]$.

###  C.2 Equivalence between different boundary conditions

Here, we show the equivalence of the quantum algorithms working with
$H_{\mathrm{F}}^{L}$ and $H_{\mathrm{F,pbc}}^{L}$. In Section VII, we apply
the QPE under the Hamiltonian $H_{\mathrm{F}}^{pL}$ to the input state
$\ket{\Psi_{0}^{L}}$, Eq. (88). The input state is approximately a
superposition of Floquet eigenstates $\ket{\Phi_{n}^{l}}$ for $l\in[6L]$
according to Eqs. (110) and (111) based on Proposition 10. The calculation
relies solely on the facts that each $\ket{\Phi_{n}^{l}}$ is an approximate
eigenstate of $H_{\mathrm{F}}^{L}$ satisfying
$\norm{(H_{\mathrm{F}}^{L}-(\epsilon_{n}-l\omega))\ket{\Phi_{n}^{l}}}\leq
e^{-\Theta(L-\alpha T)}$ by Theorem 2 and that it causes only a small error in
the QPE result $\delta_{\mathrm{approx}}$ like Eq. (115) as shown by
Proposition D1. To prove the equivalence, it is sufficient to show the former
fact for the alternative Floquet Hamiltonian $H_{\mathrm{F,pbc}}^{pL}$ as
follows.

######  Proposition C1.

Let $\ket{\Phi_{n}^{l}}\in\mathcal{H}^{\infty}$ be a Floquet eigenstate such
that
$H_{\mathrm{F}}\ket{\Phi_{n}^{l}}=(\epsilon_{n}-l\omega)\ket{\Phi_{n}^{l}}$.
It is an approximate eigenstate of the truncated Floquet Hamiltonian
$H_{\mathrm{F,pbc}}^{L}$ by

$\displaystyle\norm{(H_{\mathrm{F,pbc}}^{L}-(\epsilon_{n}-l\omega))\ket{\Phi_{n}^{l}}}$
$\displaystyle\quad\leq 54(2M+1)^{2}\exp\left(-\frac{L-|l|}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right)$ $\displaystyle\quad\leq e^{-\Theta(L-\alpha T)},$
(215)

where $H_{\mathrm{F,pbc}}^{L}$ is defined by Eq. (LABEL:A_Eq:modified_H_F),

Proof of Proposition C1.— The proof is completely parallel to the proof for
$H_{\mathrm{F}}^{L}$, which is shown as Proposition 4 in the main text.
Setting $l=0$ for simplicity, we obtain the relation,

$\displaystyle(H_{\mathrm{F,pbc}}^{L}-\epsilon_{n})\ket{\Phi_{n}}$
$\displaystyle\quad=\sum_{l^{\prime}\in[L]}\ket{l^{\prime}}_{f}\left(\sum_{|m|\leq
M}H_{m}\ket{\phi_{n}^{(l^{\prime}\ominus
m)_{[L]}}}-(\epsilon_{n}+l^{\prime}\omega)\ket{\phi_{n}^{l^{\prime}}}\right)$
$\displaystyle\quad=\sum_{l^{\prime}\in[L]}\ket{l^{\prime}}_{f}\left(\sum_{|m|\leq
M}H_{m}\ket{\phi_{n}^{l^{\prime}-m}}-(\epsilon_{n}+l^{\prime}\omega)\ket{\phi_{n}^{l^{\prime}}}\right)$
$\displaystyle\qquad\quad+\sum_{l^{\prime}\in[L]}\ket{l^{\prime}}_{f}\sum_{|m|\leq
M}H_{m}\left(\ket{\phi_{n}^{(l^{\prime}\ominus
m)_{[L]}}}-\ket{\phi_{n}^{l^{\prime}-m}}\right).$

The symbol $(l\ominus m)_{[L]}=(l\oplus(-m))_{[L]}$ means $l-m$ modulo $2L$
defined on $[L]$. In the last line, the first term disappears by the
eigenvalue equation $H_{\mathrm{F}}\ket{\Phi_{n}}=\epsilon_{n}\ket{\Phi_{n}}$.
In the second term, only the contributions from $|l^{\prime}|\geq L-M$ can
survive since $(l\ominus m)_{[L]}=l-m$ is otherwise satisfied. As a result,
the norm is bounded by

$\displaystyle\norm{(H_{\mathrm{F,pbc}}^{L}-\epsilon_{n})\ket{\Phi_{n}}}$
$\displaystyle\quad\leq\sum_{|l^{\prime}|\geq L-M}\sum_{|m|\leq
M}\left(\norm{\ket{\phi_{n}^{(l^{\prime}\ominus
m)_{[L]}}}}+\norm{\ket{\phi_{n}^{l^{\prime}-m}}}\right)$
$\displaystyle\quad\leq
2(2M+1)\alpha\sum_{l^{\prime}\mathbb{Z}\backslash[L-2M]}\norm{\ket{\phi_{n}^{l^{\prime}}}}$
$\displaystyle\quad\leq 18(2M+1)^{2}\exp\left(-\frac{L-2M}{2M+1}+\frac{\sinh
1}{2\pi}\alpha T\right),$

where we use Eq. (LABEL:Eq:phi_n_l_contribute_out) in the main text for
deriving the last inequality. Using $e^{2M/(2M+1)}<3$, we arrive at the
inequality, Eq. (215), for $l=0$. The result for a generic integer
$l\in\mathbb{Z}$ is obtained similarly. $\quad\square$

In the main text, the algorithm in Section VII deals with the truncated
Hamiltonian $H_{\mathrm{F,pbc}}^{pL}$ ($p\geq 7$), and each Floquet eigenstate
$\ket{\Phi_{n}^{l}}$ for $l\in[6L]$ is involved in the initial state
$\ket{\Psi_{0}^{L}}$ as Eqs. (110) and (111). The above proposition guarantees
the relation,

$\norm{(H_{\mathrm{F,pbc}}^{pL}-(\epsilon_{n}-l\omega))\ket{\Phi_{n}^{l}}}\leq
e^{-\Theta(L-\alpha T)}.$ (218)

The standard QPE based on $H_{\mathrm{F,pbc}}^{pL}$ exactly as described in
Section VI. Combined with the efficient block-encoding of
$H_{\mathrm{F,pbc}}^{pL}$ in Section C.1, the Floquet QPE algorithms for
$(\epsilon_{n},\ket{\Phi_{n}})$ are efficiently executed by the controlled
block-encoding $C[O_{H_{m}}]$ and its inverse.

##  Appendix D QSVT for approximate eigenstates

In the QPE algorithm of Sec. VII, we use QSVT based on the truncated Floquet
Hamiltonian $H_{\mathrm{F}}^{L}$, but we apply it to a state expanded by the
set of approximate eigenstates $\\{\ket{\Phi_{n}}\\}$ as Eq. (114). Here, we
show that the influence of this deviation $\delta_{\mathrm{approx}}$ is
bounded by Eq. (115).

Let us consider a generic time-independent Hamiltonian $H$ with a spectral
decomposition $H=\sum_{n}E_{n}\ket{\phi_{n}}\bra{\phi_{n}}$. The Hamiltonian
$H$ is assumed to be renormalized as $\norm{H}\leq 1$, and thus
$E_{n}\in[-1,1]$. The QSVT based on $H$ applies a degree-$q$ polynomial
$f_{q}(H)$ to a state expanded by approximate eigenstates
$\\{\ket{\tilde{\phi}_{n}}\\}_{n}$. Denoting their approximate eigenvalues by
$\\{\tilde{E}_{n}\in[-1,1]\\}_{n}$, we examine how the QSVT based on $H$
reproduces the one based on

$\tilde{H}=\sum_{n=1}^{n_{\mathrm{max}}}\tilde{E}_{n}\ket{\tilde{\phi}_{n}}\bra{\tilde{\phi}_{n}}.$
(219)

We summarize the result be the following proposition.

######  Proposition D1.

(Approximate QSVT)

Suppose that a given state $\ket{\psi}$ is expanded by
$\ket{\psi}=\sum_{n=1}^{n_{\mathrm{max}}}c_{n}\ket{\tilde{\phi}_{n}}$
($\sum_{n}|c_{n}|^{2}=1$), where the approximate eigenstates
$\\{\ket{\tilde{\phi}_{n}}\\}_{n}$ are characterized by

$\norm{(H-\tilde{E}_{n})\ket{\tilde{\phi}_{n}}}\leq\eta,\quad^{\exists}\tilde{E}_{n}\in[-1,1],$
(220)

and
$\braket{\tilde{\phi}_{n}}{\tilde{\phi}_{n^{\prime}}}=\delta_{nn^{\prime}}$.
Then, the difference between $f_{q}(H)$ and $f_{q}(\tilde{H})$ when applied to
$\ket{\psi}$ is bounded by

$\norm{f_{q}(H)\ket{\psi}-f_{q}(\tilde{H})\ket{\psi}}\leq
q^{2}\eta\sqrt{n_{\mathrm{max}}},$ (221)

for any degree-$q$ polynomial $f_{q}$ realized by QSVT.

Proof of Proposition D1.— We first focus on the difference of Eq. (221) for
each approximate eigenstate $\ket{\psi}=\ket{\tilde{\phi}_{n}}$. Using a
degree-$(q-1)$ polynomial $g_{q-1}(x,y)$ defined by factorization
$f_{q}(x)-f_{q}(y)=(x-y)g_{q-1}(x,y)$, it is evaluated as follows;

$\displaystyle\norm{(f_{q}(H)-f_{q}(\tilde{H}))\ket{\tilde{\phi}_{n}}}$
$\displaystyle\quad=\norm{\sum_{n^{\prime}}g_{q-1}(E_{n^{\prime}},\tilde{E}_{n})(E_{n^{\prime}}-\tilde{E}_{n})\ket{\phi_{n^{\prime}}}\braket{\phi_{n^{\prime}}}{\tilde{\phi}_{n}}}$
$\displaystyle\quad\leq\max_{x\in[-1,1]}(|g_{q-1}(x,\tilde{E}_{n})|)\norm{(H-\tilde{E}_{n})\ket{\tilde{\phi}_{n}}}.$
(222)

The mean value theorem gives an upper bound on $g_{q-1}$ by

$\displaystyle|g_{q-1}(x,\tilde{E}_{n})|$ $\displaystyle\leq$
$\displaystyle\sup_{x\in(-1,1)}(|f^{\prime}_{q}(x)|)\leq q^{2}.$ (223)

The second inequality follows from the fact that achievable degree-$q$
polynomials in QSVT should be renormalized as $|f_{q}(x)|\leq 1$
(${}^{\forall}x\in[-1,1]$), and then their derivatives cannot exceed $q^{2}$
by the Markov theorem [69]. Therefore, for generic state
$\ket{\psi}=\sum_{n=1}^{n_{\mathrm{max}}}c_{n}\ket{\tilde{\phi}_{n}}$, the
difference, $\norm{f_{q}(H)\ket{\psi}-f_{q}(\tilde{H})\ket{\psi}}$, has an
upper bound $\sum_{n=1}^{n_{\mathrm{max}}}|c_{n}|q^{2}\eta$. Using the
inequality $\sum_{n=1}^{n_{\mathrm{max}}}|c_{n}|\leq\sqrt{n_{\mathrm{max}}}$,
which is derived from the Cauchy-Schwartz inequality, we obtain Eq. (221).
$\quad\square$

While the above results are for QSVT for hermitian matrices, their extension
to generic matrices can be immediately obtained. In the case of QPE under the
truncated Floquet Hamiltonian in Section VII, we apply QSVT based on
$H_{\mathrm{F}}^{pL}$ or $H_{\mathrm{F,pbc}}^{pL}$ to the input state
$\ket{\Psi_{0}^{L}}$, which is a superposition of $\ket{\Phi_{n}^{l}}$ by Eqs.
(110) and (111). Then, Proposition 10 suggests that the number
$n_{\mathrm{max}}$ for the terms other than the negligible state
$\ket{\Psi_{\mathrm{neg}}^{L}}$ is bounded by

$n_{\mathrm{max}}\leq\mathrm{dim}(\mathcal{H})\times 12L,$ (224)

consisting of $\ket{\Phi_{n}^{l}}$ for
$n=1,2,\ldots,\mathrm{dim}(\mathcal{H})$ and $l\in[6L]$. The error $\eta$,
which provides the upper bound on
$\norm{(H_{\mathrm{F}}^{pL}-(\epsilon_{n}-l\omega))\ket{\Phi_{n}^{l}}}$ scales
as $e^{-\Theta(L-\alpha T)}$ by Eq. (46). This is also true for the modified
Hamiltonian $H_{\mathrm{F,pbc}}^{pL}$ as discussed in Section C. Therefore,
when the QPE based on QSVT is executed with the query complexity
$q_{\mathrm{QPE}}$, the error of regarding $\ket{\Phi_{n}^{l}}$ as the exact
eigenstate of the truncated Floquet Hamiltonians amounts to at most

$\delta_{\mathrm{approx}}\leq q_{\mathrm{QPE}}^{2}e^{-\Theta(L-\alpha T-N)},$
(225)

as shown in Eq. (115).

##  Appendix E Extension to Hamiltonian with exponentially-decaying Fourier
components

In the main text, we focus on the cases where the Fourier indices in the
Hamiltonian $H(t)$ are bounded by $|m|\leq M$ as in Eq. (27). Here, we
consider the case whose Hamiltonian is given by

$H(t)=\sum_{m=-\infty}^{\infty}H_{m}e^{-im\omega
t},\quad\norm{H_{m}}\leq\alpha e^{-|m|/\zeta},$ (226)

with positive constants $\alpha,\zeta>0$. For instance, these Hamiltonians can
describe the Gaussian wave packet of laser light [28]. Our results in the main
text, i.e. the guaranteed quasienergy from Sambe space and the quantum
algorithms for quasienergy and Floquet eigenstates, can be easily extended to
these cases.

To extend our results in the main text to this class of time-periodic
Hamiltonians, we note the points to be confirmed:

  1. (E-1)

Exponential decay of $\braket{l}{e^{-iH_{F}t}}{l^{\prime}}_{f}$ in the
distance $|l-l^{\prime}|$ (Lieb-Robinson bound)

  2. (E-2)

Exponential decay of $\ket{\phi_{n}^{l}}$ in the Fourier index $l$

  3. (E-3)

Efficient block-encoding of the truncated Floquet Hamiltonian $H_{F}^{L}$

(E-1) is required for the Floquet QPE to compute pairs of
$(\epsilon_{n},\ket{\phi_{n}(t)})$ as Section VI. According to Ref. [28], a
time-periodic Hamiltonian by Eq. (226) also possesses a bound,
$\norm{\braket{l}{e^{-iH_{F}t}}{l^{\prime}}_{f}}\leq
e^{-\Theta(|l-l^{\prime}|-\alpha T)}$. This results in the proper cutoff
$L_{\mathrm{LR}}\in\Theta(\alpha T+\log(1/\varepsilon))$ for the Sambe space
formalism of the Floquet operator $U(T;0)$. (E-2) is required for the Floquet
QPE to compute pairs of $(\epsilon_{n},\ket{\Phi_{n}})$ as Section VI. The
accuracy of quasienergy and Floquet eigenstates by the truncated Floquet
Hamiltonian $H_{\mathrm{F}}^{L}$, i.e., Theorem 2, relies solely on the
exponential decay of $\ket{\phi_{n}^{l}}$, which tells us a proper cutoff
$L\in\Theta(\alpha T+\log(1/\varepsilon))$ to achieve the allowable error
$\varepsilon$. Namely, the proof of (E-2) validates the QPE under
$H_{\mathrm{F}}^{L}$ in the Floquet QPE algorithm. Finally, (E-3) is required
for the Floquet QPE algorithm to run efficiently with designated oracles. Our
algorithms use the block-encoding of the truncated Floquet Hamiltonian for
realizing the Floquet operator $U(T;0)$ (Section VI) or for executing the QPE
(Section VII). It should be constructed efficiently by queries to some block-
encoding of the Hamiltonian to preserve the efficiency of time-independent
cases.

(E-1) and (E-3) are resolved in Ref. [28]: A time-periodic Hamiltonian $H(t)$
by Eq. (226) has the Lieb-Robinson bound on the propagation, given by

$\norm{\braket{l}{e^{-iH_{\mathrm{F}}t}}{l^{\prime}}_{f}}\leq\exp\left(-\frac{|l-l^{\prime}|}{\zeta^{\prime}}+2\zeta^{\prime\prime}\alpha
t+\frac{2}{\zeta^{\prime\prime}}\right),$ (227)

with the two constants $\zeta^{\prime}=(1/\zeta-1+e^{-1/\zeta})^{-1}$ and
$\zeta^{\prime\prime}=(1-e^{-1/\zeta})^{-1}$. For the efficient block-
encoding, we assume that the Hamiltonian $H(t)$ by Eq. (226) is written by

$H(t)=\sum_{j=1}^{J}\alpha_{j}(t)H_{j},\quad\alpha_{j}(t+T)=\alpha_{j}(t),$
(228)

and that we can organize block-encoding $O_{H_{j}}$ respectively for each
time-independent operator $H_{j}$. Then, in a similar manner to Section V.2,
we can organize the modified Floquet Hamiltonian suitable for block-encoding
by

$H_{\mathrm{F,pbc}}^{L}=\sum_{l\in[L]}\left(\sum_{j=1}^{J}\mathrm{Add}_{l}^{[L]}\otimes(\alpha_{j}^{l}H_{j})-l\omega\ket{l}\bra{l}_{f}\otimes
I\right),$ (229)

where $\alpha_{j}^{l}=T^{-1}\int_{0}^{T}\differential
t\,\alpha_{j}(t)e^{il\omega t}$ denotes the Fourier component of
$\alpha_{j}(t)$. The block-encoding of $H_{\mathrm{F,pbc}}^{L}$ can be
constructed by one query to $C[O_{H_{j}}]$ respectively for $j=1,2,\ldots,J$
and some other cheap primitive gates like Proposition 6. At the same time,
running the algorithms with $H_{\mathrm{F,pbc}}^{L}$ is essentially the same
as running with the original Floquet Hamiltonian $H_{\mathrm{F}}^{L}$ under
$L\in\Theta(\alpha T+\log(1/\varepsilon))$. The remaining task for the
extension is to prove condition (E-2). We end up with this section by showing
the counterpart of Theorem 3 as follows.

######  Theorem E1.

Let $\ket{\phi_{n}(t)}$ be a Floquet eigenstate of a time-periodic Hamiltonian
with exponentially-decaying Fourier components by Eq. (226) Then, its Fourier
component $\ket{\phi_{n}^{l}}$ exponentially decays in the Fourier index $l$
by

$\norm{\ket{\phi_{n}^{l}}}\leq\exp\left(-\frac{|l|-1/2}{4\zeta}+\frac{\coth(1/4\zeta)}{8\pi\zeta}\alpha
T\right),$ (230)

when the quasienergy $\epsilon_{n}$ belongs to
$\mathrm{BZ}=[-\omega/2,\omega/2)$.

Proof of Theorem E1.— We follow the proof of Theorem 3 in Section A. We can
prove Proposition A2 in the same way, and this part does not affect the bound
itself. The difference appears in the evaluation of
$\norm{H_{\mathrm{Add},I}^{L}(\tau)}$ in Eq. (171) as follows.

$\displaystyle\norm{H_{\mathrm{Add},I}^{L}(\tau)}$ $\displaystyle\leq$
$\displaystyle\sum_{m\in\mathbb{Z}}e^{m\omega\tau}\norm{H_{m}}$ (231)
$\displaystyle\leq$
$\displaystyle\alpha\left(2\sum_{m=0}^{\infty}e^{-m(\zeta^{-1}-\omega\tau)}-1\right),$

in Proposition A1. For $\tau\in[0,1/(2\zeta\omega)]$, this gives a bound,
$\norm{H_{\mathrm{Add},I}^{L}(\tau)}\leq\alpha\coth(1/4\zeta)$. By choosing
the parameter $\lambda=1/(4\zeta\omega)$ in Eq. (166), we arrive at Eq. (230).
$\quad\square$

Compared to Theorem 3, the characteristic scale $\zeta\in\order{1}$ plays a
role of the maximum Fourier index $M$ in a time-periodic Hamiltonian by Eq.
(27). This exponential decay implies the approximation of the quasienergy
$\epsilon_{n}$ by the eigenvalue of the truncated Floquet Hamiltonian
$H_{\mathrm{F}}^{L}$ with an error up to $e^{-\Theta(L-\alpha T)}$ as in
Theorem 2. As a consequence, all the results in the main text are valid also
for the class of Hamiltonians by Eq. (226). The cost of the Floquet QPE for
$(\epsilon_{n},\ket{\phi_{n}(t)})$ [Section VI] or
$(\epsilon_{n},\ket{\Phi_{n}})$ [Section VII] remains given by Theorem 9 and
Theorem 12 respectively. The cost of the Floquet eigenstate preparation
discussed in Section VIII is summarized by Table 2. We conclude that the
quantum algorithm for computing quasienergy and Floquet eigenstates can
achieve near optimal query complexity even for time-periodic Hamiltonians
having exponentially-decaying Fourier components. This result is reminiscent
of Hamiltonian simulation [28], in which real-time dynamics can be simulated
with nearly optimal query complexity both for time-periodic Hamiltonians with
a finite number of Fourier components and for those with exponentially-
decaying Fourier components.