Collision Finding with Many Classical or Quantum Processors

Stacey Jeffery

I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii In this thesis, we investigate the cost of finding collisions in a black-box function, a problem that is of fundamental importance in cryptanalysis. Inspired by the excellent performance of the heuristic rho method of collision finding, we define several new models of complexity that take into account the cost of moving information across a large space, and lay the groundwork for studying the performance of classical and quantum algorithms in these models. iii Acknowledgements I am deeply indebted to my supervisor, Dr. Michele Mosca, for introducing me to the subject of quantum information processing, and for the years of support and encouragement

Xiaodong Xing, Alejandro Gomez Cadavid, Artur F. Izmaylov +1 more

We propose a hybrid quantum-classical algorithm for solving the time-independent Schrödinger equation for atomic and molecular collisions. The algorithm is based on the S -matrix version of the Kohn variational principle, which computes the fundamental scattering S -matrix by inverting the Hamiltonian matrix expressed in the basis of square-integrable functions. The computational bottleneck of the classical algorithm─symmetric matrix inversion─is addressed here using the variational quantum linear solver (VQLS), a recently developed noisy intermediate-scale quantum (NISQ) algorithm for solving systems of linear equations. We apply our algorithm to single- and multichannel quantum scattering problems, obtaining accurate vibrational relaxation probabilities in collinear atom–molecule collisions. We also show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules. Our results demonstrate that it is possible to calculate scattering cross sections and rates for complex molecular collisions on NISQ quantum processors, opening up the possibility of scalable digital quantum computation of gas-phase bimolecular collisions and reactions of relevance to astrochemistry and ultracold chemistry.

Torsten V. Zache

Jian Xiao Zou, Yongyang Liu, Le Dong

In this article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2k-2)n/2k+1-3 ), and the classical memory and quantum memory complexities are O(2(2k-2)n/2k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2squantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2k-2)n-(2k+1-2k-1-3)s/2k+1-3 )while the classical memory and quantum memory complexities are O(2(2k-1-1)n+s-2k-2/2k+1-3 ) and O(n), respectively.

Qipeng Liu, Mark Zhandry