Physical experiments as oracles

Edwin J Beggs

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.

Andrzej Posiewnik

Jerry B. Marion, J. L. Fowler

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.

José Félix Costa

Consider the classical model of a Turing machine with an oracle. The classical oracle is a one step external consultation device. The oracle may contain either non-computable information, or computable information provided just to speed up the computations of the Turing machine. In this talk we will consider the abstract experimenter (e.g. the experimental physicist) as a Turing machine and the abstract experiment of measuring a physical quantity (using a specified physical apparatus) as an oracle to the Turing machine. The algorithm running in the machine abstracts the experimental method of measurement (encoding the recursive structure of experimental actions) chosen by the experimenter. It is standard to consider that to measure a real number 4 µ, e.g. the value of a physical quantity, the experimenter (now the Turing machine) should proceed by approximations. Thus, besides the value of µ, we will consider dyadic rational approximations (denoted by finite binary strings), and a procedure to measure µ proved to be universal.