⇦Chinese Physics Letters, 2020, Vol. 37, No. 5, Article code 050304Express Letter Resonant Quantum Search with Monitor Qubits * Frank Wilczek1,2,3,4,5, Hong-Ye Hu (扈鸿业)6, Biao Wu (吴飙)7,3,8 Affiliations 1Center for Theoretical Physics, MIT, Cambridge, MA 02139, USA 2D. Lee Institute, Shanghai Jiao Tong University, Shanghai 200240, China 3Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China 4Department of Physics, Stockholm University, Stockholm, SE-106 91, Sweden 5Department of Physics, Arizona State University, Tempe, AZ 25287, USA 6Department of Physics, University of Californian, San Diego, CA 92093, USA 7International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China 8Collaborative Innovation Center of Quantum Matter, Beijing 100871, China Received 24 April 2020, online 27 April 2020 *B.W. is supported by the National Key R&D Program of China (Grant Nos. 2017YFA0303302 and 2018YFA0305602), the National Natural Science Foundation of China (Grant No. 11921005), and Shanghai Municipal Science and Technology Major Project (Grant No. 2019SHZDZX01). F.W. is supported by the Swedish Research Council (Contract No. 335–2014-7424), U.S. Department of Energy (Contract No. de-sc0012567), and the European Research Council (Grant No. 742104). Citation Text: Wilczek F, Hu H Y and Wu B 2020 Chin. Phys. Lett. 37 050304    Abstract We present an algorithm for the generalized search problem (searching $k$ marked items among $N$ items) based on a continuous Hamiltonian and exploiting resonance. This resonant algorithm has the same time complexity $O(\sqrt{N/k})$ as the Grover algorithm. A natural extension of the algorithm, incorporating auxiliary "monitor" qubits, can determine $k$ precisely, if it is unknown. The time complexity of our counting algorithm is $O(\sqrt{N})$, similar to the best quantum approximate counting algorithm, or better, given appropriate physical resources. DOI:10.1088/0256-307X/37/5/050304 PACS:03.67.Ac, 03.67.Lx, 89.70.Eg © 2020 Chinese Physics Society Article Text The advantages of quantum computers over classical computers are rooted in the tensor product structure of quantum mechanics and the superposition principle. It is, however, not straightforward to utilize those advantages. Shor's algorithm for factorizing large integer numbers[1] and Grover's search algorithm[2] are outstanding but rare examples where quantum computation gives a theoretical edge in a natural problem.[3] Shor's and Grover's algorithms are quantum circuit algorithms, consisting of a sequence of discrete operations known as quantum gates.[3] There is a different paradigm of quantum computing wherein algorithms are designed by constructing Hamiltonians. The system is initially in an easy-to-prepare quantum state, and the quantum computer evolves the quantum state using designed Hamiltonians. It eventually arrives at a quantum state which encodes the solution of the problem. The Hamiltonian approach can take advantage of intuition in quantum mechanics that physicists have cultivated over decades of research. A Hamiltonian was proposed for quantum search by Farhi and Gutmann in 1998,[4] and a generic quantum adiabatic algorithm was proposed in 2000.[5] In the adiabatic algorithm, the quantum computer follows the ground state of a time-dependent Hamiltonian. It has been shown that every quantum circuit algorithm can be converted into a quantum adiabatic algorithm, whose time complexity is exactly the same.[6,7] A quantum Hamiltonian algorithm for independent-set problems has some advantages over other known quantum algorithms and classical algorithms.[8] A quantum algorithm is essentially a manipulation that evolves an initial state to a target quantum state. Since resonance has been widely exploited in many branches of physics to achieve that sort of state evolution, it is natural to ask whether resonant evolution might be useful in this context. Here we use resonance to construct a quantum Hamiltonian algorithm for a generalized form of the problem addressed by Grover, namely to find, given an oracle, marked entries within a list of items. If the list has $N$ entries, and there are $k \geq 1$ marked items, our resonant algorithm can find one of the marked entries in time $O(\sqrt{N/k})$. This time complexity is the same as the Grover algorithm[2] and the quantum adiabatic search algorithm.[9,10] Though there is no gain in performance, there is no loss either, and the resonant approach seems particularly simple and transparent. Next we introduce a monitor qubit, which is very natural in our context. Roughly speaking, a monitor qubit keeps track of whether the resonant transition of interest has occurred. Through use of monitor bits we can both avoid wasteful measurements on computational bits, and also gather information on the initial state. Below we demonstrate two different, characteristic methods to extract information using monitor qubits: predictive dissonance and robust readout. In the search context, predictive dissonance allows us to determine the number $k$ of marked entries, when it is not given, with the time complexity $O(\sqrt{N})$. All known quantum algorithms can only approximately determine $k$ with a similar time complexity.[11,12] Robust readout is a more open-ended concept, which depends in detail on the physical implementation of the quantum computer. Given appropriate resources, it can speed things up further. Let us briefly recall the basic resonance phenomenon in a two-state quantum system.[13] We consider the time-dependent Hamiltonian, $$ \hat{H}(t) = \begin{pmatrix} \dfrac{\mathit{\Delta}}{2} & \epsilon e^{-i\omega t}\\ \epsilon e^{i\omega t} & -\dfrac{\mathit{\Delta}}{2} \end{pmatrix}\,,~~ \tag {1} $$ where $\mathit{\Delta}$ is the energy difference between the two states and $\omega$ and $\epsilon$ are the frequency and strength of the external drive, respectively. Without loss of generality, we assume that $\epsilon$ is real. This Hamiltonian can describe some realistic physical systems, or arise as a rotating-wave approximation of systems where the driving is proportional to $\cos (\omega t)$. By going to a rotating reference frame in Hilbert space, one readily derives the time evolution operator corresponding to Eq. (1) to be $$ \hat{U}(t) = \cos(\kappa t)\hat{I}-i\sin(\kappa t)\Big[\dfrac{\omega-\mathit{\Delta}}{2\kappa}\hat{\sigma}_{z}+\dfrac{\epsilon}{\kappa}\hat{\sigma}_{x}\Big]\,,~~ \tag {2} $$ where $\kappa= \sqrt{\epsilon^2+(\omega-\mathit{\Delta})^2/4}$. Off resonance, when $|\omega-\mathit{\Delta}|\gg |\epsilon|$ , we have $$ \hat{U}(t)\approx \cos(\dfrac{|\omega-\mathit{\Delta}|}{2}t)\hat{I}-i\sin(\dfrac{|\omega-\mathit{\Delta}|}{2}t)\hat{\sigma}_{z}.~~ \tag {3} $$ In this case, if the initial condition has only upper component, then the system will remain concentrated on the upper component. On resonance, $|\omega-\mathit{\Delta}|\ll\epsilon $, the time propagator becomes $$ \hat{U}(t) \approx \cos(\epsilon t)\hat{I}-i\sin(\epsilon t)\hat{\sigma}_{x}\,.~~ \tag {4} $$ If we start with only the upper component present, it will have evolved completely into a state with only the lower component after a time $\tau = \pi/(2\epsilon)$. We now apply this framework to construct a quantum search algorithm. The search problem is to find items that satisfy certain criteria in an unsorted database of $N$ items. On a quantum computer, these items are stored as $n = \log_{2}N$ qubits with $N$ orthonormal basis states $\left|1\right\rangle , \left|2\right\rangle , \ldots, \left|N\right\rangle $ embodying a binary encoding. To exploit quantum resonant search, we construct the Hamiltonian $$ \hat{H}(t) = a(t)\hat{H}_{\gamma}+b(t)\hat{H}_{x}+c(t),~~ \tag {5} $$ where $\hat{H}_{\gamma} = |\gamma\rangle\langle \gamma |$ and $\hat{H}_{x} = |x\rangle\langle x|$. The state $\left|\gamma\right\rangle =\frac{1}{\sqrt{N}} \sum_{j}\left|j\right\rangle $ is the equal-weight superposition of the number basis. Since $\left|x\right\rangle $ is the state that satisfies our searching criteria, we call it the answer state. In general, there could be more than one state that satisfy the searching criteria, and we will discuss those scenarios shortly. $\hat{H}_{x}$ embodies the oracle[9,10] which encodes the answer. As the initial state and the Hamiltonian have the same permutation symmetry, we decompose the quantum state $|\psi\rangle$ as $$ |\psi\rangle =\phi_1\dfrac{\sqrt{N-1}}{\sqrt{N}}|x_{\perp}\rangle+ \phi_2\dfrac{1}{\sqrt{N}}|x\rangle\,.~~ \tag {6} $$ Here $|x_{\perp}\rangle=\dfrac{1}{\sqrt{N-1}} \sum^\prime_{j}\left|j\right\rangle $, where the summation is over all items other than the answer item. This converts the system into a two-state model spanned by $|x\rangle$ and $|x_{\perp}\rangle$. The Hamiltonian (5) now takes the reduced form $$ \hat{\mathcal H}_1(t)=\begin{pmatrix} a(t)+c(t) & \sqrt{\frac{1}{N}}a(t)\\ \\ \sqrt{\frac{1}{N}}a(t) & b(t)+c(t) \end{pmatrix}\,,~~ \tag {7} $$ where we have taken the large $N$ limit. We choose $$\begin{align} a(t) =& p\cos(\omega t)\,,~~ \tag {8} \end{align} $$ $$\begin{align} b(t) =& -\mathit{\Delta}+p\cos(\omega t)\,,~~ \tag {9} \end{align} $$ $$\begin{align} c(t) =& \mathit{\Delta}/2-p\cos(\omega t)\,.~~ \tag {10} \end{align} $$ By comparing it to the Hamiltonian in Eq. (1), we have $\epsilon=p/(2\sqrt{N})$. (Here we have invoked the rotating wave approximation. It could be avoided with a slightly different, notationally more complicated Hamiltonian.) As our initial state is mostly in the upper component, $\langle s|{x_\perp}\rangle \approx 1$, we see that it will have rotated to the desired item $\left|x\right\rangle $ after $\tau_1=\pi\sqrt{N}/p$. If $p$ is independent of $N$, the time complexity of our algorithm is $O(\sqrt{N})$, the same as the Grover algorithm[2] and the quantum adiabatic search algorithm.[9,10] Note that $a(t) = 1-\frac{t}{T}$, $b(t) = -c(t)=-\frac{t}{T}$ corresponds to the quantum search Hamiltonian of Farhi and Gutmann.[4] A simple variation on the basic search problem is to allow $k$ different valid answers. Similarly, we can decompose the Hilbert space into two: one sub-space spanned by the $k$ answer items, and the rest space spanned by the other items. As long as $k\ll N$, we have in the large $N$ limit $$ \hat{\mathcal H}_1(t)=\begin{pmatrix} a(t)+c(t) & \sqrt{\frac{k}{N}}a(t)\\ \\ \sqrt{\frac{k}{N}}a(t) & b(t)+c(t) \end{pmatrix}\,.~~ \tag {11} $$ The critical rotation time is then $\tau_k= \pi\sqrt{N/k}/p$. We define a monitor qubit by expanding the Hilbert space to include an auxiliary qubit and generalizing $a(t)$, $b(t)$, and $c(t)$ in the form $$\begin{align} \hat{a}(t) =& \hat{1}\otimes \hat{\sigma}_{x}p\cos(\omega t)\,,~~ \tag {12} \end{align} $$ $$\begin{align} \hat{b}(t) =& \hat{1}\otimes \hat{\sigma}_{x}p\cos(\omega t)-\mathit{\Delta} \hat{1}\otimes \hat{1}\,,~~ \tag {13} \end{align} $$ $$\begin{align} \hat{c}(t) =& \dfrac{\mathit{\Delta}}{2} \hat{1}\otimes \hat{1}-\hat{1}\otimes\hat{\sigma}_{x}p\cos(\omega t)\,,~~ \tag {14} \end{align} $$ where of course the second factor acts on the monitor qubit. We again use the rotating wave approximation and Eq. (6) to reduce the Hamiltonian. In the rotating frame, we have $$ \hat{H}_{\rm rot} = \big(\dfrac{\omega-\mathit{\Delta}}{2}\big)\hat{\sigma}_{z}\otimes \hat{1} +\epsilon\hat{\sigma}_{x}\otimes \hat{\sigma}_{x}\,.~~ \tag {15} $$ On resonance $|\omega-\mathit{\Delta}|\ll \epsilon$ the time evolution operator is $$ \hat{U}(t) \approx \cos(\epsilon t)\hat{1}\otimes\hat{1}-i\sin(\epsilon t) \hat{\sigma}_{x}\otimes \hat{\sigma}_{x}\,,~~ \tag {16} $$ demonstrating that the monitor qubit rotates simultaneously with the computational qubits. If the initial state is prepared to be $$ \left|\psi(0)\right\rangle =\left(\dfrac{1}{\sqrt{N}}\left|x\right\rangle +\dfrac{\sqrt{N-1}}{\sqrt{N}}\left|x_\perp\right\rangle \right)\otimes \left|0\right\rangle\,,~~ \tag {17} $$ then following the dynamics given by Eq. (16), we find $$\begin{alignat}{1} &\left|\psi(t)\right\rangle =\cos(\epsilon t)\left(\dfrac{1}{\sqrt{N}}\left|x\right\rangle +\dfrac{\sqrt{N-1}}{\sqrt{N}}\left|x_\perp\right\rangle \right)\otimes |0\rangle \\ &~~~- i\sin(\epsilon t)\left(\dfrac{1}{\sqrt{N}}\left|x_\perp\right\rangle +\dfrac{\sqrt{N-1}}{\sqrt{N}}\left|x\right\rangle \right)\otimes |1\rangle.~~ \tag {18} \end{alignat} $$ This allows us to make measurement on the monitor qubit without collapsing the computational qubits to their number states. Suppose we make a measurement at time $t$ on the monitor qubit. If the result is $\left|1\right\rangle $, the system collapses to $\left(\frac{1}{\sqrt{N}}\left|x_\perp\right\rangle +\frac{\sqrt{N-1}}{\sqrt{N}}\left|x\right\rangle \right)\otimes \left|1\right\rangle $. In the case, we measure the computational qubits and will find the answer with probability $(N-1)/N$. If the result is $\left|0\right\rangle $, the system will collapse to state $\left(\frac{1}{\sqrt{N}}\left|x\right\rangle +\frac{\sqrt{N-1}}{\sqrt{N}}\left|x_\perp\right\rangle \right)\otimes \left|0\right\rangle $, which is exactly the initial state $\left|\psi(0)\right\rangle $ we prepared. Therefore we can continue to run the algorithm without the need to re-initialize the system. This could be useful, in the case $k$ is known, if we have small errors which take us off exact resonance and introduce rare failures. More interesting is the possibility to address the general problem of determining $k$, when it is not given. This is known as quantum counting problem.[11,12] We will discuss two approaches: the first involves the concept of predictive dissonance and the second involves the concept of robust readout. Both of them are of independent interest. They are characteristic potentialities opened up by monitor qubits, and could be of wider utility. In Eq. (16) we must take $$ \epsilon ~=~ \frac{p\sqrt k}{2 \sqrt N}\,.~~ \tag {19} $$ As a consequence, there will be times $$ t^{\rm zero} (k) ~=~ l \pi \frac{2 \sqrt N}{p\sqrt k}\,,~~ \tag {20} $$ where $l$ is an integer, when the monitor qubit (initially $| 0 \rangle$) is surely 0 and times $$ t^{\rm one} (k) ~=~ \left(l + \frac{1}{2}\right) \pi \frac{2 \sqrt N}{p\sqrt k}~~ \tag {21} $$ when the monitor qubit is surely 1. The case $k = 0$ is special: then the monitor qubit is always 0. Now given values $k_1, k_2$, we want to find times for which $k_1$ predicts the monitor qubit to be 0 and $k_2$ predicts it to be 1, or vice versa, i.e., $$\begin{align} t = 2 l_1 \pi \frac{\sqrt N}{p\sqrt k_1} = (2 l_2 + 1) \pi \frac{ \sqrt N}{p\sqrt k_2}~~ \tag {22} \end{align} $$ or $$\begin{align} t = (2l_1 + 1) \pi \frac{\sqrt N}{p\sqrt k_1} = 2 l_2 \pi \frac{\sqrt N}{p\sqrt k_2}~~ \tag {23} \end{align} $$ for integers $l_1, l_2$. We will refer to this phenomenon where alternative hypotheses give contradictory predictions, exactly or with high probability, as "predictive dissonance". In our context, it is related to the physical phenomenon of beats. Predictive dissonance is a way to insure progress. By measuring the monitor qubit at such a time, we will rule out either $k_1$ or $k_2$. For example, in the case of Eq. (22), if the monitor bit is measured to be 0, $k_2$ can be ruled out; if the monitor bit is 1, $k_1$ can be ruled out. And thus, if we are given an upper bound $k_{\max}$ on the possible values of $k$, we can home in a unique $k$ after at most $k_{\max}$ invocations of predictive dissonance. Our numerical results show that the number of invocations is proportional to $k_{\max}^\alpha$ with $\alpha\lesssim 0.7$ (see next section). Unfortunately it is not always possible to achieve exact predictive dissonance. For one thing, the occurrence of square roots of $k_1$ and $k_2$ generally precludes the existence of such times. On the other hand, by careful consideration of $\sqrt{k_1/k_2}$ we can find times which satisfy our requirements to a good approximation. At such times, we can interpret the measurement of the monitor qubit as ruling out $k_1$ or $k_2$ with high probability. Of course, for efficiency we also want to keep the times reasonably small. We can assume that $k_1 < k_2$. First suppose that $\sqrt {\frac{k_2}{k_1}}$ is rational, and write it in the reduced form $2^s\frac{a}{b}$ with $a, b$ odd. Then if $s < 0$ we can satisfy Eq. (22) with $$\begin{align} l_1 ~=&~ 2^{-s-1} b\,, \\ 2l_2 + 1 ~=&~ a\,, \\ t ~=&~ \frac{2^{-s} \pi \sqrt N}{p \sqrt {k_1}} ~\leq~ \frac{\pi \sqrt N}{p}\,,~~ \tag {24} \end{align} $$ while if $s>0$ we can satisfy Eq. (23) with $$\begin{align} 2l_1 + 1 ~=&~ b\,, \\ l_2 ~=&~ 2^{s-1} a\,, \\ t ~=&~ \frac{2^{s-1} \pi \sqrt N}{p \sqrt {k_2}} ~\leq~ \frac{\pi \sqrt N}{p}\,.~~ \tag {25} \end{align} $$ In the exceptional case $s=0$ we do not get exact predictive dissonance, but we can get close, as follows. At times $t = 2 l_2 \pi \frac{\sqrt N}{p\sqrt {k_2}}$ we will surely measure 0 if $k = k_2$ on the monitor qubit, while if $k = k_1$ we will measure 1 with probability $$ P_1 ~\equiv~ \sin^2 \left(l_2 \pi \sqrt {\frac{k_1}{k_2}}\right) ~=~ \sin^2 \left(\pi l_2 \frac{b}{a}\right)\,.~~ \tag {26} $$ Now elementary number theory instructs us that there will be values of $l_2 < a $ for which $$ l_2 b ~\equiv~ \frac{a \pm 1}{2}\quad({\rm mod}\, a)\,.~~ \tag {27} $$ For these values of $l_2$ we will have $$ P_1 = \cos^2 \frac{\pi}{2a} \geq 0.75~~ \tag {28} $$ since $a \geq 3$. Thus if we measure 1 we can eliminate $k_2$ as a candidate, while if we measure 0 repeatedly we can eliminate $k_1$ with high confidence. For each measurement, the same time bound in Eqs. (24) and (25) applies. We now switch to a different procedure, cruder but more general, which applies when $\sqrt{\frac{k_2}{k_1}}$ is irrational. (Number-theoretic refinements are certainly possible, but they are beyond the scope of this paper.) To set the stage, let us re-state the essence of our problem in the form we will address it. We want to set up predictive dissonance by finding a time, not too large, such that on resonance measurement of the monitor qubit will surely yield 0 if $k= k_2$ but will have large probability to yield 1 if $k=k_1$. The first condition reads $$\begin{align} {\rm phase}_2 ~=&~ \frac{2p\sqrt{k_2}}{\sqrt N} t ~=~ l_2 \pi\,, \\ t ~=&~ \frac{l_2 \pi \sqrt N}{2p\sqrt{k_2}}\,,~~ \tag {29} \end{align} $$ and gives us $$ {\rm phase}_1 ~=~ {l_2 \pi} \sqrt{\frac{k_1}{k_2}}\,.~~ \tag {30} $$ We want to insure that ${\rm phase}_1$ is close to $\frac{\pi}{2}$ modulo $\pi$, and also, in order for our time bound to hold, that $l_2 \leq \sqrt{k_2}$. Let us consider the phase modulo $\pi$ as defining a circle. If $\pi \sqrt{\frac{k_1}{k_2}}$ lies within the interval of length $\frac{\pi}{3}$ centered at $\frac{\pi}{2}$, then simply by choosing $l_2 =1$ we achieve $$ P_1 ~\geq~ \cos^2 \frac{\pi}{6} ~=~ 0.75~~ \tag {31} $$ as in Eq. (28). If $\theta \equiv \pi \sqrt{\frac{k_1}{k_2}}$ lies in the interval $0 < \theta \leq \frac{1}{3} \pi$, modulo $\pi$, then steps in units of $\theta$ will move us monotonically into the sector just described. If $\theta$ lies in the interval $\frac{2}{3} \pi \leq \theta < \pi $, then steps in units of $\theta$ will move us monotonically backward into that sector. One can check that the number of steps required is always consistent with our standard time bound. Finally, the case $\theta = 0$, corresponding to $k_1 =0$, is trivial. We apply predictive dissonance to a class of problems, where the estimated maximum number of possible solutions $k_{\max}$ is independent of $N$. For many hard instances of NP complete problems, this is indeed the case.[14] We want to pinpoint the number of solutions, $k_{{\rm true}}\in [0,k_{\max}]$. We choose pairs of $k_1$ and $k_2$ in the range $[0,k_{\max}]$, and use predictive dissonance to eliminate one of them after the readout. In general, the choice of $k_1$ and $k_2$ will result in $\sqrt{\frac{k_2}{k_1}}$ as an irrational number. Then we could use the protocol described in the previous section to choose the proper time $t_{{\rm run}}$ such that the measurement of monitor qubit will surely yield 0 if $k=k_2$ and will have high probability $p$ to yield 1 if $k=k_1$. In fact, the protocol described in the previous section ensures $p\geq 0.75$. To further enhance the probability $p$, we take a sequential $J$ measurements of monitor qubit, and the readout will be a binary string of length $J$, i.e., $R = [0,0,1,0,\ldots]$, where $0$ means no flip of the monitor qubit and $1$ denotes the flip of the monitor qubit. If there is at least one $1$ in the readout $R$, we can eliminate $k_{2}$. If the readout $R$ has only $0$, then we can eliminate $k_1$ confidently, because the probability of such a case appearing is $(1-P)^{J}\ll 1$. The general time complexity of our predictive dissonance protocol can be expressed as $O(k_{\max}^{\alpha}N^{\beta})$. We expect $\beta=0.5$ because the single run time $t_{{\rm run}}\propto \sqrt{N}$. As will be shown below, $\alpha$ depends on the detail of choosing $k_1$, $k_2$ pairs. In the following, we discuss two pairing schemes: (1) half-size pairing and (2) head-tail pairing. At a given time, we always have a list of possible $\{\widetilde{k}_{i}\}$ and assume $\widetilde{k}_0 < \widetilde{k}_1 < \cdots < \widetilde{k}_n$. For the half-size pairing scheme, we choose $k_1=\widetilde{k}_i$ and $k_2=\widetilde{k}_{i+n/2}$; for the head-tail pairing scheme, we choose $k_1=\widetilde{k}_{i}$ and $k_{2}=\widetilde{k}_{n-i}$. In numerical simulation, for each fix $k_{\max}$ and $N$, we random sample $k_{{\rm true}}\in [0,k_{\max}]$, and follow predictive dissonance protocol to find $k_{{\rm true}}$. And we use ensemble averaged $\overline{T}$ to denote the average running time to pinpoint $k_{\rm true}$ for given $N$ and $k_{\max}$. For those two pairing schemes, we first fix $k_{\max}=50$, and then vary the number of items $N$ in the database. The result is shown in Fig. 1(a). We find for both pairing schemes, $\overline{T}\propto \sqrt{N}$. This is reasonable, because each run time is proportional to $\sqrt{N}$ whichever pairing scheme is chosen. Therefore, ensemble averaged run time should also be proportional to $\sqrt{N}$.
cpl-37-5-050304-fig1.png
Fig. 1. Scaling behavior of ensemble averaged running time $\overline{T}$ as a function of $N$ and $k_{\max}$. For a given $N$ and $k_{\max}$, we uniformly sample $k_{\rm true}\in [0,k_{\max}]$ 300 times. For each $k$ sample, we follow the predictive dissonance protocol to pinpoint $k$ and record the running time $T$, and we choose repetition $J=6$. The ensemble averaged time $\overline{T}$ is plotted for each $N$ and $k_{\max}$. In subplot (a), it shows $\overline{T}\propto N^{\beta}$, where $\beta$ is approximately 0.5; in subplot (b), it shows $\overline{T}\propto k_{\max}^{\alpha}$, and $\alpha$ depends on the details of pairing schemes.
Next we study the relation between averaged run time $\overline{T}$ and $k_{\max}$. We fix $N=20000$ and vary $k_{\max}$. As shown in Fig. 1(b), we find that $\overline{T}\propto k_{\max}^{\alpha}$ with the power $\alpha$ depending on the pairing scheme. For the half-size pairing, $\overline{T}\propto k_{\max}^{0.59}$, while for head-tail pairing, $\overline{T}\propto k_{\max}^{0.68}$. We conjecture that the lower bound for $\alpha$ is 0.5, because we can roughly estimate that $\overline{T}\propto k_{\max}\sqrt{N/k_{\max}}\propto \sqrt{k_{\max}N}$. What pairing scheme can achieve the optimal lower bound is subject to further discussion. There are problems where the number of solutions $k_{\rm true}$ scale with $N$.[8] If $k_{\rm true}\propto N^{\gamma}$, our numerical results indicate that $\overline{T}\propto N^{\alpha\gamma+0.5}$. We now briefly describe a very different way to exploit monitor qubits to address the same problem. It is conceptually simpler and potentially much faster, but it requires additional resources and it depends upon assumed physical properties of qubits. Indeed, let us assume that we have an ensemble containing several monitor qubits, each of the kind described before, and that they are localized particles - "spins" - carrying a magnetic moment, all within a common small region. Then the systematic oscillation of the ensemble of monitor bits will set up an oscillating magnetic field, which can be read out with great sensitivity, for instance using a SQUID. The frequency of that oscillating field encodes the unknown value of $k$, according to our preceding formulae. Use of several monitor qubits, of course, also brings in protection against errors in any one of them, and against small uncorrelated errors that affect all of them. We have used resonance to construct quantum search algorithms. In addition, with monitor qubits we have implemented predictive dissonance and robust readout, which allow us to find the number of answers efficiently when that is unknown. Our algorithms illustrate the importance of physical considerations in assessing computational potential. The parameter $p$, which governs overall speed, represents interaction energy at a particular frequency, and could become quite large in a resonant context. Robust readout can in principle obviate $k$ dependence altogether. We indicated in broad terms how robust readout can be implemented using spin qubits. Both this and possible alternative implementations merit further study. References Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerQuantum Mechanics Helps in Searching for a Needle in a HaystackAnalog analogue of a digital quantum computationQuantum Computation by Adiabatic EvolutionAdiabatic Quantum Computation is Equivalent to Standard Quantum ComputationExact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit AlgorithmQuantum independent-set problem and non-Abelian adiabatic mixingHow powerful is adiabatic quantum computation?Quantum search by local adiabatic evolutionQuantum Approximate Counting, SimplifiedA Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
[1] Shor P W 1997 SIAM J. Comput. 26 1484
[2] Grover L K 1997 Phys. Rev. Lett. 79 325
[3]Nielsen M A, Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000)
[4] Farhi E and Gutmann S 1998 Phys. Rev. A 57 2403
[5] Farhi E, Goldstone J, Gutmann S and Sipser M 2000 arXiv:quant-ph/0001106v1
[6] Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S and Regev O 2007 SIAM J. Comput. 37 166
[7] Yu H Y, Huang Y L and Wu B 2018 Chin. Phys. Lett. 35 110303
[8] Wu B, Yu H Y and Wilczek F 2020 Phys. Rev. A 101 012318
[9] van Dam Wim, Mosca M and Vazirani U 2002 Proceedings of the 42nd Annual Symposium on Foundations of Computer Science p. 279
[10] Roland J and Cerf N J 2002 Phys. Rev. A 65 042308
[11]Wie C R 2019 Quantum Inf. Comput. 19 0967
[12] Aaronson S and Rall P 2019 arXiv:1908.10846v2 [quant-ph]
[13]Scully M O and Zubairy M S 1997 Quantum Optics (Cambridge University Press, Cambridge, 1997)
[14] Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A and Preda D 2001 Science 292 472