\subsection{The $1s$-$2s$ transition frequency}

\begin{figure
\centering
 \includegraphics[width=1.0 \linewidth,angle=0]
   {omega-Eides-2002-2018.eps}
\caption{\footnotesize
  The $1s$-$2s$ hydrogen transition frequency.  Red point:
  $f_{1s,2s}^{\mathrm{(exp)}} = 2466061413187.035 (10)$~kHz \cite{Parthey},
  Eq.~(\ref{eq:omega_exp}).
  Purple point,
  $f_{1s,2s}^{\mathrm{(Eides,Sick)}} = ( 2466061413141 \pm 47 )$~kHz,
  Eq.~(\ref{eq:f_1s2s-Eides-Sick}).
  Blue point,
  $f_{1s,2s}^{(\mathrm{Eides)}} = ( 2466061412396 \pm 21 )$~kHz,
  see Eq.~(\ref{eq:f_1s2s-Eides}).
  Azure point,
  $\tilde{f}_{1s,2s}^{(2002)} = ( 2466061413996 \pm 23 )$~kHz,
  see Eq.~(\ref{eq:f_1s2s-2002-34}).
  Green point,
  $\tilde{f}_{1s,2s}^{(2018)} = ( 2466061413163.087 \pm 6.4 \big)$~kHz,
  see Eq.~(\ref{eq:f_1s2s-2018-34}).
  Magenta point,
  $f_{1s,2s}^{(2018,\mathrm{fit)}} = f_{1s,2s}^{\mathrm{(exp)}}$ with
  an uncertainty of 6.4 kHz.
  The discrepancies of the calculated frequencies from the measured
  frequency are as follows:
  $\Delta f_{1s,2s}^{\mathrm{(Eides,Sick)}} = -46$~kHz
  in Eq.~(\ref{eq:Delta-f_1s2s-Eides-Sick}),
  $\Delta f_{1s,2s}^{\mathrm{(Eides)}} = 2$~kHz
  in Eq.~(\ref{eq:Delta-f_1s2s-Eides}),
  $\Delta \tilde{f}_{1s,2s}^{(2002)} = 19.522$~kHz
  in Eq.~(\ref{eq:Delta-f_1s2s-2002-34}),
  $\Delta \tilde{f}_{1s,2s}^{(2018)} = -23.948$~kHz
  in Eq.~(\ref{eq:Delta-f_1s2s-2018-34}), and
  $\Delta f_{1s,2s}^{(2018,\mathrm{fit)}} = 0$.
  }
\label{Fig-Delta-omega}
\end{figure}

\textit{Transition frequency using 2002 CODATA~\cite{CODATA-2002}}:
The values of the fundamental constants used in Ref.~\cite{CODATA-2002}
are given in Eq.~(\ref{subeqs:2002-CODATA}), and the Dirac frequency
$f_{1s, 2s}^{\mathrm{(Dirac, 2002)}}$ is given in Eq.~(\ref{eq:f-Dirac-2002}).
Using the technique in Ref.~\cite{CODATA-2002} (see SM~\cite{supplementary}),
we find the following QED radiative and FNS correction $f_{1s, 2s}^{\mathrm{(QED, FNS, 2002)}}$
to the $1s$-$2s$ transition frequency:
\begin{equation}
  \label{eq:f-QED-FNS-2002}
  f_{1s, 2s}^{\mathrm{(QED, FNS, 2002)}} =
  ( -7127027.610 \pm 16 ) ~ \text{kHz}.
\end{equation}
Using Eq.~(\ref{eq:energy-ns-Dirac-recoil}) in Eq.~(\ref{eq:f=f^Dirac+f^QED-FNS}), and the proton
RMS charge radius in Eq.~(\ref{eq:proton-radius-num-2002}), we get the transition frequency
$f_{1s, 2s}^{\mathrm{(2002)}}$,
\begin{equation}
  \label{eq:f_1s2s-2002}
  f_{1s,2s}^{(2002)} =
  ( 2466061413995.950 \pm 23 ) ~ \text{kHz},
\end{equation}
and the discrepancy $\Delta f_{1s, 2s}^{(2002)} = %
f_{1s, 2s}^{(2002)} - f_{1s, 2s}^{\mathrm{(exp)}}$,
\begin{equation}
  \label{eq:Delta-f_1s2s-2002}
  \Delta f_{1s,2s}^{(2002)} = 808.915 ~ \text{kHz} .
\end{equation}
$| \Delta f_{1s, 2s}^{(2002)} |$ is much larger than the uncertainty of $f_{1s, 2s}^{(2002)}$,
$\delta f_{1s, 2s}^{(2002)} = 23$~kHz, and much larger than the uncertainty of
$f_{1s, 2s}^{\mathrm{(exp)}}$, $\delta f_{1s, 2s}^{\mathrm{(exp)}} = 0.010$~kHz.

Using Eq.~(\ref{eq:energy-ns-Dirac-recoil-34}) in Eq.~(\ref{eq:f=f^Dirac+f^QED-FNS}),
we get
\begin{equation}
  \label{eq:f_1s2s-2002-34}
  \tilde{f}_{1s,2s}^{(2002)} =
  ( 2466061413206.557 \pm 23 ) ~ \text{kHz},
\end{equation}
and the discrepancy $\Delta \tilde{f}_{1s, 2s}^{(2002)} = %
\tilde{f}_{1s, 2s}^{(2002)} - f_{1s, 2s}^{\mathrm{(exp)}}$ is
\begin{equation}
  \label{eq:Delta-f_1s2s-2002-34}
  \Delta \tilde{f}_{1s,2s}^{(2002)} = 19.522 ~ \text{kHz} .
\end{equation}
$| \Delta \tilde{f}_{1s, 2s}^{(2002)} |$ is smaller than the uncertainty of $f_{1s, 2s}^{(2002)}$,
$\delta f_{1s, 2s}^{(2002)} = 23$~kHz, but much larger than the uncertainty of
$f_{1s, 2s}^{\mathrm{(exp)}}$, $\delta f_{1s, 2s}^{\mathrm{(exp)}} = 0.010$~kHz.

\textit{Transition frequency using 2018 CODATA~\cite{proton_radius}}:
The values of the Rydberg frequency $c R_{\infty}$, the electron to proton mass ratio $\mu_{ep}$,
the electron to muon mass ratio $\mu_{e \mu}$, the fine structure constant $\alpha$,
the RMS proton radius $r_p$, and the reduced electron Compton wavelength $\lambdabar_C$, from Ref.~\cite{proton_radius} are:
\begin{subequations}   \label{subeqs:2018-CODATA}
\begin{eqnarray}
  c R_{\infty}^{(2018)} &=& 3.289 841 960 2508 (64) \times 10^{15} ~ \text{Hz},
  \label{eq:Ridberg-num-2018}
  \\
  \mu_{ep}^{(2018)} &=& 5.446 170 214 87 (33) \times 10^{-4},
  \label{eq:mu_e-num-2018}
  \\
  \mu_{e \mu}^{(2018)} &=& 4.836 331 69 (11) \times 10^{-3},
  \label{eq:m-_emu-num-2018}
  \\
  \alpha^{(2018)} &=& 7.297 352 5693 (11) \times 10^{-3},
  \label{eq:alpha-num-2018}
  \\
  r_{p}^{(2018)} &=& 0.8414 (19) \times 10^{-15} ~ \text{m},
  \label{eq:proton-radius-num-2018}
  \\
  \lambdabar_{C}^{(2018)} &=& 3.861 592 6796 (12) \times 10^{-13} \, \text{m}.
  \label{eq:Compton-num-2018}
\end{eqnarray}
\end{subequations}
Using Eq.~(\ref{eq:energy-ns-Dirac-recoil}) in Eq.~(\ref{eq:f=f^Dirac+f^QED-FNS}),
we get the Dirac frequency $f_{1s, 2s}^{\mathrm{(Dirac, 2018)}}$,
\begin{equation}    \label{eq:f-Dirac-2018}
  f^{\mathrm{(Dirac, 2018)}} = ( 2466068540913.7 \pm 4.8) ~ \text{kHz} .
\end{equation}
Using Eq.~(\ref{eq:energy-ns-Dirac-recoil-34}) in Eq.~(\ref{eq:f=f^Dirac+f^QED-FNS}), we get
\begin{equation}
  \label{eq:f-Dirac-2018-34}
  \tilde{f}^{\mathrm{(Dirac, 2018)}} =
  ( 2466068540152.921 \pm 4.8) ~ \text{kHz} .
\end{equation}
Using the technique in Ref.~\cite{proton_radius} (see the SM~\cite{supplementary}),
we find the following QED radiative and FNS correction $f_{1s, 2s}^{\mathrm{(QED, FNS, 2018)}}$
to the $1s$-$2s$ transition frequency:
\begin{equation}
  \label{eq:f-QED-FNS-2018}
  f_{1s, 2s}^{\mathrm{(QED, FNS, 2018)}} =
  ( -7126679.6 \pm 4.4 ) ~ \text{kHz}.
\end{equation}
The hydrogen $1s$-$2s$ transition frequency $f_{1s, 2s}^{(2018)}$
for the proton RMS charge radius in Eq.~(\ref{eq:proton-radius-num-2018})
and the Dirac frequency in Eq.~(\ref{eq:f-Dirac-2018}) is
\begin{equation}
  \label{eq:f_1s2s-2018}
  f_{1s,2s}^{(2018)} =
  ( 2466061413923.866 \pm 6.4 ) ~ \text{kHz},
\end{equation}
and the discrepancy $\Delta f_{1s, 2s}^{(2002)} =
f_{1s, 2s}^{(2018)} - f_{1s, 2s}^{\mathrm{(exp)}}$ is
\begin{equation}
  \label{eq:Delta-f_1s2s-2018}
  \Delta f_{1s,2s}^{(2018)} = 736.831 ~ \text{kHz} .
\end{equation}
$| \Delta f_{1s, 2s}^{(2018)} |$ is much larger than the uncertainty of $f_{1s, 2s}^{(2018)}$,
$\delta f_{1s, 2s}^{(2018)} = 6.4$~kHz, and much larger than the experimental uncertainty
$\delta f_{1s, 2s}^{\mathrm{(exp)}} = 0.010$~kHz.

The hydrogen $1s$-$2s$ transition frequency $f_{1s, 2s}^{(2018)}$
using the proton RMS charge radius in Eq.~(\ref{eq:proton-radius-num-2018})
and the Dirac frequency in Eq.~(\ref{eq:f-Dirac-2018-34}) is
\begin{equation}
  \label{eq:f_1s2s-2018-34}
  \tilde{f}_{1s,2s}^{(2018)} =
  ( 2466061413187.035 \pm 6.4 ) ~ \text{kHz},
\end{equation}
and the discrepancy $\Delta \tilde{f}_{1s, 2s}^{(2002)} =
f_{1s, 2s}^{(2018)} - f_{1s, 2s}^{\mathrm{(exp)}}$ is
\begin{equation}
  \label{eq:Delta-f_1s2s-2018-34}
  \Delta \tilde{f}_{1s,2s}^{(2018)} = -23.948 ~ \text{kHz} .
\end{equation}
$| \Delta \tilde{f}_{1s, 2s}^{(2018)} |$ is larger than the uncertainty of $\tilde{f}_{1s, 2s}^{(2018)}$,
$\delta \tilde{f}_{1s, 2s}^{(2018)} = 6.4$~kHz, and much larger than the experimental uncertainty
$\delta f_{1s, 2s}^{\mathrm{(exp)}} = 0.010$~kHz.

\textit{Fitting $r_{p}$ to obtain optimal transition frequency}:
Next, since $r_{p}$ is the least well-known of the fundamental constants that enter
into the expression for $\tilde{f}_{1s, 2s}$, we fit $r_{p}$ so as to minimize
$\Delta {\tilde f}_{1s,2s} \equiv {\tilde f}_{1s, 2s} - f_{1s, 2s}^{\mathrm{(exp)}}$.
We expand $\Delta \tilde{f}_{1s, 2s}$ in powers of
$\varrho_p \equiv (r_{p} - r_{p}^{(2018)})/\delta r_{p}^{(2018)}$, and get
\begin{equation}
  \Delta \tilde{f}_{1s, 2s} =
  \Delta \tilde{f}_{1s, 2s}^{(2018)} -
  \mathcal{B}_{1} \, \varrho_p -
  \mathcal{B}_{2} \, \varrho_{p}^{2} ,
\end{equation}
where $\mathcal{B}_{1} = 429.337 \, \delta f_{1s, 2s}^{\mathrm{(exp)}}$
and $\mathcal{B}_{2} = 0.484751 \, \delta f_{1s, 2s}^{\mathrm{(exp)}}$.
We can solve for the value of $r_p$ which gives $\Delta \tilde{f}_{1s, 2s} = 0$ and
we find that $r_{p}^{\mathrm{(fit)}} = 0.830734$~fm, so that $\Delta r_{p}^{\mathrm{(fit)}} \equiv
r_{p}^{\mathrm{(fit)}} - r_{p}^{(2018)} = -5.613 \, \delta r_{p}^{(2018)} = -0.01066$~fm,
where $\delta r_{p}^{(2018)}$ is the uncertainty of
$r_{p}^{(2018)}$ in Eq.~(\ref{eq:proton-radius-num-2018}).

Solving the equations $\Delta \tilde{f}_{1s, 2s} = \delta f_{1s, 2s}^{\mathrm{(exp)}}$
and $\Delta \tilde{f}_{1s, 2s} = -\delta f_{1s, 2s}^{\mathrm{(exp)}}$ for $r_p$, we estimate
the uncertainty $\delta r_{p}^{\mathrm{(fit)}}$ due to the uncertainty
$\delta f_{1s, 2s}^{\mathrm{(exp)}}$ of $f_{1s, 2s}^{\mathrm{(exp)}}$, and we find
$\delta r_{p}^{\mathrm{(fit)}} = 0.002 \, \delta r_{p}^{(2018)}$.  Note that
$\delta r_{p}^{\mathrm{(fit)}}$ is much smaller than $\delta r_{p}^{(2018)}$.
Hence, we take $\delta r_{p}^{(2018)}$ as the uncertainty for $r_p$.

{\textit{Summary and Conclusion}}:
We have calculated the $1s$-$2s$ quantum transition frequency of the hydrogen atom using QED
radiative and finite nuclear size and mass corrections, and evaluated the uncertainty of the
calculated result due to uncertainties in the fundamental constants using four methods.
(1) The procedure outlined in Ref.~\cite{Eides-hydrogen-atom} yields $f_{1s,2s}^{\mathrm{(Eides)}} = ( 2466061412396 \pm 21 )$~kHz and its uncertainty
$\delta f_{1s,2s}^{\mathrm{(Eides)}} = 2$~kHz. (2) The 2002 CODATA of
Ref.~\cite{CODATA-2002} yields $f_{1s,2s}^{\mathrm{(2002)}} = ( 2466061413996 \pm 23 )$~kHz and
its uncertainty $\delta f_{1s,2s}^{\mathrm{(2002)}}  = 19.522$~kHz. (3) The 2018 CODATA of
Ref.~\cite{proton_radius} yields $f_{1s,2s}^{\mathrm{(2018)}}  = ( 2466061413163.087 \pm 6.4 \big)$~kHz and
its uncertainty $\delta f_{1s,2s}^{\mathrm{(2018)}} = -23.948$~kHz.  (4) using method (3) but
fitting the proton RMS charge radius to obtain
$f_{1s,2s}^{(2018,\mathrm{fit)}} = f_{1s,2s}^{(\mathrm{exp)}}$,
which has an uncertainty due to the uncertainty of the fundamental constants of $\delta f_{1s, 2s}^{(2018,\mathrm{fit})} = 6.4$~kHz.

To conclude, atomic hydrogen $1s$-$2s$ spectroscopy has been crucial for the development of quantum
mechanics. Due to hydrogen's simple structure, combined with the long lifetime of the
$2s$ level and the Doppler suppression of the two-photon transition, it is crucial for
testing the accuracy of quantum mechanics.  Moreover, it will likely be crucial
for studying CPT symmetry using anti-hydrogen \cite{Ahmadi, Kostelecky, Bluhm, Rasmussen}.

A useful interaction with V.A. Yerokhin and K. Pachucki is gratefully acknowledged.


\section{Introduction} \label{sec:intro}
Wikidata is the largest collaborative general knowledge graph supported by a worldwide community. As of November 2022, Wikidata contains 100 million items, 1.4 billion statements and covers many general topics for knowledge exploration and data science applications\footnote{Wikidata Statistics: \url{https://www.wikidata.org/wiki/Wikidata:Statistics}}. Wikidata also contains references that provide additional information, such as sources and URL links to such statements (1 billion statement references as in the dump November 2022 of Wikidata).

Unfortunately, due to the enormous size of Wikidata, extracting and exploring knowledge from Wikidata are challenging even using the standard public Wikidata Query Service (WDQS)\footnote{Wikidata Query: \url{https://query.wikidata.org/}} or parsing official released dumps\footnote{Wikidata Dumps: \url{https://dumps.wikimedia.org/wikidatawiki/entities/}} of Wikidata.
The amount of information in Wikidata has been growing rapidly 39 times over seven years, from 3 GB (gzip compressed dump) in 2015 to 118 GB in 2022, and it keeps increasing as more and more data. Because of the execution timeout limit problem of Wikidata online query service \cite{wikidata}, users cannot make large queries with millions of results, execute complex queries requiring large aggregation operations, or access huge statement references. Moreover, hosting a local copy of Wikidata requires powerful servers (minimum hardware requirement: 16 CPU cores, 128GB RAM, and 1.5T SSD storage \cite{wikidata_limit}.)

This paper introduces our preliminary works on Wikidata-lite, a toolkit to help build a Wikidata database offline from the Wikidata dump to extract, explore, and analyze Wikidata knowledge \cite{wikidb}. Wikidata-lite aims to be fast and easy for Wikidata knowledge extraction and exploration for data scientists and application developers. With these objectives, we implement Wikidata-lite with key-value stores  (\textbf{lmdb}\footnote{lmdb: \url{http://www.lmdb.tech/doc/}, and python binding \cite{lmdb}}) as the underneath database. It allows fast reading and saves memory since the entire database is available in a memory map of a hard disk; there is no need to do extra copy data to memory. The tool also supports fully concurrent read access from multiple processes and threads.

Wikidata-lite is an ongoing development project, the current release features are as follows:
\begin{itemize}
    \item Retrieving information about 100 million entities and 1.4 billion statements for knowledge exploration. The information includes item labels, descriptions, aliases in multilingual, and statement information.
    \item Accessing more than 1 billion references for fact-checking applications.
    \item Searching entities by their attributes for subset item extraction. For example, it takes 0.02 seconds to get 5,868,897 males (wd:Q6581072) using Wikidata-lite while getting a timeout limit error using the online query service of Wikidata.
\end{itemize}

The rest of the paper is structured as follows. We describe the related work in Section \ref{sec:related_work}. We introduce the Wikidata-lite toolkit and the current representative use cases in Section \ref{sec:tool}. Finally, in Section \ref{sec:future}, we present conclusions and discuss the upcoming features of Wikidata-lite.
\begin{figure*}[htbp]
\centering
\includegraphics[width=\textwidth]{wikidata_lite.pdf}
\caption{Wikidata-lite workflow and features}
\label{fig:framework}
\end{figure*}
\section{Related Work} \label{sec:related_work}
Many tools are available to parse, query, and explore knowledge from Wikidata dumps. KGTK is a knowledge graph toolkit for creating, transforming, merging, and exploring knowledge graphs \cite{kgtk}. KGTK model knowledge graphs in tab-separated (TSV) files with four columns: edge-identifier, head, edge-label, and tail. Wikidata dumps could be converted to KGTK formats with transformation operations. KGTK provides many graph manipulation operations such as intersection, subtraction, and joining and other analytics operations such as calculating node popularities, degrees, shortest paths, or graph embeddings. The TSV files could be imported to the Kypher processor to query Wikidata knowledge \cite{kyper}. The Kyper underneath technique translates the TSV file into SQL and executes it on SQLite so that it also consumes an enormous memory if executing a large query. However, the current KGTK release does not support accessing statement references. Moreover, Wikidata-lite is implemented using lmdb on key-value storage with memory maps with \textbf{lmdb}, making it faster and simpler than using SQLite (one more abstraction of SQL data model on top of storage).

WDumper is a toolkit for creating a topical subset (set of entities related to particular topics and the relationships between them) from the JSON dump of Wikidata \cite{wdumper}. Since WDumper allows users to extract and filter a small sampling of Wikidata, exploring subsets on small devices such as laptops or personal computers is feasible. The WDumper output is an RDF dump (N-Triple). Unlike the subset reusability objective of WDumper, Wikidata-lite focuses on extracting and exploring whole Wikidata knowledge.

There are many other tools to query, transform and analyze RDF knowledge graphs, such as Neo4J\footnote{Neo4j: \url{https://neo4j.com/}}, Graphy\footnote{Graphy: \url{https://graphy.link/}} and RDFlib\footnote{RDFlib: \url{https://rdflib.readthedocs.io/en/stable/}}. In this work, we only focus on the JSON dump of Wikidata knowledge graph.
\section{Wikidata-lite} \label{sec:tool}
In this section, we first present Wikidata-lite in Section \ref{sec:wikidata_lite}, then the use-cases are introduced in Section \ref{sec:usecases}.
\subsection{Architecture} \label{sec:wikidata_lite}

Wikidata-lite helps user access Wikidata offline with high-speed performance and memory efficiency usage. Figure \ref{fig:framework} depicts an overview of Wikidata-lite.

Given a JSON dump file of Wikidata, Wikidata-lite parses the dump as a JSON object for each item. Then, the item information is transformed into a key-value object, where keys are item IDs. The values are JSON objects about item labels, descriptions, aliases, site links, and all statements and references related to this item. In the data indexing module, the key-value objects are directly written to the memory map of a hard disk using \textbf{lmdb} library. The entire Wikidata is stored in memory maps allowing direct access to item information without copying this information to memory. We also build an inverted index of Wikidata items for item search with attribute features and calculate item popularity using the PageRank algorithms. The processing and indexing steps take two days, and the final \textbf{lmdb} file size is around 200GB (the compressed size for sharing is 35GB).

The Wikidata retrieval module helps to fast access item information about the specific query as explained in Section \ref{sec:retrieval}. Users also can search items by labels (keywords) as mentioned in Section \ref{sec:search_keywords}. The item search by attributes allows users to find a subset of entities based on their attributes as introduced in Section \ref{sec:search_attributes}. We released the source code, a transformed database, and example codes in this preliminary work. The API and interfaces will be released soon in future work.

\subsection{Use-cases} \label{sec:usecases}
This section explains Wikidata-lite use cases, i.e., item information retrieval, item search by keywords, and item search by attributes.

\subsubsection{Item Information Retrieval} \label{sec:retrieval}
As all item information is stored in memory maps, it is really fast to retrieve items. The item information includes:
\begin{itemize}
\item Labels, descriptions, aliases: Users could get item labels, descriptions, and aliases in one specific language or all languages available.
\item Site links: Users can access all Wikipedia titles and other projects linked to the item.
\item Statements and references: This function will return all statements and references of the query item.
\item Others: Users also can retrieve item types, inverse relations such as the instance of relationships, the subclass of relationships, or getting relationships between two Wikidata items.
\end{itemize}

The item information retrieval of Wikidata-lite is also easy to integrate into other downstream applications such as entity linking on text or tabular data \cite{semtab2021}, \cite{mtab2021}.

\subsubsection{Item Search by Keywords} \label{sec:search_keywords}
We use the MTabES approach \cite{mtabes} to build item search by keywords. MTabES is a search tool that allows re-ranking between rankings of the algorithms BM25 (using ElasticSearch\footnote{ElasticSearch: \url{https://www.elastic.co/}}), fuzzy search with edit distances (using SymSpell:
Symmetric Delete algorithm \cite{Garbe_SymSpell_2012}), and PageRank scores. We index all item labels and aliases in multilingual. Users could access item search APIs and demos at \url{https://mtab.kgraph.jp/mtabes}.

\subsubsection{Item Search by Attributes} \label{sec:search_attributes}
We implement the item search by attributes inspired from the haswbstatement feature of Wikibase Cirrus Search\footnote{haswbstatement fetures: \url{https://www.mediawiki.org/wiki/Help:Extension:WikibaseCirrusSearch}}. The module returns items with specific values in the statement with specific properties. However, Wikidata-lite could directly search items with/or without specific properties as the inputs.
For example, getting all scholarly articles that have relations with DNA, or X-ray diffraction, or molecular geometry, and Francis Crick and Nature. The corresponding query input is a combination of query statements of (AND, "P31", "Q13442814"), (OR, None, "Q7430"), (OR, None, "Q12101244"), (OR, None, "Q911331"), (AND, None, "Q123280"), (AND, None, "Q180445"). Wikidata-lite returns 46 items in 0.01754 sections for the query. A query statements contain three parts: Boolean operations (\textit{AND/OR/NOT}), property IDs (If there is no property given, the value of property ID is None), and item IDs.

Another example of the queries that return millions of results is getting all male (AND, None, Q6581097). It takes 0.02 seconds to get 5,868,897 items, while the online query service of Wikidata will get a timeout limitation for this query. Other examples of item search by attributes can be found at \url{https://github.com/phucty/wikidb/blob/master/example.ipynb}.

\section{Conclusion and Future Work} \label{sec:future}
This paper introduces our preliminary work on Wikidata-lite, a toolkit for offline extracting and exploring Wikidata knowledge. Wikidata-lite has high performance and memory efficiency, allowing users to retrieve item information, statements, and references from Wikidata dump. Users also can search items by keywords or attributes.

One extension of Wikidata-lite is the ability to handle attribute item search with natural language text by integrating keyword item search to find correct item IDs beforehand. We also plan to use Wikidata-lite for data summarization tasks and natural language generation from Wikidata statements.

On the consumer side, we plan to make Wikidata-lite available as a service released with REST APIs and an interface that allows users to use all Wikidata-lite operations directly.
\section*{Acknowledgements}
The research was supported by the Cross-ministerial Strategic Innovation Promotion Program (SIP) Second Phase, “Big-data and AI-enabled Cyberspace Technologies” by the New Energy and Industrial Technology Development Organization (NEDO).

\bibliographystyle{IEEEtran}


\section{Introduction}
In the element distinctness problem, we are given a black box (oracle) $O_x$ that when queried index $i$ of the unknown string $x=(x_1,x_2,\ldots,x_N)\in [M]^N$, where $[M]=\{1,2,\ldots,M\}$ and $M\geq N$, it  outputs the value $x_i$.
The task now is to determine whether the string $x$ contains two equal items $x_{i}=x_{j}$ (called the colliding pair), with as few queries to the index oracle $O_x$ as possible.
The problem is well-known both in classical and quantum computation. The classical bounded-error query complexity (a.k.a decision tree complexity, see \cite{decision_tree_survey} for more information) is shown to be $\Theta(N)$ by a trivial reduction from the OR-problem \cite{quantum_alg1.2}. In comparison, Ambainis proposed a $O(N^{2/3})$-query quantum algorithm with bounded-error \cite{quantum_alg2.1,quantum_alg2.2}.
The algorithm is also optimal: the bounded-error quantum query complexity of the element distinctness problem has previously been shown to be $\Omega(N^{2/3})$ \cite{quantum_lower1,quantum_lower2,quantum_lower3} by the polynomial method \cite{polynomial}.

In \cite{quantum_alg2.1,quantum_alg2.2}, Ambainis first designed a $O(N^{2/3})$-query quantum algorithm $\mathcal{A}$ which solves the promised version in which  $x$ contains at most one colliding pair, by using quantum walk search on Johnson graph.
He then reduced the problem to this promised version, by sampling a sequence of exponentially shrinking subsets to run $\mathcal{A}$.
By showing the probability that the sequence has a subset containing at most one colliding pair is greater than $1/2$ and the overall query complexity is of the same order, Ambainis successfully solved the element distinctness problem with query complexity $O(N^{2/3})$.
This two-stage process shows the promise problem that the algorithm $\mathcal{A}$ solves is crucial, and we formalize it in the following:

\begin{mytcbprob}{element distinctness problem with at most one colliding pair }{at_most_1}
\textbf{input:} index oracle $O_x$ hiding the unknown string $x=(x_1,x_2,\ldots,x_N)\in [M]^N$.

\textbf{promise:} $x$ contains exactly one colliding pair $x_i=x_j$ with $i\neq j$; or $x_i$s are distinct for $i\in[N]$.

\textbf{output:} index $(i,j)$ of the colliding pair $x_i=x_j$; or ``all distinct”.
\end{mytcbprob}

In fact, $\mathcal{A}$ is a one-sided error algorithm: if the string $x$ contains a colliding pair $x_i=x_j$, then $\mathcal{A}$ might asserts that $x$ is ``all distinct''; but if elements in $x$ are all distinct, then $\mathcal{A}$ won't make a mistake. This inspires us to consider the question: is there an exact quantum algorithm that solves Problem~\ref{problem:at_most_1} with the same query complexity $O(N^{2/3})$? In this paper, we answer the question affirmatively by presenting Algorithm~\ref{alg:main_block} in Section~\ref{sec:alg}. We summarize our result as:

\begin{theorem}\label{thm:intro}
There exits an exact quantum algorithm that solves Problem~\ref{problem:at_most_1} with query complexity $O(N^{2/3})$.
\end{theorem}

The main steps of  Algorithm~\ref{alg:main_block} is as follows:
\begin{enumerate}
    \item Converting Problem~\ref{problem:at_most_1} to quantum walk search on a quasi-Johnson graph $G$ (using the staggered model \cite{staggered}). This is done in Section~\ref{subsec:johonson} similar to \cite{Portugal_2018,Portugal_book}, but we modify the quantum walk operator $u := U_B(\theta_2) U_A(\theta_1)$ and the operator $R_T(\alpha)$ which marks the target vertices by multiplying them by the phase $e^{i\alpha}$, so that the angle parameters $\theta_1,\theta_2,\alpha$ are no longer restricted to $\pi$. The flexibility in setting these angle parameters offers an opportunity to design an exact algorithm.

    \item Reducing quantum walk search on the whole graph $G$ to its $5$-dimensional invariant subspace $\mathcal{H}_0$, by classifying the vertices of $G$, i.e. $(r+1)$-sized subsets $(S,y)$ of string $x$'s indices $[N]$, into $5$ groups according to the $5$ different cases in which subset $(S,y)$ intersect with the colliding pair. This is presented in Section~\ref{sec:reduction}, where we also obtain the expression of $U_B(\theta_2)$ and $U_A(\theta_1)$ in $\mathcal{H}_0$.

    \item Reducing further the $5$-dimensional subspace of quantum walk search to the $2$-dimensional qubit subspace $\mathcal{H}_1 := \text{span}\{\ket{\psi_0},\ket{T}\}$. This part (shown in Section~\ref{sec:clock}) is the core of this paper with quite some technique, and we elaborate it in the following steps:
    \begin{enumerate}[(i)]
        \item Based on Jordan's Lemma \cite{Jordan_1875}, we decompose the quantum walk operator $u=U_B(\theta_2) U_A(\theta_1)$ to the direct sum of a scalar-multiplication in the $1$-dimensional invariant subspace spanned by initial state $\ket{\psi_0}$, and two 3D-rotations on two different Bloch spheres (two $2$-dimensional invariant subspaces).
        \item Based on the special rotation angles $\phi_1,\phi_2$ of the two 3D-rotations obtained in step (i), and the {\it intuition} of the minute hand (the bigger angle $\phi_2$) catching up with the hour hand ($\phi_1$) on a watch, we devise the equations [Eq.~\eqref{eq:inner_angle1}] that the iteration number $ct_2$ of $u=U_B(\theta_2) U_A(\theta_1)$ and the two fixed angles $\theta_1,\theta_2$ therein should satisfy, so that the effect of $u^{ct_2}$ on the two Bloch spheres both become the identity transformation. The overall effect of $u^{ct_2}$ in $\mathcal{H}_0$ thus becomes a phase rotation about the initial state: $e^{-i\beta \ket{\psi_0}\bra{\psi_0}}$, where $\beta$ is some fixed angle to be determined in the next step.
        \item With some detailed analysis (Lemma~\ref{thm:inner_exist}) on Eq.~\eqref{eq:inner_angle1}, we show that it posses solutions $\theta_1,\theta_2$ when $ct_2$ is set according to Eq.~\eqref{eq:inner_iter1}, so that the intuition in step (ii) really works.
    \end{enumerate}
    By step (ii), we have actually obtained the $2$-dimensional invariant subspace $\mathcal{H}_1 = \text{span}\{\ket{\psi_0},\ket{T}\}$ of the quantum walk search iteration $u^{ct_2}R_T(\alpha)=e^{-i\beta \ket{\psi_0}\bra{\psi_0}} e^{i\alpha \ket{T}\bra{T}} =: S_r(\beta) S_o(\alpha)$, which is the generalized Grover's iteration $G(\alpha,\beta)$.

    \item We use the fixed-axis-rotation (FXR) method \cite{FXR}, in Section~\ref{sec:FXR}, to obtain the appropriate parameters $\alpha_1,\alpha_2$ of rotation $F_{xr,\beta}:=G(\alpha_2,\beta) G(\alpha_1,\beta)$ and its iteration number $t_1$ [see Eqs.~\eqref{eq:outer_iter1}-\eqref{eq:im1}], such that applying $F_{xr,\beta}^{t_1}$ to the initial state $\ket{\psi_0}$ produces precisely the target state $\ket{T}$.
\end{enumerate}

Problem \ref{problem:at_most_1} has also been studied by Portugal in \cite{Portugal_2018,Portugal_book}, where he improves the success probability of Algorithm $\mathcal{A}$ from constant to $1-O(N^{1/3})$, quickly approaching $1$, by careful analysis on the asymptotic behaviours of eigenvalues and eigenvectors of the quantum walk iterations $[(U_B(\pi) U_A(\pi))^{t_2}R_T(\pi)]^{t_1}$ when $N\to\infty$, and by setting the optimal iteration numbers $t_1,t_2$.
However, asymptotic behaviours are not enough to design an exact algorithm. Therefore in step 3 to determine the effect of $u^{ct_2}$, we use Jordan's Lemma \cite{Jordan_1875} about common invariant subspaces of two reflections instead.
Note that in our case we consider `reflections' with partial phase $\theta\neq \pi$. Jordan's Lemma has been widely used in the literature, such as the spectral lemma of quantum walk operator based on Markov chain \cite{Szegedy_03}, spectral decomposition of interpolated quantum walk operator \cite{Krovi2016}, and the qubitization technique in quantum singular value transformation \cite{QSVT}.

The promise in Problem~\ref{problem:at_most_1} that there is at most one colliding pair is in some sense necessary to design a fast and exact quantum algorithm, because without any promise on the number of equal elements in $x$, the deterministic quantum query complexity will be $\Omega(N)$. In fact, we can first reduce the problem of calculating the Boolean function $OR(y),\ y\in\{0,1\}^N$ to the element distinctness problem of a specific string $x\in \{0,1,\ldots,N\}^{N+1}$ such that $x_i=(1-y_i)i,\forall i\in[N]$ and $x_{N+1}=0$ \cite{quantum_alg1.2}. Then $OR(y)=1$ if and only if $x$ contains a colliding pair. This reduction tells us that the query complexity of the element distinctness problem must be greater than that of calculating the Boolean function $OR$. Secondly, the deterministic quantum query complexity of calculating $OR$ on the domain $\{0,1\}^N$ is shown to be $N$ by the polynomial method \cite{polynomial}. Therefore, any exact quantum algorithm solving the element distinctness problem without any promise on the number of colliding pairs must query the index oracle $O_x$ for $\Omega(N)$ times.

On the other hand, the deterministic quantum query complexity of Problem~\ref{problem:at_most_1} is $\Omega(N^{2/3})$, so that the $O(N^{2/3})$ in Theorem \ref{thm:intro} is actually $\Theta(N^{2/3})$!
Note, however, that the aforementioned $\Omega(N^{2/3})$ bounded-error quantum query complexity of the general element distinctness problem by the polynomial method {\it does not} imply the $\Omega(N^{2/3})$ lower bound of Problem~\ref{problem:at_most_1}, because the promised version is easier than the general version and thus the query lower bound smaller.
Nevertheless, we can use the adversary method instead, because the negative-weight adversary lower bound \cite{hoyer2007negative} of the decision version of Problem~\ref{problem:at_most_1} has been proved to be $\Omega(N^{2/3})$ \cite{belovs2012adversary,rosmanis2014quantum}. For completeness, we describe the proof of the $\Omega(N^{2/3})$ lower bound of Problem~\ref{problem:at_most_1} in Section \ref{sec:lower_bound}.

\section{\label{sec:alg}Description of the algorithm}
In this section, we present an exact quantum algorithm for Problem~\ref{problem:at_most_1} (see Algorithm~\ref{alg:main_block}).
\subsection{\label{subsec:johonson}Converting to quantum walk search on quasi-Johnson graph}

The quasi-Johnson graph $G$ underlying Algorithm~\ref{alg:main_block} has {\it vertex set} $V=\{(S,y):S\in S_r,\ y\in [N]\setminus S \}$, where  $S_r$ consists of all the $r$-sized subsets of $ [N]$. Index $y$ can be seen as the index to be swapped into $S$ in one step of quantum walk. $r$ is set to be
\begin{equation}\label{eq:r_def}
    r=\lfloor N^{{2}/{3}} \rfloor.
\end{equation}
An {\it edge} in $G$ connects two different vertices $(S,y)$ and $(S',y')$ if and only if $S=S'$ or $S\cup\{y\}=S'\cup\{y'\}$.
Note that $|V|=\binom{N}{r}(N-r)$, which is not equal to $\binom{N}{r+1}$. Thus $G$ is not a real Johnson graph, whose edges connect two vertices, i.e. $(r+1)$-sized subsets, if and only if they differ in exactly one element.

Every vertex is equipped with $r+1$ slots of size $M$ to store the item values in string $x$ corresponding to the index set $S\cup\{y\}$. Thus the basis of the two working registers is of the following form:
\begin{equation*}
    \ket{S,y}\otimes \ket{x'_1,x'_2,\ldots,x'_{r+1}}.
\end{equation*}
Suppose we store the value $x'_i$ with $m$ qubits ($2^m\geq M$). Then the effect of the index oracle $O_x$ is
\begin{equation}\label{eq:oracle}
    O_x \ket{i}\ket{b}=\ket{i}\ket{b\oplus x_i},
\end{equation}
where $i\in [N]$ is the querying index, and $\oplus$ is bit-wise XOR on $m$ qubits. Thus $O^2=I$.

As vertex basis $\ket{S,y}\in \mathbb{C}^{\binom{N}{r}}\otimes \mathbb{C}^{ N-r } $ encodes the index set $S\cup\{y\}$, we will need a quantum subroutine $\mathcal{P}$ to obtain the ascending index sequence $(i_1,i_2,\ldots,i_r)$ corresponding to $S$, and the true index $\bar{y}\in [N]$ corresponding to $y$, so as to query the index oracle $O_x$. To be more precise,
\begin{equation}\label{eq:SubroutineP}
    \mathcal{P}: \ket{S,y} \otimes \ket{b_1} \cdots \ket{b_r} \ket{b'} \mapsto \ket{S,y} \otimes \ket{b_1\oplus i_1} \cdots \ket{b_r\oplus i_r} \ket{b'\oplus \bar{y} }.
\end{equation}
Note that $\mathcal{P}^2=I$. The decoding procedure $\mathcal{P}$ might take a lot of space, but as we are only considering query complexity, this is not a problem.

The {\it edge set} of graph $G$ is actually determined by the two local diffusion operator $U_A(\theta_1)$ and $U_B(\theta_2)$, as the edges indicate the transiting restriction among vertices in a step of quantum walk $u=U_B(\theta_2) U_A(\theta_1)$. Operator $U_A(\theta_1)$ is defined as
\begin{equation}\label{eq:U_A_def}
    U_A(\theta_1) = I-(1-e^{i\theta_1}) \sum_{S\in S_r} \ket{A_S}\bra{A_S},
\end{equation}
where
\begin{equation}\label{eq:As}
    \ket{A_S} = \frac{1}{\sqrt{N-r}} \sum_{y\in[N]\setminus y} \ket{S,y}
\end{equation}
is an equal-superposition of the clique $A_S=\{(S,y)\in V : y\in [N]\setminus S \}$ determined by $S$. Note that $|A_s|=N-r$ and there are $\binom{N}{r}$ cliques of this kind. From the definition of $U_A(\theta_1)$, we know that it transits a vertex to a superposition of vertices in the same clique, but never to vertex in other clique. Therefore, $U_A(\theta_1)$ corresponds to applying Grover diffusion operator in every clique $A_S$.

The other diffusion operator $U_B(\theta_2)$ is the combined effect of steps 3.(b).(ii)-(iv) in Algorithm~\ref{alg:main_block} on the first register. The operator $U_B^{\text{EXT}}(\theta_2)$ in step 3.(b).(iii) is a bit complicated, and is defined as
\begin{equation}\label{eq:U_B_def}
    U_B^{\text{EXT}}(\theta_2) = I- (1-e^{i\theta_2}) \sum_{(x_1',\ldots,x_{r+1}')} \sum_{[S,y]} \ket{B_{[S,y]}^{(x_1',\ldots,x_{r+1}')}} \bra{B_{[S,y]}^{(x_1',\ldots,x_{r+1}')}},
\end{equation}
where the first sum is over all the possible string $(x_1',\ldots,x_{r+1}')\in [M]^{r+1}$, and the second sum is over all the representatives $[S,y]$ of clique $B_{[S,y]}=\{ (S',y') : \{y'\}\cup S'=\{y\}\cup S \}$. Note that $|B_{[S,y]}|=r+1$ and there are $\binom{N}{r+1}$ of this kind.
The state $\ket{B_{[S,y]}^{(x_1',\ldots,x_{r+1}')}}$ is determined by $[S,y]$ and $(x_1',\ldots,x_{r+1}')$, and is defined as
\begin{equation}
    \ket{B_{[S,y]}^{x_1',\ldots,x_{r+1}'}} = \frac{1}{\sqrt{r+1}} \sum_{y'\in S\cup \{y\}} \ket{S\cup\{y\}\setminus\{y'\},y'}\ket{\pi(x_1'),\ldots,\pi(x_{r+1}')},
\end{equation}
where the permutation $\pi$ on the second register is related to the permutation of indices in the first register. This relation is best illustrated by an example: suppose $[S,y]=[\{1,4\},3]$, then
\begin{equation}\label{eq:example}
    \ket{B_{[S,y]}^{(x_1',x_2',x_3')}} = \frac{1}{\sqrt{3}} \Big( \ket{\{1,4\},3}\ket{x_1',x_2',x_3'} + \ket{\{3,4\},1}\ket{x_3',x_2',x_1'} + \ket{\{1,3\},4}\ket{x_1',x_3',x_2'} \Big).
\end{equation}
Compared to the first term in Eq.~\eqref{eq:example}, the third term exchanged the index $4$ and $3$. Therefore $\pi$ exchanges the corresponding $x_2'$ and $x_3'$ in the second register. The second term is obtained in a similar fashion.
Although the indices in $S$ are unordered, we regard them to be in the ascending order so that $\ket{B_{[S,y]}^{x_1',\ldots,x_{r+1}'}}$ is well-defined. For example, $x_3'$ in the second term of Eq.~\eqref{eq:example} is related to index $3$ but not $4$.
Combining this and the ascending order of the output sequence of $\mathcal{P}$, we know that during the whole procedure of Algorithm~\ref{alg:main_block}, $\ket{x_{i_1},\ldots,x_{i_r}}$ in the second register as the subset of $x=(x_1,\ldots,x_N)$ is always related to the ascending index sequence $(i_1,\ldots,i_r)$ of $\ket{S}$ in the first register.
Thus we can omit the second register when analyzing the algorithm. Moreover, in the final measurement of Algorithm~\ref{alg:main_block}, the two registers will collapse to the entangled state $\ket{S,y}\ket{x_{i_1},\ldots,x_{i_r}}$. Therefore, we can obtain indices of the colliding pair without further quires.
Thus we have shown, the combined effect of steps 3.(b).(ii)-(iv) in Algorithm~\ref{alg:main_block} can be seen as the following operator acting on the first register.
\begin{equation}
    U_B(\theta_2) = I- (1-e^{i\theta_2}) \sum_{[S,y]} \ket{B_{[S,y]}} \bra{B_{[S,y]}},
\end{equation}
where
\begin{equation}
    \ket{B_{[S,y]}} = \frac{1}{\sqrt{r+1}} \sum_{y'\in S\cup \{y\}} \ket{S\cup\{y\}\setminus\{y'\},y'}.
\end{equation}

The {\it marked vertices} $(S,y)$ of graph $G$ are those containing the colliding pair's indices $(i_1,i_2)$ in $S$, and the related marking operator $R_T(\alpha)$ multiplies $\ket{S,y}\ket{x'_1,\ldots,x'_{r},0}$ by $e^{i\alpha}$ if the second register contains the colliding pair. Note that $R_T(\alpha)$ may be time consuming, but it does not need to query the index oracle $O_x$.

An example of the quasi-Johnson graph when $N=5,r=2$ and $(1,3)$ being the indices of the colliding pair in $x=(x_1,\ldots,x_5)$ is shown in Fig.~\ref{fig:johnson}.
It gives us a visual impression of what the quasi-Johnson graph $G$ with its two kinds of cliques $A_S$ and $B_{[S,y]}$ would look like.

\begin{figure}
    \centering
    \includegraphics[width=0.5\textwidth]{Johnson_example.pdf}
    \caption{The quasi-Johnson graph $G$ when $N=5$ and $|S|=r=2$. Note that $\binom{N}{r} (N-r) = \binom{N}{r+1} (r+1) = 10\times 3$, so that the two types of cliques $A_S$ and $B_{[S,y]}$ are of the same size $3$ and of the same quantity $10$. The vertex $(S,y)=(\{1,2\},3)$ in $G$, for example, is represented by the blue circle with shorthand ``$12,3$'' inside. The cliques $A_S$ are represented by equilateral triangles with red dotted edges. The cliques $B_{[S,y]}$ are represented by shaded gray triangles with black solid edges, $4$ of them are equilateral and the other $6$ triangles are obtuse. Suppose $(1,3)$ is the indices of the colliding pair in $x=(x_1,\ldots,x_5)$. Then the three nodes in the upper right corner with bold numbers ``$\textbf{13}$'' inside are the marked vertices.}
    \label{fig:johnson}
\end{figure}

If we denote the equal-superposition of all the marked vertices by $\ket{T}$, and the equal-superposition of all vertices by $\ket{\psi_0} := \frac{1}{\sqrt{|V|}} \sum_{(S,y)\in V} \ket{S,y}$, then the goal of quantum walk search on quasi-Johnson graph $G$ is to transform $\ket{\psi_0}$ to $\ket{T}$ by applying an appropriate sequence consists of $U_A(\theta_1),U_B(\theta_2)$ and $R_T(\alpha)$.

\begin{algorithm}[htb]
    \SetKwFunction{}{}
    \SetKwInOut{KWProcedure}{Procedure}
    \SetKwInput{Runtime}{Runtime}
    \caption{Exact quantum algorithm for Problem~\ref{problem:at_most_1}}
    \label{alg:main_block}
    \LinesNumbered

    \KwIn {index oracle $O_x$ given in Problem~\ref{problem:at_most_1} [effect shown in Eq.~\eqref{eq:oracle}]}
    \KwOut {indices $(i_1,i_2)$ of the colliding pair; or ``all distinct”.}

    \KWProcedure{}

    \begin{enumerate}[1.]
    \item Prepare the equal-superposition  of all vertices $\ket{\psi_0} = \frac{1}{\sqrt{|V|}} \sum_{(S,y)\in V} \ket{S,y}$ in the first register.

    \item Call decoding procedure $\mathcal{P}$ on $\ket{\psi_0}$ to obtain the ascending index sequence $(i_1,\ldots,i_r)$ of $S$, and query $O_x$ for $r$ times to obtain $\frac{1}{\sqrt{|V|}} \sum_{(S,y)\in V} \ket{S,y}\ket{x_{i_1},\ldots,x_{i_r},0} $. Then apply $\mathcal{P}$ again to erase the ancillary register storing the index sequence.

    \item Iterate the following steps for $t_1$ times:
    \begin{enumerate}[(a)]
        \item Apply the marking operator $R_T(\alpha_1)$ which multiplies $\ket{S,y}\ket{x'_1,\ldots,x'_{r},0}$ by $e^{i\alpha_1}$ if the second register contains the colliding pair.
        \item Iterate the following steps for $ct_2$ times:
        \begin{enumerate}[(i)]
            \item Apply $U_{A}(\theta_1)$ [see Eq.~\eqref{eq:U_A_def}] to the first register.
            \item Call $\mathcal{P}$ on $\ket{S,y}$ to obtain $\bar{y}$, and query $O_x$ with $\bar{y}$, storing the answer in the last slot of the second register $\ket{x'_{r+1}}$. Then apply $\mathcal{P}$ again to erase the ancillary register storing the index sequence.
            \item Apply $U_B^{\text{EXT}}(\theta_2)$ [see Eq.~\eqref{eq:U_B_def}] on the two working registers.
            \item Repeat step (ii) to set $\ket{x'_{r+1}}$ back to $\ket{0}$.
        \end{enumerate}
        \item Apply the marking operator $R_T(\alpha_2)$ with a different angle $\alpha_2$.
        \item Repeat step (b).
    \end{enumerate}
    \item Measure the two working registers in computational basis, and based on the outcome $S$ and $(x_{i_1'},\ldots,x_{i_r'})$, obtain indices $(i_1,i_2)$ of the colliding pair; or output ``all distinct” if $(x_{i_1'},\ldots,x_{i_r'})$ are all distinct.
    \end{enumerate}

    p.s. The $6$ parameters $t_1,\alpha_1,\alpha_2,ct_2,\theta_1,\theta_2$ is set according to Eqs.~\eqref{eq:inner_iter1}-\eqref{eq:cos_phi_def}.

\end{algorithm}

\subsection{Parameters in the algorithm}
Algorithm~\ref{alg:main_block} contains $6$ parameters $\alpha_1,\alpha_2,\theta_1,\theta_2,t_1,c\cdot t_2$ to be set below. We justify their values in the next section.
The iteration  number of the inner loop [step 3.(b)] is
\begin{equation}\label{eq:inner_iter1}
    c\cdot t_2 = 10\cdot \lceil \frac{\pi}{2}\sqrt{r} \rceil.
\end{equation}
The rotation parameters $\theta_1,\theta_2$ in the inner loop are solutions to the following equations:
\begin{equation}\label{eq:inner_angle1}
    \cos\phi_1 = -\cos(1-\frac{2}{c})\frac{\pi}{t_2}, \quad \cos\phi_2 = -\cos\frac\pi{t_2},
\end{equation}
where $\cos\phi_i = \cos\frac{\theta_1+\theta_2}{2} + 2\sin\frac{\theta_1}{2} \sin\frac{\theta_2}{2}\, \lambda_i$, and
$\lambda_i=\frac{i(N+1-i)}{(N-r)(r+1)}$.
Let $\beta :=-( c\cdot t_2 \frac{\theta_1+\theta_2}{2} \mod 2\pi)$, $\lambda=\frac{r(r-1)}{N(N-1)}$, and $\phi_0 := |4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2}) \mod [-\frac{\pi}{2},\frac{\pi}{2}]|$, where the notation ``$x \mod [-\frac{\pi}{2},\frac{\pi}{2}]$'' means  adding $x$ with an appropriate integer multiples $l$ of $\pi$, such that $x+l\pi\in [-\frac{\pi}{2},\frac{\pi}{2}]$. Then the iteration number of the outer loop [step 3] is
\begin{equation}\label{eq:outer_iter1}
    t_1 = \lceil \frac{\pi}{\phi_0} \rceil.
\end{equation}
The angle parameters $\alpha_1,\alpha_2$ in the outer loop are solutions to the following equations:
\begin{align}
    0 &= 1- 2\lambda \frac{\tan(t_1\phi)}{\sin\phi} ( -\sin\frac{\alpha_1}{2} \cos\frac{\alpha_2}{2} \sin\beta + 2\sin\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2} (1-2\lambda) ), \label{eq:real1}\\
    0 &=-(1-2\lambda)\sin\beta \tan\frac{\alpha_1}{2} \tan\frac{\alpha_2}{2} + \cos\beta \tan\frac{\alpha_1}{2} +(2\lambda+(1-2\lambda)\cos\beta) \tan\frac{\alpha_2}{2}  +\sin\beta \label{eq:im1},
\end{align}
where $\phi$ satisfies
\begin{align}\label{eq:cos_phi_def}
    \cos{\phi} &= \cos(\frac{\alpha_1+\alpha_2}{2}+\beta) + 2\lambda (\sin\frac{\alpha_1+\alpha_2}{2} \sin\beta -4\sin\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2})
    \notag \\ &\qquad
    + 8\lambda^2 \sin\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2}.
\end{align}

\section{Analysis of the algorithm}
We first analyze the query complexity of Algorithm~\ref{alg:main_block}. From Eq.~\eqref{eq:outer_iter1}, the iteration number $t_1$ of the outer loop is related to angle $\beta/2$. Note that $\frac{\beta}{2}$ tends to a constant which is irrelevant to $N$ when $N\to\infty$ from Eq.~\eqref{eq:infty_beta}. Therefore, the inner loop is iterated for $2t_1\in O(N/r)$ times. As the inner loop queries $O_x$ for $2ct_2\in O(\sqrt{r})$ times, and the preparation of $\ket{\psi_0}$ needs $r$ queries, the total query complexity is $O(N/\sqrt{r}+r)=O(N^{2/3})$ by Eq.~\eqref{eq:r_def}.

We now analyze the correctness of Algorithm~\ref{alg:main_block}. Note that $\ket{\psi_0}$ remains unchanged when the items of $x$ are all distinct, because $R_T(\alpha)$ now becomes the identity operator $I$, and $\ket{\psi_0}$ is invariant under $U_A(\theta_1)$ and $U_B(\theta_2)$. Hence, Algorithm~\ref{alg:main_block} is correct for this case. We thus assume that $x$ contains a single colliding pair in the following three subsections.

\subsection{Reducing to $5$-dimensional subspace}\label{sec:reduction}
The reduced $5$-dimensional subspace $\mathcal{H}_0$ is spanned by five equal-superpositions of the vertices in five different groups: $\eta_0^0,\eta_0^1,\eta_1^0,\eta_1^1,\eta_2^0$, where $\eta_l^j = \{(S,y)\in V: |S\cap K|=l,\, |\{y\}\cap K|=j \}$. That is, we group the vertices of $G$ into five different groups by the $5$ different situations that $(S,y)$ intersects with indices $\{i_1,i_2\}=:K$ of the colliding pair. The size of each groups, by basic combinatorics, is
\begin{equation}\label{eq:set_size}
    |\eta_l^0|=\binom{k}{l}\binom{N-k}{r-l}(N-r-(k-l)), \quad |\eta_l^1|=\binom{k}{l}\binom{N-k}{r-l}(k-l),
\end{equation}
where $k=2$ is the size of $K$. We denote by $\ket{T}$ the target state $\ket{\eta_2^0}$, as all vertices in this group contains indices $\{i_1,i_2\}$ of the colliding pair. Clearly $\ket{\psi_0}\in\mathcal{H}_0$, and the square root of the proportion of targets to all vertices is
\begin{equation}\label{eq:psi_0}
    \braket{T|\psi_0} = \sqrt{\frac{r(r-1)}{N(N-1)}}.
\end{equation}

We now show that the effect of step 3.(b) of Algorithm~\ref{alg:main_block} in $\mathcal{H}_0$ is
\begin{equation}\label{eq:u}
    u = U_B(\theta_2) U_A(\theta_1) = (I-(1-e^{i\theta_2})BB^\dagger) \cdot ( I-(1-e^{i\theta_1})AA^\dagger ),
\end{equation}
where
\begin{equation}
    A\circ A=
\begin{bmatrix}
{1-\frac{2}{N-r}} & 0 & 0 \\
{\frac{2}{N-r}} & 0 & 0 \\
0 & {1-\frac{1}{N-r}} & 0 \\
0 & {\frac{1}{N-r}} & 0 \\
0 & 0 & 1
\end{bmatrix},
\quad B\circ B=
\begin{bmatrix}
1 & 0 & 0 \\
0 & \frac{1}{r+1} & 0 \\
0 & 1-\frac{1}{r+1} & 0 \\
0 & 0 & \frac{2}{r+1} \\
0 & 0 & 1-\frac{2}{r+1}
\end{bmatrix}.
\end{equation}
The  notation $\circ$ here is the Hadamard (element-wise) product. We use it because the square root notation $\sqrt{*}$ takes up too much space.

\textbf{Proof (Calculation):} Consider $U_A(\theta_1) = I-(1-e^{i\theta_1}) \sum_{S\in S_r} \ket{A_S}\bra{A_S}$ first.
Recall from Eq.~\eqref{eq:As} that $\ket{A_S} = \frac{1}{\sqrt{N-r}} \sum_{y\in[N]\setminus y} \ket{S,y}$ is determined by $S$. Thus $\braket{A_S | \eta_l^j} \neq 0$ only if $|S\cap K|=l$, where $l\in \{0,1,2\}$.
To determine its value, note that $\ket{S,y}$ in $\ket{\eta_l^j}$ has to have the same $S$ as that of $A_S$ to produce nonzero inner-product. Therefore, we have
\begin{align}
\braket{A_S | \eta_l^j} &= \frac{\delta_{|S\cap K|,l}}{\sqrt{N-r}\sqrt{|\eta_l^j|}}
\times\begin{cases}
N-r-(k-l), & j=0 \\
k-l, & j=1
\end{cases}\\
&= \frac{\delta_{|S\cap K|,l}}{\sqrt{N-r} \sqrt{\binom{k}{l} \binom{N-k}{r-l}}}
\times \begin{cases}
\sqrt{N-r-(k-l)}, & j=0 \\
\sqrt{k-l}, & j=1
\end{cases}. \label{eq:sumSr}
\end{align}
We now consider the sum $\sum_{S\in S_r} \braket{\eta_{l'}^{j'} | A_S} \braket{A_S | \eta_l^j}$. Note that it's nonzero only if $l=l'$, and thus the sum now reduces to be over those $S\in S_r$ that satisfy $|S\cap K|=l$. There are $\binom{k}{l} \binom{N-k}{r-l}$ of this kind, cancelling the denominator in Eq.~\eqref{eq:sumSr}. Hence, the effect of $U_A(\theta_1)$ in its invariant subspace $\{\ket{\eta_l^0}, \ket{\eta_l^1}\}$ is
\begin{equation}
    I-(1-e^{i\theta_1})
\begin{bmatrix}
\sqrt{1-\frac{k-l}{N-r}}\\
\sqrt{\frac{k-l}{N-r}}
\end{bmatrix}
\begin{bmatrix}
\sqrt{1-\frac{k-l}{N-r}}, &
\sqrt{\frac{k-l}{N-r}}
\end{bmatrix},
\end{equation}
which degenerates to the scalar multiplication $e^{i\theta_1} \ket{\eta_k^0}\bra{\eta_k^0}$ when $l=k$. The effect of $U_A(\theta_1)$ in $\mathcal{H}_0$ as shown in Eq.~\eqref{eq:u} now follows easily. The effect of $U_B(\theta_2)$ can be determined in a similar fashion. \hfill $\blacksquare$

The effect of $R_T(\alpha)$ in $\mathcal{H}_0=\text{span} \{ \ket{\eta_0^0} , \ket{\eta_0^1} , \ket{\eta_1^0}, \ket{\eta_1^1}, \ket{\eta_2^0}  \}$ that appeared in step 3.(a) and 3.(c) of Algorithm~\ref{alg:main_block} is obviously
\begin{equation}\label{eq:Rt}
    R_T(\alpha)=\text{diag}\left( [1,1,1,1,e^{i\alpha}] \right).
\end{equation}
Now the goal of Algorithm~\ref{alg:main_block}, in a nutshell, is to achieve the following equation
\begin{equation}
    1 = \bra{T} \big(u^{c\,t_2} R_T(\alpha_2) \cdot u^{c\,t_2} R_T(\alpha_1) \big)^{t_1} \ket{\psi_0},
\end{equation}
by appropriately setting the parameters therein.

\subsection{Constructing phase rotation about the initial state}\label{sec:clock}

In this subsection, we show how to construct the following phase rotation $R_{\psi_0}(\beta)$ about the initial state $\ket{\psi_0}$, by iterating the quantum walk operator $u= U_B(\theta_2) U_A(\theta_1)$ for $c\cdot t_2$ times.
\begin{equation}
    R_{\psi_0}(\beta) := I-(1-e^{i\beta}) \ket{\psi_0}\bra{\psi_0}
\end{equation}
We first justify the values of $\theta_1,\theta_2$ and $c\cdot t_2$ as shown respectively in Eq.~\eqref{eq:inner_angle1} and Eq.~\eqref{eq:inner_iter1} by the following lemma.

\begin{lemma}\label{lem:inner_effect}
By setting the parameters $\theta_1,\theta_2$ in $u= U_B(\theta_2) U_A(\theta_1)$ and $c\cdot t_2$ according to Eq.~\eqref{eq:inner_angle1} and Eq.~\eqref{eq:inner_iter1} respectively, the effect of $u^{ct_2}$ in $\mathcal{H}_0$ is the following:
\begin{equation}\label{eq:psi_rotate}
    I-(1- e^{i\,ct_2\frac{\theta_1+\theta_2}{2}} )\ket{\psi_0}\bra{\psi_0}.
\end{equation}
\end{lemma}

\textbf{Attention:} Eq.~\eqref{eq:psi_rotate} is defined in the subspace $\mathcal{H}_0$, but not in the whole space spanned by all the vertices of $G$. In fact, to construct Eq.~\eqref{eq:psi_rotate} in the whole space, we claim that one must iterate $u$ for at least $r$ times rather than $ct_2\in O(\sqrt{r})$ times:
if $S_1\cup \{y_1\}$ and $S_2\cup \{y_2\}$ are disjoint (this is possible, since $|S|=r=N^{2/3}\ll N$), then one needs to iterate $u$ for at least $r$ times in order to `transform' $\ket{\psi}$ to $\ket{\varphi}$. `Transform' here means that after $\ket{\psi}$ is changed to some superposition, $\ket{\varphi}$ appears in this superposition.
This is because $U_A(\theta_1)$ and $U_B(\theta_2)$ are diffusion operators within clique $A_S$ and $B_{[S,y]} $ respectively. Thus a step of quantum walk $u=U_B(\theta_2) U_A(\theta_1)$ will only update one index in $S$ for a fixed $(S,y)$.
Eq.~\eqref{eq:psi_rotate} defined in the whole space can certainly `transform' $\ket{\psi}$ to $\ket{\varphi}$ in one step, and thus the claim follows.

\begin{proof}
Similar to the spectral lemma in \cite{Szegedy_03}, we first perform singular value decomposition on the discriminant matrix $D:=A^\dagger B$ of order $3$ as $D=WSV^\dagger = \sum_{i=0}^2 \lambda_i \ket{w_i}\bra{v_i}$. The square $\lambda_i^2$ of the $3$ singular values are
\begin{equation}
     \left[1,\ \left(1-\frac{1}{N-r}\right) \left(1-\frac{1}{r+1}\right),\ \left(1-\frac{2}{N-r}\right) \left(1-\frac{2}{r+1}\right) \right]
     =:
     [\cos^2\frac{\gamma_0}{2},\cos^2\frac{\gamma_1}{2},\cos^2\frac{\gamma_2}{2}].
     \footnote{The singular values shows a particular pattern, i.e. $\cos^2\frac{\gamma_i}{2} = (1-i/(N-r))\cdot(1-i/(r+1)) $, for all the $D=A^\dagger B$ with order $k\geq 1$. We are not able to prove this, and have posted it as an open question in \cite{web_question}.}
\end{equation}
Then we have the following two key equations, which lies at the heart of Jordan's lemma \cite{Jordan_1875}:
\begin{align}
& \Pi_A \cdot B\ket{v_i} := AA^\dagger B\ket{v_i} = AD\ket{v_i}= \cos\frac{\gamma_i}{2} \cdot A \ket{w_i}, \\
& \Pi_B \cdot A\ket{w_i} := BB^\dagger A\ket{w_i} = B(\bra{w_i}D)^\dagger = \cos\frac{\gamma_i}{2} \cdot B \ket{v_i}.
\end{align}
It can be verified that $A\ket{w_0} = B\ket{v_0} = \ket{\psi_0}$. Thus we obtain the three {\it common} invariant subspaces $\{ \ket{\psi_0} \}$, $\text{span}\{A\ket{w_1}, B\ket{v_1} \}$ and $\text{span}\{A\ket{w_2}, B\ket{v_2} \}$ of
\begin{equation}\label{eq:u}
    u=(I-(1-e^{i\theta_2})\Pi_B) \cdot ( I-(1-e^{i\theta_1})\Pi_A ).
\end{equation}

The effect of $u$ in the subspace $\text{span}\{A\ket{w_i}, B\ket{v_i} \}$ ($2$-dimensional space) is the composition of two 3D-rotations: a rotation about $A\ket{w}$ by angle $-\theta_1$, followed by a rotation about $B\ket{w}$ by $-\theta_2$, and the angle between the two rotation axes is $\gamma_i$. We articulate this in the following.
As $\bra{w_i}A^\dagger B\ket{v_i} =\cos\gamma_i/2$, we might as well let $B\ket{v_i} = \cos\gamma_i/2 \ A\ket{w_i} + \sin\gamma_i/2\ A\ket{w_i}^\perp$, where $A\ket{w_i}^\perp$ is perpendicular to $A\ket{w_i}$ and lies in the same qubit space. Simple calculation shows that the effect of $U_A(\theta_1)$ on the orthonormal basis $\{A\ket{w_i},A\ket{w_i}^\perp\}$ is
\begin{equation}
    U_A(\theta_1) =
\begin{bmatrix}
e^{i\theta_1} & 0 \\
0 & 1
\end{bmatrix}
= e^{i\theta_1/2} R_{Aw_i}(-\theta_1/2).
\end{equation}
The notation
\begin{equation}\label{eq:rotate_def}
    R_{\vec{n}}(\phi) := \cos\phi I -i\sin\phi\, \vec{n} \cdot \vec{\sigma}
\end{equation}
represents a rotation on the Bloch sphere about axis $\vec{n}$ by angle $2\phi$ obeying the right-handed rule, and $\vec{n} \cdot \vec{\sigma} := n_x X+n_y Y+n_z Z$, where $X,Y,Z$ are the three Pauli matrices. $U_A(\theta_1)$ thus represents a rotation about $Aw_i=[0,0,1]$ by angle $-\theta_1$. Similarly, the effect of $U_B(\theta_2)$ on the orthonormal basis $\{A\ket{w_i},A\ket{w_i}^\perp\}$ is
\begin{equation}
    U_B(\theta_2)=
\begin{bmatrix}
1-(1-e^{i\theta_2}) \cos^2 \frac\gamma 2 & -(1-e^{i\theta_2}) \sin\frac\gamma 2 \cos\frac\gamma 2 \\
-(1-e^{i\theta_2}) \sin\frac\gamma 2 \cos\frac\gamma 2 & 1-(1-e^{i\theta_2}) \sin^2 \frac\gamma 2
\end{bmatrix}
= e^{i\theta_2/2} R_{Bv_i}(-\theta_2/2),
\end{equation}
which represents a rotation about $Bv_i=[\sin\gamma_i,0,\cos\gamma_i]$ by angle $-\theta_2$. Thus the angle between the two rotation axes $Aw_i$ and $Bv_i$ is $\gamma_i$.

By the composition lemma of two rotations (Exercise~4.15 in \cite{nielsen_chuang_2010}), the effect of $u$ (shown in Eq.~\eqref{eq:u}) in the subspace $\text{span}\{A\ket{w_i}, B\ket{v_i} \}$ as the composition of two rotations is another rotation $e^{i\frac{\theta_1+\theta_2}{2}} R_{\vec{n}}(\phi_i)$, whose rotation angle $\phi_i$ satisfies:
\begin{equation}\label{eq:phi_i}
    \cos\phi_i = \cos\frac{\theta_1+\theta_2}{2} + 2\sin\frac{\theta_1}{2} \sin\frac{\theta_2}{2}\, \lambda_i,
\end{equation}
where $\lambda_i:=\sin^2\frac{\gamma_i}{2}=\frac{i(N+1-i)}{(N-r)(r+1)}$. Note that Eq.~\eqref{eq:inner_angle1} is equivalent to
\begin{equation}\label{eq:inner_angle2}
    \phi_1 = \pi \pm (1-\frac{2}{c})\frac{\pi}{t_2}, \quad \phi_2 = \pi \pm \frac{\pi}{t_2}.
\end{equation}
Therefore $c t_2 \phi_i \equiv 0 \mod 2\pi$ ( $c=10$ is even). From the composition lemma of two rotations and mathematical induction, we have
\begin{equation}\label{eq:rotate_composition}
    R_{\vec{n}}^k(\phi) = R_{\vec{n}}(k\phi).
\end{equation}
Note that $R_{\vec{n}}(\phi)=I$ when $\phi \equiv 0 \mod 2\pi$. Hence, the effect of $u^{ct_2}$ on the three invariant subspace $\{ \ket{\psi_0} \}$, $\text{span}\{A\ket{w_1},A\ket{w_1}^\perp\}$ and $\text{span}\{A\ket{w_2},A\ket{w_2}^\perp\}$, up to the irrelevant global phase $e^{i\, ct_2\frac{\theta_1+\theta_2}{2}}$, are $e^{i\, ct_2\frac{\theta_1+\theta_2}{2}}I,\ I$ and $I$, respectively. This completes the proof of Lemma~\ref{lem:inner_effect}.
\end{proof}

The intuition behind Eq.~\eqref{eq:inner_angle2} can be interpreted as the minute hand ($\phi_2$) catching up with the hour hand ($\phi_1$) on a watch [considering the case that `$\pm$' is `$+$' in Eq.~\eqref{eq:inner_angle2}].
As $\cos\phi_i$ is linear in $\lambda_i$, the rotation angle $\phi_i$ will never be equal since $\lambda_1$ and $\lambda_2$ differs. We let the difference between $\phi_1$ and $\phi_2$ to be $\frac{2\pi}{ct_2}$, and let the difference between $\phi_2$ and $\pi$ to be $\frac{\pi}{t_2}$,
so that after $ct_2$ iterations, $\phi_1$ is slower than $\phi_2$ for an entire cycle, and $\phi_2$ is faster than $\pi$ for $c/2$ cycle. Hence, $c t_2 \phi_i \equiv 0 \mod 2\pi$ as desired.
More importantly, setting iteration number $ct_2$ according to Eq.~\eqref{eq:inner_iter1} guarantees that the equations \eqref{eq:inner_angle2} about $\theta_1,\theta_2$ have a solution. This is shown in the following lemma.

\begin{lemma}\label{thm:inner_exist}
When $N\geq 5, c=10$, and $t_2 \geq \frac{\pi}{2} \sqrt{r}$,
there exist solutions $\theta_1,\theta_2$ to Eq. \eqref{eq:inner_angle1}. One of the solutions satisfies $\frac{\theta_1+\theta_2}{2} =\pi - d \frac\pi{t_2}$, where the intermediate variable $d$ has two properties: $cd\pi$ is not an integer multiple of $2\pi$; and when $N\to \infty$, $d \to \sqrt{c^2-8(c-1)}/c =\sqrt{7}/5$.
This solution can be obtained by solving Eq.~\eqref{eq:first} first for $d$, and then substitute it into Eq.~\eqref{eq:second} to obtain $\theta_1$, and finally let $\theta_2=2(\pi-d\pi/t_2)-\theta_1$.
\end{lemma}

\begin{proof}
See Appendix \ref{proof:inner_exist}.
\end{proof}

According to Lemma~\ref{thm:inner_exist}, when $N\to \infty$, the effect of $u^{ct_2}$ multiplies $\ket{\psi_0}$ by a relative phase
\begin{equation}\label{eq:infty_beta}
    e^{-cdi\pi}=e^{ -2\sqrt{7}i\pi} \approx e^{ -1.29 i\pi},
\end{equation}
and the claim that $cd\pi$ is not an integer multiple of $2\pi$ guarantees $u^{ct_2}\neq I$.

\subsection{Exact quantum search with arbitrarily given phase rotation}\label{sec:FXR}

In this subsection, we will transform the initial state $\ket{\psi_0}$ to $\ket{T}$ in $\mathcal{H}_0$ by appropriately setting the angle $\alpha$ in $R_T(\alpha)$, with the help of the FXR method \cite{FXR}.

Let $\beta =-( c\cdot t_2 \frac{\theta_1+\theta_2}{2} \mod 2\pi)=(cd\pi \mod 2\pi)$, then by Eq.~\eqref{eq:Rt} and Lemma~\ref{lem:inner_effect}, the effect of $R_T(\alpha)$ and $u^{ct_2}$ in $\mathcal{H}_0$ are
\begin{equation}
    I-(1-e^{i\alpha})\ket{T}\bra{T} =: S_o(\alpha),
    \quad
    I-(1-e^{-i\beta})\ket{\psi_0}\bra{\psi_0} =: S_r(\beta),
\end{equation}
respectively. Recall from Eq.~\eqref{eq:psi_0} that $\braket{T|\psi_0} = \sqrt{\frac{r(r-1)}{N(N-1)}} =: \sqrt{\lambda}$.
Thus we might as well let $\ket{\psi_0} = \sqrt{1-\lambda} \ket{R} + \sqrt{\lambda}\ket{T}$, where $\ket{R}\in \text{span}\{\ket{T},\ket{\psi_0}\}$ and is perpendicular to $\ket{T}$.
We denote by $\mathcal{H}_1 := \text{span}\{\ket{R},\ket{T}\}$ the $2$-dimensional invariant subspace of $u^{ct_2}R_T(\alpha) = S_r(\beta) S_o(\alpha)$. Note that $S_r(\beta) S_o(\alpha)$ is the generalized Grover's operator $G(\alpha,\beta)$, where $S_o$ is the `oracle' operator, and $S_r$ is the diffusion operator.

Just as the calculation step of Theorem 2 in \cite{FXR}, by repeatedly using the composition lemma of two rotations, we find that the effect of
\begin{equation}
    F_{xr,\beta}:= G(\alpha_2,\beta) G(\alpha_1,\beta),
\end{equation}
which is now the effect of one iteration of the outer loop (step 3 in Algorithm~\ref{alg:main_block}),
is a rotation $e^{i(\frac{\alpha_1+\alpha_2}{2}-\beta)} R_{\vec{n}}(\phi)$ on the Bloch sphere of $\mathcal{H}_1$. The rotation angle $\phi$ satisfies Eq.~\eqref{eq:cos_phi_def}, and the axis $\vec{n}$ are as follows:
\begin{align}
    \sin\phi\, n_x &= 2\sqrt{\lambda(1-\lambda)} (\cos\frac{\alpha_1}{2} \cos\frac{\alpha_2}{2} \sin\beta - 2(1-2\lambda) \cos\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2}), \label{eq:sinnx1}\\
    \sin\phi\, n_y &= 2\sqrt{\lambda(1-\lambda)} ( -\sin\frac{\alpha_1}{2} \cos\frac{\alpha_2}{2} \sin\beta + 2(1-2\lambda) \sin\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2} ), \label{eq:sinny1}\\
    \sin\phi\, n_z &= \sin\frac{\alpha_1}{2} \cos\frac{\alpha_2}{2} \cos\beta +\cos\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2}
    \notag \\ &\qquad
    +(1-2\lambda) \cos\frac{\alpha_1+\alpha_2}{2} \sin\beta  -2(1-2\lambda)^2 \cos\frac{\alpha_1}{2} \sin\frac{\alpha_2}{2} \sin^2\frac{\beta}{2} \label{eq:sinnz1}.
\end{align}

Transforming $\ket{\psi_0}$ to $\ket{T}$ in $\mathcal{H}_1$ is then equivalent to the equation $0 = \bra{R} R^k_{\vec{n}}(\phi) \ket{\psi_0}$. By setting the equation's real and imaginary part both to be zero, and with the help of Eq.~\eqref{eq:rotate_composition}, we obtain the equations that parameters $(k=t_1,\alpha_1,\alpha_2)$ need to satisfy:
\begin{align}
0 &= \sqrt{1-\lambda} \cos{k\phi} - \sqrt{\lambda} \sin{k\phi}\ n_y, \label{real1} \tag{real 1}\\
0 &= \sqrt{1-\lambda}\ n_z + \sqrt{\lambda}\ n_x. \label{im1} \tag{im 1}
\end{align}
Substituting Eqs.~\eqref{eq:sinnx1}-\eqref{eq:sinnz1} into the above two equations then leads to Eqs.~\eqref{eq:real1},\eqref{eq:im1}.

Let $\phi_0 = |4\arcsin(\sqrt{\lambda}\sin\frac{\beta}{2}) \mod [-\frac{\pi}{2},\frac{\pi}{2}]|$, then Theorem 2 in \cite{FXR} shows that the above equations possess a solution when $k>\pi/\phi_0$. This explains the value of $t_1$ shown in Eq.~\eqref{eq:outer_iter1}.

\subsection{Query lower bound}\label{sec:lower_bound}
\begin{lemma}\label{thm:lower}
The deterministic quantum query complexity of Problem~\ref{problem:at_most_1} is $\Omega(N^{2/3})$.
\end{lemma}
\begin{proof}
The easier decision problem of Problem~\ref{problem:at_most_1}, i.e. to determine whether elements in $(x_1,x_2,\ldots,x_N)\in [M]^N$ are all distinct, is in fact the evaluation of partial Boolean function $f:\mathcal{D}\to \{0,1\}$, whose domain $\mathcal{D}\subseteq [M]^N$ consists of two parts: $f^{-1}(1)=\{x\in[M]^N : x\ \text{contains a single colliding pair} \}$, and $f^{-1}(0)=\{x\in[M]^N : \text{elements in}\ x\ \text{are all distinct} \}$.
We therefore need only to show that the deterministic quantum query complexity of evaluating $f$ is $\Omega(N^{2/3})$.
Let $Q_{\epsilon}(f)$ be the bounded-error quantum query complexity of evaluating $f$. Bounded-error means to output the correct answer with probability $1-\epsilon$, where $0\leq\epsilon<1/2$. According to Theorem 2 in \cite{hoyer2007negative},
\begin{equation}
    Q_{\epsilon}(f)\geq \frac{1-2\sqrt{\epsilon(1-\epsilon)}}{2} \text{ADV}^\pm (f),
\end{equation}
where $\text{ADV}^\pm (f)$ is the negative-weight adversary lower bound of $f$. Hence, by letting $\epsilon=0$, we know that the deterministic quantum query complexity of evaluating $f$ is at least $\text{ADV}^\pm (f)/2$. The definition of $\text{ADV}^\pm (f)$ is
\begin{equation}
    \text{ADV}^\pm (f) = \max_{\Gamma\in \mathcal{M}} \frac{||\Gamma||}{\max_{i\in[n]} ||\Gamma \circ \Delta_i||},
\end{equation}
where $\mathcal{M}$ are the set of all the nonzero real matrices, whose row indices composed of elements in $f^{-1}(1)$, and whose column indices composed of elements in  $f^{-1}(0)$; element $(x,y)$ in the $0-1$ matrix $\Delta_i\in\mathcal{M}$ equals $1$ if and only if $x_i\neq y_i$; notation $\circ$ is the Hadamard product, and $||\cdot||$ is the spectral norm.

It has been shown respectively in \cite{belovs2012adversary} and \cite{rosmanis2014quantum} that when $M=\Omega(N^2)$ and $M=N$, the lower bound of $\text{ADV}^\pm (f)$ are both $\Omega(N^{2/3})$.
The proof in \cite{rosmanis2014quantum} does not follow the idea in \cite{belovs2012adversary} of emending the adversary matrix $\Gamma$ into some bigger matrix related to the Hamming association scheme, and therefore it breaks the restriction of $M=\Omega(N^2)$. It's also said in \cite{rosmanis2014quantum} that its proof can be generalized to any $M\geq N$, thus the deterministic quantum query complexity of Problem~\ref{problem:at_most_1} is $\Omega(N^{2/3})$.
\end{proof}

\section{Conclusion and future work}
In this paper, we have designed an exact quantum algorithm with query complexity $\Theta(N^{2/3})$ that solves the promised element distinctness  problem with at most one colliding pair. The algorithm utilize Jordan's lemma about common invariant subspaces, and the recently proposed FXR method for exact quantum search with arbitrary phase rotations, so as to achieve certainty of success. In contrast, previous algorithms based on the analysis of asymptotic behaviours of eigenvalues of quantum walk search  could not achieve 100\% success.
Whether the idea in this paper could be applied to other  quantum walk search problem is a possible direction for future research.
\bibliographystyle{unsrt}


\section{Proof of Theorem \ref{thm:hardyjm}}
 A key argument in our proof is given by the following well known version of Shur test
\begin{prop}\label{shurtest}cLet $\alpha_{N,R}\geq 0$, with $N,R\in 2^{\mathbb{Z}}$, $1<q<\infty$, then
$$\sum_R\left(\sum_N \alpha_{N,R} C_N \right)^q\lesssim \sum_N \left(C_N\right)^{q}$$
provided there exists a sequence of positive numbers $p_N$ such that
\begin{eqnarray}
 \left(\sum_N \alpha_{N,R} p_N^{\frac{q'}{q}}\right)^{\frac{q}{q'}}\lesssim p_R\label{shur1}\\
 \sum_R \alpha_{N,R} p_R\lesssim p_N. \label{shur2}
\end{eqnarray}
\end{prop}
\begin{proof}

By Holder's inequality with conjugated exponent $(q, q')$
$$\sum_N \alpha_{N,R} C_N =\sum_N \alpha_{N,R}^{\frac{1}{q}}\alpha_{N,R}^{\frac{1}{q'}} p_N^{\frac{1}{q}}\frac{C_N}{p_N^{\frac{1}{q}}} \leq  \left(\sum_N \alpha_{N,R} p_N^{\frac{q'}{q}}\right)^{\frac{1}{q'}}  \left(\sum_N \alpha_{N,R} \frac{C_N^q}{p_N}\right)^{\frac{1}{q}}$$
we get
$$\sum_R\left(\sum_N \alpha_{N,R} C_N \right)^q\leq \sum_R \left(\sum_N \alpha_{N,R} p_N^{\frac{q'}{q}}\right)^{\frac{q}{q'}}  \left(\sum_N \alpha_{N,R} \frac{C_N^q}{p_N}\right)$$
that, thanks to \eqref{shur1} and Fubini, implies
$$\sum_R\left(\sum_N \alpha_{N,R} C_N \right)^q\lesssim \sum_R p_R  \left(\sum_N \alpha_{N,R} \frac{C_N^q}{p_N}\right)=\sum_N \frac{C_N^q}{p_N}\left(\sum_R \alpha_{N,R}p_R \right).$$
Now by \eqref{shur2} we conclude
$$\sum_R\left(\sum_N \alpha_{N,R} C_N \right)^q\lesssim \sum_N \frac{C_N^q}{p_N} p_N=\sum_N C_N^q.$$
\end{proof}

The strategy of the proof for  is an adaptation of  proof of Hardy inequality in the case $q=2$ given by Tao \cite{T}, i.e.  to prove the following estimate
\begin{equation}\label{assump1}
\int_{\mathbb{R}^d}\frac{|f(x)|^q}{|x|^{sq}}dx \lesssim  \sum_N N^{qs} ||P_N f||_{L^q(\mathbb{R}^d)}^q
\end{equation}
where $P_N f$ are the classical Littlewood-Paley projectors with $N$ a dyadic number.

We devide $\mathbb{R}^d$ in dyadic shells obtaining

\begin{equation}
    \int_{\mathbb{R}^{d}}\frac{\vert f(x) \vert^{q}}{\vert x \vert^{qs}}\,dx = \sum_{R \in 2^{\mathbb{Z}}} \int_{\frac{R}{2}\leq \vert x \vert \leq R} \frac{\vert f(x)\vert^{q}}{\vert x\vert^{qs}}\,dx \lesssim \sum_{R \in 2^{\mathbb{Z}}} \frac{1}{R^{sq}}\,\int_{\{\frac{R}{2}\leq \vert x \vert\leq R\}} \vert f \vert^q \, dx. \label{primopasdisug:cap6}
\end{equation}
such that using the Littlewood-Paley decomposition we get
\begin{equation}
    \sum_{R \in 2^{\mathbb{Z}}} \frac{1}{R^{sq}}\,\int_{\{\frac{R}{2}\leq \vert x \vert\leq R\}} \vert f \vert^q \, dx\leq \sum_{R \in 2^{\mathbb{Z}}} R^{-sq}\, \left( \sum_{N \in 2^{\mathbb{Z}}}  \left( \int_{\{\vert x \vert \leq R\}} \vert P_{N}(f) \vert^{q} \right)^{\frac{1}{q}} \right)^{q}.
\end{equation}
By the Bernstein inequality $||P_{N}(f)||_{L^{\infty}(\mathbb{R}^d)}\leq N^{\frac{d}{q}}||P_{N}(f)||_{L^{q}(\mathbb{R}^d)}$
it follows that
\begin{equation}
    \left( \int_{\frac{R}{2}<\vert x \vert< R} \vert P_{N}(f) \vert^{q} \right)^{\frac{1}{q}} \leq R^{\frac{d}{q}}\Vert P_{N}(f) \Vert_{L^{\infty}} \\
    \leq (NR)^{\frac{d}{q}} \Vert P_{N}(f) \Vert_{L^{q}},
\end{equation}
and clearly
\begin{equation*}
    \left( \int_{\frac{R}{2}<\vert x \vert< R} \vert P_{N}(f) \vert^{q} \right)^{\frac{1}{q}} \leq \Vert P_{N}f \Vert_{L^q},
   \end{equation*}
such that we get
$$
 \int_{\mathbb{R}^{d}}\dfrac{\vert f(x)\vert^{q}}{\vert x \vert^{qs}} dx\lesssim \sum_{R}R^{-qs} \left( \sum_{N} \min\{ 1,(NR)^{\frac{d}{q}}\}\, \Vert P_{N}f \Vert_{L^{q}} \right)^{q} \notag \\
=$$
$$=\sum_{R}\left(\sum_{N} \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}\, \Vert \, N^{s}\,P_{N}f \Vert_{L^{q}}\right)^{q}.$$

The last step is to apply the Schur test given by Proposition \ref{shurtest} in order to conclude that
$$
    \sum_{R}\left(\sum_{N} \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}\, \Vert \, N^{s}\,P_{N}f \Vert_{L^{q}}\right)^{q} \leq \sum_{N \in 2^{\mathbb{Z}}} N^{sq}\, \Vert P_{N}(f) \Vert_{L^{q}}^{q}\notag\\
    =$$
    $$=\sum_{N \in 2^{\mathbb{Z}}}N^{sq}\,\int_{\mathbb{R}^{d}}\vert P_{N}(f)\vert^{q}=\int_{\mathbb{R}^{d}} \sum_{N \in 2^{\mathbb{Z}}} N^{sq}\vert P_{N}(f)\vert^{q}. $$
Notice that
\begin{eqnarray}
 \sum_{N>\frac{1}{R}}  \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}+\ \sum_{N\leq \frac{1}{R}}  \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}= \nonumber\\
= R^{-s}  \sum_{N>\frac{1}{R}}  N^{-s}+R^{\frac{d}{q}-s} \sum_{N\leq \frac{1}{R}} N^{\frac{d}{q}-s}\lesssim 1 \nonumber
\end{eqnarray}
such that (arguing in the same way when summing over $R$)
  \begin{eqnarray}
 \sum_N  \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}  \lesssim 1\\
 \sum_R  \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\}  \lesssim 1. \end{eqnarray}
The hypoteses for Shur test  given by Proposition \ref{shurtest} are hence fulfilled by choosing $\alpha_{N,R}=  \min\{ (NR)^{-s},(NR)^{\frac{d}{q}-s}\} $ and $p_N=1$ in Proposition \ref{shurtest}.
 This proves \eqref{eq:hardy}.
 \\

\section{Proof of Corollary \ref{cor:hardyjm}}
In Theorem \ref{thm:hardyjm} we proved the  following estimate
\begin{equation}\label{assump1}
\int_{\mathbb{R}^d}\frac{|f(x)|^q}{|x|^{sq}}dx \lesssim  \sum_N N^{qs} ||P_N f||_{L^q(\mathbb{R}^d)}^q
\end{equation}
where $P_N f$ are the classical Littlewood-Paley projectors with $N$ a dyadic number.  First we prove that \eqref{assump1} implies the Fractional Hardy inequality.
We have two cases: $q\geq 2, q<2$.\\
Case $q\geq 2$:\\

Thanks to  \eqref{assump1}
we derive
$$\sum_N N^{qs} ||P_N f||_{L^q(\mathbb{R}^d)}^q=\int_{\mathbb{R}^d} \sum_N N^{sq}|P_N f(x)|^q dx \leq  \int_{\mathbb{R}^d} \left(\sum |N^s P_N f(x)|^2\right)^{\frac{q}{2}} dx  $$
from the elementary inequality $\left(\sum_i a_i^{p_1}\right)^{\frac{1}{p_1}}\leq \left(\sum_i a_i^{p_2}\right)^{\frac{1}{p_2}}$ with $p_1\geq p_2,$
obtaining $$\int_{\mathbb{R}^d}\frac{|f(x)|^q}{|x|^{sq}}dx \lesssim \sum_N N^{qs} ||P_N f||_{L^q(\mathbb{R}^d)}^q\leq $$
$$ \leq  \int_{\mathbb{R}^d} \left(\sum_N |N^s P_N f(x)|^2\right)^{\frac{q}{2}} dx \sim |||D|^s f||_{L^q(\mathbb{R}^d)}^q$$
where the last equivalence is nothing but the classical square function estimate, see for instance \cite{MS}.\\
To prove \eqref{eq:hardy3} we notice that
$$\int_{\mathbb{R}^d} \sum_N N^{sq}|P_N f(x)|^q dx\leq $$
$$\leq \int_{\mathbb{R}^d} \left( \sum_N N^{2s}|P_N f(x)|^2 \right)^{\frac 12} \left( \sum_N N^{2s(q-1)}|P_N f(x)|^{2(q-1)} \right)^{\frac 12}dx \leq$$
$$\leq  \left(\int_{\mathbb{R}^d} \left( \sum_N N^{2s}|P_N f(x)|^2 \right)^{\frac q2}dx\right)^{\frac 1q}\left(\int_{\mathbb{R}^d} \left( \sum_N N^{2s(q-1)}|P_N f(x)|^{2(q-1)} \right)^{\frac{q}{2(q-1)}}dx\right)^{\frac{q-1}{q}}$$
by applying  twice the  Holder's inequality, first  in the serie with conjugated exponent $(2, 2)$ and then in the integral  with conjugated exponent $(q, \frac{q}{q-1})$.
By definition
$$\left(\int_{\mathbb{R}^d} \left( \sum_N N^{2s(q-1)}|P_N f(x)|^{2(q-1)} \right)^{\frac{q}{2(q-1)}}dx\right)^{\frac{q-1}{q}}=||f||_{\dot F^s_{q, 2(q-1)}}^{q-1}.$$
\\
Case $q< 2$:\\
For the case $q <2$ we use the dual characterization of $L^q$ norms, i.e.

\begin{gather*}
    \Vert \frac{f}{\vert x \vert^{s}} \Vert_{L^{q}}=\sup_{\Vert g \Vert_{q'}=1} \langle \frac{ f(x)}{\vert x \vert^{s}},\,g \rangle= \sup_{\Vert g \Vert_{q'}=1}\, \langle f(x),\, \frac{g(x)}{\vert x \vert^{s}}\rangle\\
    =\sup_{\Vert g \Vert_{q'}=1}\, \langle \vert D \vert^{-s}(\vert D \vert^{s}  f(x)),\, \frac{g(x)}{\vert x \vert^{s}}\rangle= \sup_{\Vert g \Vert_{q'}=1} \langle \vert D \vert^{s}f ,\, \vert D \vert^{-s}(\frac{g(x)}{\vert x \vert^{s}})\rangle\\
    \leq \, \Vert \vert D \vert^{s}f \Vert_{L^{q}}\, \Vert \vert D \vert^{-s}(\frac{g(x)}{\vert x \vert^{s}})\Vert_{L^{q'}}.
\end{gather*}

Now we aim to prove that

\begin{equation}\label{eq:sw2}
   \Vert \vert D \vert^{-s}(\frac{g(x)}{\vert x \vert^{s}})\Vert_{L^{q'}(\mathbb{R}^d)} \lesssim \Vert g\Vert_{L^{q'}(\mathbb{R}^d)},
\end{equation}
for all  $g \in L^{q'}$ with $q'>2$ such that
we could conclude that
\begin{gather*}
\Vert \frac{f}{\vert x \vert^{s}} \Vert_{L^{q}(\mathbb{R}^d)}=\sup_{\Vert g \Vert_{q'}=1} \langle \frac{\vert f(x)\vert}{\vert x \vert^{s}},\,g \rangle  \lesssim  \Vert D \vert^{s}f \Vert_{L^{q}(\mathbb{R}^d)}.
\end{gather*}

Now we prove \eqref{eq:sw2}. We have (skipping $q'$ with $q$ to simplify the notation)
\begin{gather*}
    \vert D \vert^{-s}(\frac{g(x)}{\vert x \vert^{s}})\vert^q  \sim \left\vert \int_{\mathbb{R}^{d}} \frac{g(y)}{\vert x-y\vert^{d-s}\,\vert y \vert^{s}}\,dy   \right\vert^{q} \leq \left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert}{\vert y \vert^{s}\, \vert x-y \vert^{d-s}} \,dy \right\vert^{q}\\
\lesssim \left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert\, \mathbbm{1}_{\{ \vert y \vert > \frac{\vert x\vert}{2}\}}(y) }{\vert y \vert^{s}\, \vert x-y\vert^{d-s}} dy\right\vert^{q}+\left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert\, \mathbbm{1}_{\{ \vert y \vert \leq \frac{\vert x\vert}{2}\}}(y) }{\vert y \vert^{s}\, \vert x-y\vert^{d-s}} dy\right\vert^{q}\\
\lesssim \frac{1}{\vert x \vert^{qs}}\, \left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert\, \mathbbm{1}_{\{ \vert y \vert > \frac{\vert x\vert}{2}\}}(y) }{ \vert x-y\vert^{d-s}} dy\right\vert^{q}+\left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert\, \mathbbm{1}_{\{ \vert y \vert \leq \frac{\vert x\vert}{2}\}}(y) }{\vert y \vert^{s}\, \vert x-y\vert^{d-s}} dy\right\vert^{q}\\
\lesssim \frac{1}{\vert x \vert^{qs}}\, \left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert}{ \vert x-y\vert^{d-s}}dy \right\vert^{q}+\left\vert \int_{\mathbb{R}^{d}} \frac{\vert g(y)\vert\, \mathbbm{1}_{\{ \vert y \vert \leq \frac{\vert x\vert}{2}\}}(y) }{\vert y \vert^{s}\, \vert x-y\vert^{d-s}}dy \right\vert^{q}\\
:=\vert S_{1}(g) \vert^{q}+\vert S_{2}(g)\vert^{q}
\end{gather*}

By  previous estimates using Paley-Littlewood decompostion and the square function equivalence we get
when $q>2$
\begin{gather*}
    \int_{\mathbb{R}^{d}}\vert S_{1}(g)\vert^{q}\,dx\sim \int_{\mathbb{R}^{d}}\left\vert \frac{\vert D\vert^{-s}\vert g(x)\vert }{\vert x\vert^{s}} \right\vert^{q}\,dx \lesssim \left\Vert \vert D \vert^{s}(\vert D \vert^{-s}|g|) \right\Vert_{L^{q}(\mathbb{R}^d)}^q=\Vert g\Vert_{L^{q}(\mathbb{R}^d)}^q.
\end{gather*}

Concerning  $\Vert S_{2}(g)\Vert_{L^q}$ we follow the strategy of Stein and Weiss in \cite{SW}  proving the $L^q$ continuity for singular homogeneous kernels of degree -$d$. The proof of this fact is Lemma 2.1 in \cite{SW} that we show for reader convenience.
First notice that $\frac{\vert y \vert}{\vert x \vert}\leq \frac{1}{2}$ implies
\begin{gather*}
    \vert x-y\vert \geq \vert x \vert - \vert  y \vert \geq \frac{\vert x \vert}{2},
\end{gather*}
such that
\begin{gather}
    \int_{\vert y \vert \leq \frac{\vert x \vert}{2}} \frac{\vert g(y)\vert}{\vert x-y\vert^{d-s}\vert y\vert^{s}}\, dy \lesssim \int_{\vert y \vert \leq \frac{\vert x \vert}{2}} \frac{\vert g(y)\vert}{\vert y \vert^{s}\, \vert x\vert^{d-s}}\,dy. \label{weiss:intdastim}
\end{gather}
Now we introduce following \cite{SW} the function,
\begin{gather*}
    K(x,y)=\begin{cases}
    \vert y \vert^{s}\,\vert x \vert^{d-s} \quad \vert y \vert \leq \frac{\vert x \vert}{2}\\
    0 \quad \text{otherwise}
    \end{cases}
\end{gather*}
and
\begin{gather*}
    Ug(x):=\int_{\vert y \vert \leq \frac{\vert x}{2} \vert} \frac{\vert g(y)\vert}{\vert y \vert^{s}\, \vert x\vert^{d-s}}\,dy=\int_{\mathbb{R}^{d}} K(\vert x\vert,\,\vert y \vert)|g(y)|\,dy.
\end{gather*}
To conclude the proof it suffices hence to show that
\begin{gather*}
    \int_{\mathbb{R}^{d}} \vert Ug \vert^{q}dx \lesssim \int \vert g \vert^{q} dx.
\end{gather*}
Fixing  $\eta \in S^{d-1}$ and calling  $\vert x\vert=R$ we define
\begin{gather*}
    U_{\eta}g(R):=\int_{0}^{+\infty} \,r^{d-1}\, K(R,r)\cdot |g(r\,\eta)|dr,
\end{gather*}
such that
\begin{gather*}
Ug(x)=\int_{\mathbb{R}}K(\vert x\vert,\vert y \vert)|g(y)|dy=\int_{0}^{+\infty} \left(\int_{S^{d-1}} \hspace{-8pt} K(R,r)|g(r\,\eta)|\,d\sigma_{\eta}\right)\,r^{d-1}\,dr\\
=\int_{S^{d-1}}\int_{0}^{+\infty} \hspace{-8pt}K(R,r)|g(r\eta)|\,r^{d-1}\,dr\,d\sigma_{\eta}=\int_{S^{d-1}} U_{\eta}g(R)\,d\sigma_{\eta}.
\end{gather*}

By the substitution $r=tR$ we obtain
\begin{gather*}
   \hspace{-3cm}U_{\eta}g(R) = \int_{0}^{+\infty}\hspace{-8pt} K(R,Rt)\,|g(t\,R\,\eta)|\,R^{d-1}\,t^{d-1}\,R\,dt\\
   =\int_{0}^{+\infty}\hspace{-8pt}K(1,t)\,|g(t\,R\,\eta)|t^{d-1}\,dt,
\end{gather*}
thanks to the fact that  $K$ is homogeneous of degree $-d$ , i.e. that
\begin{gather*}
    K(\lambda x,\,\lambda y)=\vert \lambda \vert^{-d}K(\vert x\vert,\vert y\vert).
\end{gather*}
Let  $h$ be the function in  $L^{q'}((0,+\infty);R^{d-1}\,dR)$ of unitary norm  such that
\begin{gather*}
    \left( \int_{0}^{+\infty} \vert U_{\eta}g(R)\vert^{q}\,R^{d-1}\,dR \right)^{\frac{1}{q}}=\int_{0}^{+\infty} \hspace{-8pt}U_{\eta}g(R)h(R)\,R^{d-1}\,dR\\
    =\int_{0}^{+\infty} \left\{ \int_{0}^{+\infty}K(1,t)\,\vert g(t\,R\,\eta)\vert \,t^{d-1}\,dt \right\}\,R^{d-1}\,h(R)\,dR\\
    =\int_{0}^{+\infty} \hspace{-8pt} K(1,t)\,t^{d-1} \left\{ \int_{0}^{+\infty} \hspace{-8pt}\vert g(tR\eta) \vert\, h(R)\,R^{d-1}\,dR \right\}\,dt\\
    \leq \int_{0}^{+\infty}K(1,t)\,t^{d-1} \left\{\int_{0}^{+\infty}\vert g(t\,R\,\eta)\vert^{q}\,R^{d-1}\,dR  \right\}^{\frac{1}{q}}\,dt\\
    =\left( \int_{0}^{+\infty}\hspace{-8pt} K(1,t)t^{d-1-\frac{d}{q}}\,dt \right)\cdot \left\{ \int_{0}^{+\infty}\hspace{-8pt} \vert g(R\eta)\vert^{q}\,R^{d-1}\,dR\right\}^{\frac{1}{q}}\\
    =\left(\int_{0}^{1}t^{d-\frac{d}{q}-1-s}\,dt\right)\cdot \left\{ \int_{0}^{+\infty} \hspace{-8pt} \vert g(R\eta)\vert^{q}\,R^{d-1}\,dR\right\}^{\frac{1}{q}}=:J\cdot \left\{ \int_{0}^{+\infty} \hspace{-8pt} \vert g(R\eta)\vert^{q}\,R^{d-1}\,dR\right\}^{\frac{1}{q}} ,
\end{gather*}
where the last integral  $J$ converges due to the fact that by our assumptions  $s <\frac{d}{q'}$ (remember that we skipped $q'$ with $q$).

Now we estimate $L^{q}(\mathbb{R}^{d})$ norm of $Ug. $ By Jensen inequality
\begin{gather*}
    \vert Ug(R) \vert^{q}=\left\vert \int_{S^{d-1}} \vert U_{\eta}g(R)\vert\,d\sigma_{\eta} \right\vert^{q} \leq \{\vert S^{d-1}\vert \}^{q-1}\,\int_{S^{d-1}} \vert U_{\eta}g\vert^{q}\,d\sigma_{\eta},
\end{gather*}
such that integrating with respect to the measure  $R^{d-1}dR$ we get
\begin{gather*}
    \hspace{-4cm}\int_{0}^{+\infty} \hspace{-5pt}\vert Ug(R) \vert^{q}R^{d-1}\,dR
    \leq \\
    \leq J^{q}\,\vert S^{d-1} \vert^{q-1}\left( \int_{0}^{+\infty} \left\{ \int_{S^{d-1}} \hspace{-5pt} \vert U_{\eta}g(R)\vert^{q}\,d\sigma_{\eta} \right\}\,R^{d-1}\,dR \right)\\
    =J^{q}\,\vert S^{d-1} \vert^{q-1}\,\int_{S^{d-1}}\int_{0}^{+\infty} \vert U_{\eta}g(R) \vert^{q}\,R^{d-1}\,dR \, d\sigma_{\eta}\\
    \leq J^{q}\,\vert S^{d-1} \vert^{q-1}\, \int_{S^{d-1}}\int_{0}^{+\infty}\vert g(R\,\eta) \vert^{q}\,R^{d-1}\,dR\,d\sigma=J^{q}\,\vert S^{d-1}\vert^{q-1}\,\int_{\mathbb{R}^{d}}\vert g(x)\vert^{q}\,dx.
\end{gather*}
By the fact that  $Uf(x)$ is radial we can conclude that
\begin{gather*}
    \int_{\mathbb{R}^{d}} \vert Ug(x) \vert^{q}\,dx =\vert S^{d-1} \vert\cdot \int_{0}^{+\infty}\vert Ug(R)\vert^{q}\,R^{d-1}\,dR \leq J^{q}\vert S^{d-1}\vert^{q}\,\int \vert g(x)\vert^{q}\,dx.
\end{gather*}
This concludes the proof in the case $q<2$.
\\
\\
\textbf{DECLARATIONS}\\
\\
\noindent \textbf{Conflict of interest}. The authors declare that they have no conflict of interest.


\section*{\bf References}

\bibitem{Thouless}  D. J. Thouless, Quantization of particle transport, \textit{Phys. Rev. B} {\bf 27}, 6083 (1983).

\bibitem{MiChaNiu2010} D. Xiao, M.-C. Chang, Q. Niu,  Berry phase effects on electronic properties, \textit{Rev. Mod. Phys.} {\bf 82}, 1959 (2010).

\bibitem{SMaC} M. Switkes, C. M. Marcus, K. Campman, A. C. Gossard, An Adiabatic Quantum Electron Pump, \textit{Science} {\bf 283}, 1905-1908 (1999).

\bibitem{spin} W. Ma, L. Zhou, Q. Zhang, M. Li, C. Cheng, J. Geng, X. Rong,  F. Shi, J. Gong, J. Du, Experimental observation of a generalized thouless pump with a single spin, \textit{ Phys. Rev. Lett.} {\bf 120}, 120501 (2018).

\bibitem{KraLaRin2012} Y. E. Kraus, Y. Lahini, Z. Ringe, M. Verbin, O. Zilberberg,
Topological States and Adiabatic Pumping in Quasicrystals, \textit{ Phys. Rev. Lett.} {\bf 109}, 106402 (2012).

\bibitem{CeWaShe2020} A. Cerjan, M. Wang, S. Huang, K. P. Chen, M. C. Rechtsman, Thouless pumping in disordered photonic systems, \textit{Light. Sci. Appl.} {\bf 9}, 178(2020).

\bibitem{ZilHuaJo2018} O. Zilberberg, S. Huang, J. Guglielmon, M. Wang, K. P. Chen, Y. E. Kraus, M. C. Rechtsman, Photonic topological boundary pumping as a probe of 4D quantum Hall physics, \textit{ Nature} {\bf 553}, 59-62 (2018).

\bibitem{LosZilAlBlo2020} M. Lohse, C. Schweizer, O. Zilberberg, M. Aidelsburger, I. Bloch, A Thouless quantum pump with ultracold bosonic atoms in an optical superlattice. \textit{ Nat. Phys.} {\bf 12},350–354 (2016).

\bibitem{LuSAG2016} H.-I Lu, M. Schemmer, L. M. Aycock, D. Genkina, S. Sugawa, I. B. Spielman, Geometrical Pumping with a Bose-Einstein Condensate, \textit{ Phys. Rev. Lett.} {\bf 116}, 200402 (2016).

\bibitem{LoSHa2018} M. Lohse, C. Schweizer, H. M. Price, O. Zilberberg, I. Bloch, Exploring 4D quantum Hall physics with a 2D topological charge pump, \textit{ Nature} {\bf 553}, 55-58 (2018).

\bibitem{NaTaKe2021} S. Nakajima, N. Takei, K. Sakuma, Y. Kuno, P. Marra, Y. Takahashi,
Disorder-induced Thouless pumping of ultracold atoms in an optical lattice, \textit{ arXiv:2007.06817v1 [cond-mat.quant-gas]}  (2020).

\bibitem{NaToTa2016} S. Nakajima, T. Tomita, S. Taie, T. Ichinose, H. Ozawa, L. Wang, M. Troyer, Y. Takahashi, Topological Thouless pumping of ultracold fermions. \textit{ Nat. Phys.} {\bf 12}, 296–300 (2016).

\bibitem{CheProPro2020} W. Cheng, E. Prodan, C. Prodan, Experimental Demonstration of Dynamic Topological Pumping across Incommensurate Bilayered Acoustic Metamaterials, \textit{Phys. Rev. Lett.} {\bf 125}, 224301 (2020).

\bibitem{FedQiLIK2020} Z. Fedorova, H. Qiu, S. Linden, J. Kroha,
Observation of topological transport quantization by dissipation in fast Thouless pumps,
\textit{Nat. Comm.} {\bf 11}, 3758 (2020).

\bibitem{prb1} Y. Zhang, Y. Gao, and D. Xiao, Topological charge pumping in
twisted bilayer graphene, \textit{Phys. Rev. B} {\bf 101}, 041410 (2020).

\bibitem{prb2} M. Fujimoto, H. Koschke, and M. Koshino, Topological charge pumping by a sliding moiré pattern, \textit{Phys. Rev. B} {\bf 101}, 041112 (2020).

\bibitem{prb3} Y. Su and S. Lin, Topological sliding moir\'e heterostructure, \textit{Phys. Rev. B} {\bf 101}, 041113(2020).

\bibitem{MaTeKa} F. Matsuda, M. Tezuka, N. Kawakami, Two-Dimensional Thouless Pumping of Ultracold Fermions in Obliquely Introduced Optical Superlattice, \textit{J. Phys. Soc. Jpn.} {\bf 890}, 114708 (2020).

\bibitem{flat_band} A. H. MacDonald, Bilayer Graphene’s Wicked, Twisted Road, \textit{Physics} {\bf 12}, 12 (2019).

\bibitem{moire-review} D. M. Kennes, M. Claassen, L. Xian, A. Georges, A. J. Millis, J. Hone, C. R. Dean, D. N. Basov, A. N. Pasupathy, A. Rubio, Moir\'e heterostructures as a condensed-matter quantum simulator. \textit{Nat. Phys.} {\bf 17}, 155-163 (2021).

\bibitem{magic} R. Bistritzer, A. H. MacDonald, Moir\'e bands in twisted double-layer graphene, \textit{PNAS} {\bf 108}, 12233-12237 (2011).

\bibitem{UnconvenSupercond} Y. Cao, V. Fatemi, S. Fang, K. Watanabe, T. Taniguchi, E. Kaxiras, P. Jarillo-Herrero, Unconventional superconductivity in magic-angle graphene superlattices, \textit{Nature} {\bf 556}, 43-50 (2018).

\bibitem{MoireNature} P. Wang, Y. Zheng, X. Chen, C. Huang, Y. V. Kartashov, L. Torner, V. V. Konotop, F. Ye, Localization and delocalization of light in photonic moiré lattices, \textit{Nature} {\bf 577}, 42-46 (2020).

\bibitem{LocDeloc} C. Huang, F. Ye, X. Chen, Y. Kartashov, V. V. Konotop, L. Torner, Localization-delocalization wavepacket transition in Pythagorean aperiodic potentials, \textit{Sci. Rep.} \textbf{6}, 32546 (2016).

\bibitem{Efremidis} N. K. Efremidis, S. Sears, D, N. Christodoulides, J. W. Fleischer, M. Segev, Discrete solitons in photorefractive optically induced photonic lattices, \textit{Phys. Rev. E} {\bf 66}, 046602 (2002).

 \bibitem{Fleischer} J. Fleischer, M. Segev, N. Efremidis, D. Christodoulides, Observation of two-dimensional discrete solitons in optically induced nonlinear photonic lattices, \textit{Nature} {\bf 442}, 147-150 (2003).

\bibitem{MoireNP} Q. Fu, P. Wang, C. Huang, Y. V. Kartashov, L. Torner, V. V. Konotop, F. Ye, Optical soliton formation controlled by angle twisting in photonic moir\'e lattices, \textit{ Nat. Phot. } {\bf 14}, 663-668 (2020).

\bibitem{Niu} Q. Niu, Towards a Quantum Pump of Electric Charges, \textit{ Phys. Rev. Lett.} {\bf 64}, 1812-1815 (1990).

\bibitem{review_Wannier} N. Marzari, A. A. Mostof, J. R. Yates, I. Souza, D. Vanderbilt, Maximally localized Wannier functions: Theory and applications,  \textit{Rev. Mod. Phys.} {\bf 84}, 1419-1475 (2012).

\bibitem{WannierPRL} C. Brouder, G. Panati,  M. Calandra, C. Mourougane, N. Marzar, Exponential Localization of Wannier Functions in Insulators, \textit{Phys. Rev. Lett.} {\bf 98}, 046402 (2007).

\bibitem{non-adiabat} L. Privitera, A. Russomanno, R. Citro, G. E. Santoro, Nonadiabatic Breaking of Topological Pumping. \textit{Phys. Rev. Lett.} {\bf 120}, 106601 (2018).

\end{thebibliography}

\paragraph*{\bf Acknowledgments} P. W., Q. F., R. P. and F. Y. acknowledge support from the NSFC (No. 91950120), Scientific funding of Shanghai (No.9ZR1424400), and  Shanghai Outstanding Academic Leaders Plan (No.20XD1402000).
Y.V.K. and L.T. acknowledge support from the Severo Ochoa Excellence Programme (CEX2019-000910-S), Fundacio Privada Cellex, Fundacio Privada Mir-Puig, and CERCA/Generalitat de Catalunya. V.V.K. acknowledges financial support from the Portuguese Foundation for Science and Technology (FCT) under Contracts PTDC/FIS-OUT/3882/2020 and UIDB/00618/2020.

\paragraph*{\bf Author contributions} P. W. and Q. F. contributed equally to this work. All authors (P. W., Q. F., R.P.,Y.K.,L.T., V. K. and F. Y.)contributed significantly to the paper.

\paragraph*{\bf Competing interests} The authors declare no competing interests.

\vspace{12 pt}
{\bf \large Figures}

\begin{figure}[htb]
\centering
\includegraphics[width=0.63\textwidth]{figure1.pdf}
\caption{
{\bf Tilted moir\'e lattices.}
({\bf a}) Schematics of the tilted moir\'e lattice based on a reference square lattice $V(\bm r)$ with primitive translation vectors $a\bf i$ and $a\bf j$, where $a$ is the lattice constant (here set to 1) (i). One of the constitutive sublattices is  obtained by twisting the reference lattice by the angle $\theta$ around the $z-$axis, yielding the potential $V({R}(\theta){\bm r})$ (the red-coloured lattice  in (ii)). The second sublattice is obtained by rotating the reference lattice by an angle $\alpha$ around the $x-$axis (the olive-coloured lattice in (iii)), thus producing the potential
$V({\bm r}-\alpha z \bf j)$. Superimposing $V({\bm r}-\alpha z \bf j)$ and $V({R}(\theta){\bm r})$  results in the moir\'e potential $U$ shown in (iii). The tilted moir\'e lattice has a period $Z$ along the direction of  the incident beam (shown by a dark-red arrow).  ({\bf b}) Cross-sections of the optically induced  moir\'e lattice $U({\bm r},z)$ with $p=0.3$ and $E_0=7$ (upper row) and the instantaneous bandgap structures (lower row) at distances $z=0$, $Z/4$, $Z/2$, and $3Z/4$. The red arrows indicate the primitive translation vectors ${\bm e}_1$ and ${{\bm e}}_2$ of the tilted moir\'e lattice. Blue and red lines in lower row of (b) show the first and second bands in the instantaneous lattice spectrum for the same distances. ({\bf c}) Blue and red lines show the evolution of the bottom edge of the first band and top edge of the second band with distance $z$ on one lattice period $Z$. In (b)  and (c), $\alpha=0.015$.
}
\label{fig:one}
\end{figure}

\begin{figure}[hbt]
\centering
\includegraphics[width=0.75\textwidth]{figure2.pdf}
\caption{
{\bf Numerical simulation of Thouless pumping in a titled moir\'e lattices} with $p=0.3$, Pythagorean angle $\theta=\arctan(4/3)$ ($m=2$, $n=1$) and tilt angles $\alpha=0.002$ (\textbf{a}, \textbf{b}, \textbf{e}) and $\alpha=0.015$ (\textbf{c}, \textbf{d}, \textbf{f},
\textbf{g}).  (\textbf{a}) and (\textbf{c}) Displacements of the light beam COM, $|{\bm r}_c|$, with distance $z$. (\textbf{b}) and (\textbf{d}) trajectories of the COM ${\bm r}_c=(x_c, y_c)$ in the transverse plane. The asterisks correspond to the points $z=Z$, i.e., to one longitudinal lattice period. Lines of different colour correspond to different amplitudes $E_0$ of the moir\'e lattice. Dashed diagonal lines show the evolution of ${\bm R}_{\rm av}(z)$ in (b) and (d), and of its modulus in (a) and (c) upon propagation. The results for classical motion in the potential $U$ are shown by the dark-blue solid lines. The arrows along dotted lines in (b) and (d) show the direction of tilting of one sub-lattice with respect to another one. (\textbf{e}) Snapshots of beam propagation for $\alpha=0.002$ and $E_0=10.0$ (zoom of the initial intensity distribution is shown within white square). (\textbf{f}) and (\textbf{g}) Snapshots of beam propagation for $\alpha=0.015$  and $E_0=7.5$  and $E_0=9.0$, respectively. (\textbf{h}) Evolution of the mean radius of the beam propagating inside tilted moir\'e lattice (red line), a tilted lattice obtained without twisting of two sublattices (green line) with $p=0.3$, and in a single reference lattice (blue line) with depth $p=1.3$ for $\alpha=0.015$. In all cases, $a=\pi$.}
\label{fig:two}
\end{figure}

\begin{figure}[htb]
\centering
\includegraphics[width=1.0\textwidth]{figure3.pdf}
\caption{{\bf Experimental observation of two-dimensional Thouless pumping.} ({\bf a}) Optically induced moir\'e lattices with $I_2/I_1=1.0$ (left column) and $I_2/I_1=0.1$ (right column) at different propagation distances inside the sample. Panels b, c and d correspond to the right column. ({\bf b}) Measured COM displacement $|{\bm r}_c|$ with $z$. ({\bf c}) The measured trajectory ${\bm r}_c=(x_c, y_c)$ in the transverse plane for various voltages applied to the crystal. The arrow along dotted lines shows the direction of the sliding of one sub-lattice with respect to another one. ({\bf d}) Surface and contour plots showing signal beam intensity distributions at different distances insider the sample at $\text{U}_\text{bias}=600$ V. The $x$ and $y$ axes in these distributions are determined by the directions of the primitive translation vectors ${\bm e}_1$ and ${\bm e}_2$. }
\label{fig:three}
 \end{figure}

\end{document}