Solving k-SAT problems with generalized quantum measurement
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913398216720384 |
|---|---|
| author | Zhang, Yipei Lewalle, Philippe Whaley, K. Birgitta |
| author_facet | Zhang, Yipei Lewalle, Philippe Whaley, K. Birgitta |
| contents | 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 $λ^n$. For vanishing dragging time (with final readout only), we find $λ= 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 $λ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13611 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving k-SAT problems with generalized quantum measurement Zhang, Yipei Lewalle, Philippe Whaley, K. Birgitta Quantum Physics 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 $λ^n$. For vanishing dragging time (with final readout only), we find $λ= 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 $λ$ 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. |
| title | Solving k-SAT problems with generalized quantum measurement |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2406.13611 |