From Classical to Quantum

Yun Li

Wei Zheng Teo, Marco Carmosino, Lior Horesh C

One-way functions (OWF) are one of the most essential cryptographic primitives, the existence of which results in wide-ranging ramifications such as private-key encryption and proving $P \neq NP$. These OWFs are often thought of as having classical input and output (i.e. binary strings), however, recent work proposes OWF constructions where the input and/or the output can be quantum. In this paper, we demonstrate that quantum-classical (i.e. quantum input, classical output) OWFs can be used to produce classical-classical (i.e. classical input, classical output) OWFs that retain the one-wayness property against any quantum polynomial adversary (i.e. quantum-resistant). We demonstrate this in two ways. Firstly, we propose a definition of quantum-classical OWFs and show that the existence of such a quantum-classical OWF would imply the existence of a classical-classical OWF. Secondly, we take a proposed quantum-classical OWF and demonstrate how to turn it into a classical-classical OWF. In summary, this paper showcases another possible route into proving the existence of classical-classical OWFs (assuming intermediate quantum computations are allowed) using a "domain-shifting" technique between classical and quantum information, with the added bonus that such OWFs are also going to be quantum-resistant.

C. Wetterich

Abstract Quantum particles and classical particles are described in a common setting of classical statistical physics. The property of a particle being “classical” or “quantum” ceases to be a basic conceptual difference. The dynamics differs, however, between quantum and classical particles. We describe position, motion and correlations of a quantum particle in terms of observables in a classical statistical ensemble. On the other side, we also construct explicitly the quantum formalism with wave function and Hamiltonian for classical particles. For a suitable time evolution of the classical probabilities and a suitable choice of observables all features of a quantum particle in a potential can be derived from classical statistics, including interference and tunneling. Besides conceptual advances, the treatment of classical and quantum particles in a common formalism could lead to interesting cross‐fertilization between classical statistics and quantum physics.

Tomohiro Hattori, Takuya Hatomura

Feedback-based quantum optimization is a quantum approach to combinatorial optimization. In this paper, we introduce the classical counterpart of feedback-based quantum optimization by using the quantum-classical correspondence of spin systems to discuss the possibility of quantum advantage. It also enables us to develop higher-order theory of a previously proposed classical approach to feedback-based quantum optimization. First, we compare the feedback-based algorithm for quantum optimization (FALQON) and its variant with their classical counterparts. Then, we perform benchmark tests of various quantum and classical algorithms with small-scale instances, and of classical algorithms with large-scale instances. Main findings are that (i) quantum algorithms can be advantageous to classical algorithms in terms of the quality of solutions, while classical algorithms tend to show faster convergence than quantum ones, and (ii) one of the classical algorithms discussed in this paper shows significant scalability for higher-order unconstrained binary optimization problems. These findings highlight the importance of quantumness and the usefulness of classical approaches.

Marco Bellini, Silvia Viciani, Alessandro Zavatta