Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithm—classical solutions which are as efficient as the quantum one—have been proposed in the literature. These solutions are based on the possibility of classically simulating "superpositions", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their "observational power".
Deutsch's problem is the simplest and most frequently examined example of computational problem used to demonstrate the superiority of quantum computing over classical computing. Deutsch's quantum algorithm has been claimed to be faster than any classical ones solving the same problem, only to be discovered later that this was not the case. Various de-quantised solutions for Deutsch's quantum algorithm—classical solutions which are as efficient as the quantum one—have been proposed in the literature. These solutions are based on the possibility of classically simulating "superpositions", a key ingredient of quantum algorithms, in particular, Deutsch's algorithm. The de-quantisation proposed in this note is based on a classical simulation of the quantum measurement achieved with a model of observed system. As in some previous de-quantisations of Deutsch's quantum algorithm, the resulting de-quantised algorithm is deterministic. Finally, we classify observers (as finite state automata) that can solve the problem in terms of their "observational power".
Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch's problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a "quantum" partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of "superposition," a key ingredient of quantum algorithm, is — in this specific case — classically available.
Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called {\it Deutsch's problem}. Consider a Boolean function f:{0,1}→{0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant (that is, f(0)=f(1)) or balanced (f(0)=f(1)). Classically, to solve the problem seems to require the computation of f(0) and $ f(1)$, and then the comparison of results. Is it possible to solve the problem with {\em only one} query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a ``quantum'' {\em partial affirmative answer}. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be {\it de-quantised} to a deterministic simpler solution which is as efficient as the quantum one. The use of ``superposition'', a key ingredient of quantum algorithm, is--in this specific case--classically available.
Quantum computation has shown much promise at providing, at least in some cases, a significant advantage over classical computation. However, the nature of quantum computation is still far from being well understood. In order to develop quantum algorithms effectively, it is important to understand the true nature of the differences between classical and quantum computation. We investigate these differences more closely by looking at de-quantising quantum algorithms into classical counterparts which retain the benefit provided by, and thought to be intrinsic to, the quantum algorithms. We extend a previous de-quantisation of Deutsch’s problem to show that in some situations the quantum algorithm solving the Deutsch-Jozsa problem can be de-quantised into an equivalent classical one. We quantify the entanglement in this problem and show that the inability to easily extend the de-quantisation to the general case is a result of the entanglement destroying the concise classical state description needed to de-quantise such a black-box algorithm. We further show that the quantum Fourier transform, an important process in many quantum algorithms, in its standard form is de-quantisable. This highlights key misconceptions about both the quantum Fourier transform and quantum computation itself. In such cases it is the linearity of quantum mechanics which allows constructing quantum algorithms which offer advantage over classical algorithms. The careful investigation of de-quantisation in relation to these problems allows a deeper insight into the nature of quantum computation.
While it seems possible that quantum computers may allow for algorithms offering a computational speed-up over classical algorithms for some problems, the issue is poorly understood. We explore this computational speed-up by investigating the ability to de-quantise quantum algorithms into classical simulations of the algorithms which are as efficient in both time and space as the original quantum algorithms. The process of de-quantisation helps formulate conditions to determine if a quantum algorithm provides a real speed-up over classical algorithms. These conditions can be used to develop new quantum algorithms more effectively (by avoiding features that could allow the algorithm to be efficiently classically simulated) and to create new classical algorithms (by using features which have proved valuable for quantum algorithms). Results on many different methods of de-quantisations are presented, as well as a general formal definition of de-quantisation. De-quantisations employing higher-dimensional classical bits, as well as those using matrix-simulations, put emphasis on entanglement in quantum algorithms; a key result is that any algorithm in which the entanglement is bounded is de-quantisable. These methods are contrasted with the stabiliser formalism de-quantisations due to the Gottesman-Knill Theorem, as well as those which take advantage of the topology of the circuit for a quantum algorithm. The benefits and limits of the different methods are discussed, and the importance of utilising a range of techniques is emphasised. We further discuss some features of quantum algorithms which current de-quantisation methods do not cover and highlight several important open questions in the area.
While it seems possible that quantum computers may allow for algorithms offering a computational speed-up over classical algorithms for some problems, the issue is poorly understood. We explore this computational speed-up by investigating the ability to de-quantise quantum algorithms into classical simulations of the algorithms which are as efficient in both time and space as the original quantum algorithms. The process of de-quantisation helps formulate conditions to determine if a quantum algorithm provides a real speed-up over classical algorithms. These conditions can be used to develop new quantum algorithms more effectively (by avoiding features that could allow the algorithm to be efficiently classically simulated), as well as providing the potential to create new classical algorithms (by using features which have proved valuable for quantum algorithms). Results on many different methods of de-quantisations are presented, as well as a general formal definition of de-quantisation. De-quantisations employing higher-dimensional classical bits, as well as those using matrix-simulations, put emphasis on entanglement in quantum algorithms; a key result is that any algorithm in which the entanglement is bounded is de-quantisable. These methods are contrasted with the stabiliser formalism de-quantisations due to the Gottesman-Knill Theorem, as well as those which take advantage of the topology of the circuit for a quantum algorithm. The benefits of the different methods are contrasted, and the importance of a range of techniques is emphasised. We further discuss some features of quantum algorithms which current de-quantisation methods do not cover.
Although the basic ideas of quantum computation are fairly straightforward, the detailed manipulations required to extract a useful result from an entangled superposition of answers can be rather complicated. There are, however, a small number of algorithms which are simple enough to explain using only elementary methods. The best example is Deutsch's algorithm: as this only requires two qubits its properties are amenable to brute-force matrix calculations, and these calculations can be simplified using a variety of short cuts, which also give some insight into how and why the algorithm works. We will also explore the simplest case of Grover's quantum search algorithm, which is once again simple enough to be tacked by brute force. Finally we will look briefly at two methods used to stabilize quantum computers against errors. Deutsch's algorithm The invention of Deutsch's algorithm can be taken as defining the start of modern quantum computation, and it remains a key example, exhibiting many of the key properties of quantum algorithms in a particularly simple form. (Note, however, that the version of Deutsch's algorithm described here is not in fact the original but a later modification which is both more powerful and easier to understand.) Consider a binary function f from one bit to one bit, that is a function which takes in either 0 or 1 as its input and returns either 0 or 1 as its output. There are four such functions which may be conveniently labeled by their outputs as shown in Table 8.1.