Using Physical Experiments as Oracles

Edwin J Beggs, José Félix Costa, John Vivian Tucker

Tânia Filipa, Nascimento Ambaram, Universidde de Lisboa

In this work we proceed with the investigation of the power of an abstract model of computation that considers Turing machines coupled with physical oracles. A physical oracle is an experiment controlled by the Turing machine with the purpose of measuring some quantity or parameter, possibly suitable to boost the power of the Turing machine. We consider one of the three known types of measurement experiments — the two-sided case. Researches on the computational power under bounded resources of the two other types — threshold and vanishing — have been considered and are settle by other authors up to some hard open problems. Herein we address the unfinished case of the two-sided oracle, establishing the corresponding upper bounds. We consider three types of communication between the Turing machine and the oracle (infinite precision, unbounded precision and fixed precision), that simulate the error propagation common to physical experiments. These three types of precision introduce variants of the two-sided oracle machines. We fix the upper bounds for the three cases. In the context of the infinite precision protocol of two-sided machines, we then address the question of knowing if a number, a physical parameter, is measurable or not. This problem was first put out by the physicists Geroch and Hartle without a formal framework to reason upon definition. We characterize the measurable and the non measurable numbers and we analyze some of their properties.

Josh Roeloffs

Hans Luth

Jun Li, Xiaodong Yang, Xinhua Peng +1 more

Turing's notion of oracle machine is influential in diverse fields like computation, communication as well as philosophy. It has long been a fascinating open issue on construction of a real working oracle machine. Here, we address physical implementation of a quantum oracle machine which resolves the quantum optimal control problem. We show that the most computationally challenging part of gradient ascent pulse engineering, namely computing the fidelity and gradient for input control pulse, can be accomplished by the process of physical evolution and measurement on the quantum system being controlled. The quantum system outputs the desired information for gradient iteration at a constant and affordable cost thus can be treated as an oracle. By posing queries to and receiving messages from the oracle, classical computing devices update the control parameters until an optimum is achieved. To demonstrate the idea in experiment, we use a nine-spin nuclear magnetic resonance system, on which we have succeeded in preparing a seven-correlated quantum state without involving simulating the large Hilbert space evolution.

Hans Luth