Kavli Affiliate: Birgitta Whaley
| First 5 Authors: Yipei Zhang, Philippe Lewalle, K. Birgitta Whaley, ,
| Summary:
We generalize the projection-based quantum measurement-driven $k$-SAT
algorithm of Benjamin, Zhao, and Fitzsimons (BZF, arxiv:1711.02687) to
arbitrary strength quantum measurements, including the limit of continuous
monitoring. In doing so, we clarify that this algorithm is a particular case of
the measurement-driven quantum control strategy elsewhere referred to as "Zeno
dragging". We argue that the algorithm is most efficient with finite time and
measurement resources in the continuum limit, where measurements have an
infinitesimal strength and duration. Moreover, for solvable $k$-SAT problems,
the dynamics generated by the algorithm converge deterministically towards
target dynamics in the long-time (Zeno) limit, implying that the algorithm can
successfully operate autonomously via Lindblad dissipation, without detection.
We subsequently study both the conditional and unconditional dynamics of the
algorithm implemented via generalized measurements, quantifying the advantages
of detection for heralding errors. These strategies are investigated first in a
computationally-trivial $2$-qubit $2$-SAT problem to build intuition, and then
we consider the scaling of the algorithm on $3$-SAT problems encoded with $4 –
10$ qubits. The average number of shots needed to obtain a solution scales with
qubit number as $lambda^n$. For vanishing dragging time (with final readout
only), we find $lambda = 2$ (corresponding to a brute-force search over
possible solutions). However, the deterministic (autonomous) property of the
algorithm in the adiabatic (Zeno) limit implies that we can drive $lambda$
arbitrarily close to $1$, at the cost of a growing pre-factor. We numerically
investigate the tradeoffs in these scalings with respect to algorithmic runtime
and assess their implications for using this analog measurement-driven approach
to quantum computing in practice.
| Search Query: ArXiv Query: search_query=au:”Birgitta Whaley”&id_list=&start=0&max_results=3