Optimal Usage of Quantum Random Access Memory in Quantum Machine Learning

By considering an unreliable oracle in a query-based model of quantum learning, we present a tradeoff relation between the oracle's reliability and the reusability of quantum state of the input data. The tradeoff relation manifests as the fundamental upper bound on the reusability. This limitation on the reusability would increase the quantum access to the input data, i.e., the usage of quantum random access memory (qRAM), repeating the preparation of a superposition of `big' input data on the query failure. However, it is found that, a learner can obtain a correct answer even from an unreliable oracle without any additional usage of qRAM---i.e., the complexity of qRAM query does not increase even with an unreliable oracle. This is enabled by repeatedly cycling the quantum state of the input data to the upper bound on the reusability.