Quantum Algorithms for Universal Prediction

Taiga Hiroka, Min-Hsiu Hsieh, Yuki Shirakawa

Solomonoff's universal inductive inference [Inf. Control. 1964] is one of the most general frameworks for learning from sequential data and predicting future observations. It provides prediction guarantees for any computable stochastic source. We ask whether an analogous universal theory of induction can be developed for quantum systems. To this end, we introduce universal quantum inductive inference, a framework for learning and predicting quantum sources that may exhibit arbitrary correlations and entanglement across time. Given the outcomes of past measurements and the corresponding post-measurement quantum systems, the learner produces a joint state that predicts the next measurement outcome and post-measurement system while preserving correlations with the past systems. We model a quantum source as a multipartite quantum state whose description is generated by an unknown $s$-bit program within a given time bound. The learner is required to produce a state that is $ε$-close in trace distance to the target with probability at least $1-δ$. We establish an information-theoretic inference algorithm with round complexity $O(sε^{-2}δ^{-1})$. We further prove a matching lower bound in the relevant parameter regime, even for classical sources. As a second result, we construct a non-i.i.d. state tomography algorithm that outputs a classical description of the conditional state of the next system given past measurement outcomes. Our information-theoretic tomography algorithm achieves round complexity $O(sn^2ε^{-4}δ^{-2})$, where $n$ is the number of qubits received in each round. Finally, we investigate the computational hardness of universal quantum inductive inference under quantum cryptographic assumptions.

Behrooz Sepehry, Ehsan Iranmanesh, Michael P. Friedlander +1 more

Ji Jiang, Qipeng Yan, Ye Li +6 more

It is the first step for understanding how RNA structure folds from base sequences that to know how its secondary structure is formed. Traditional energy-based algorithms are short of precision, particularly for non-nested sequences, while learning-based algorithms face challenges in obtaining high-quality training data. Recently, quantum annealer has rapidly predicted the folding of the secondary structure, highlighting that quantum computing is a promising solution to this problem. However, gate model algorithms for universal quantum computing are not available. In this paper, gate-based quantum algorithms will be presented, which are highly flexible and can be applied to various physical devices. Mapped all possible secondary structure to the state of a quadratic Hamiltonian, the whole folding process is described as a quadratic unconstrained binary optimization model. Then the model can be solved through quantum approximation optimization algorithm. We demonstrate the performance with both numerical simulation and experimental realization. Throughout our benchmark dataset, simulation results suggest that our quantum approach is comparable in accuracy to classical methods. For non-nested sequences, our quantum approach outperforms classical energy-based methods. Experimental results also indicate our method is robust in current noisy devices. It is the first instance of universal quantum algorithms being employed to tackle RNA folding problems, and our work provides a valuable model for utilizing universal quantum computers in solving RNA folding problems.

Peter W. Shor

Davis, E. D.

Properties of Shor's algorithm and the related period-finding algorithm could serve as benchmarks for the operation of a quantum computer. Distinctive universal behaviour is expected for the probability for success of the period-finding algorithm as the input quantum register is increased through its critical size of $\mathfrak{m}_0=\lceil 2\log_2 r\rceil$ qubits (where $r$ is the period sought). Use of quadratic non-residues permits unequivocal predictions to be made about the outcome of the factoring algorithm.

Peter W. Shor