Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we study the presence of quantum correlations on the implementation of Deutsch- Jozsa algorithm running in the DQC1 model. We extend the analysis to a previous experimental realization of this computation presented in Phys. Rev. A 78, 022317 (2008). The Deutsch-Jozsa algorithm, an oracle based problem, can efficiently be solved in this model. Although there is no quantum correlations in the initial and final states of the computation, we find quantum correlations in intermediate steps of the algorithm. The presence of quantum correlations is not a sufficient property for computational gain in this case, since the performance of the classical probabilistic algorithm is better than the quantum one. The reason for this unexpected result relies on the fact that we have access to the outcomes of the control qubit only. A comparison between the efficiency of DQC1 and DQCp circuits to solve the Deustch-Jozsa problem is also presented.
Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we study the presence of quantum correlations on the implementation of Deutsch- Jozsa algorithm running in the DQC1 model. We extend the analysis to a previous experimental realization of this computation presented in Phys. Rev. A 78, 022317 (2008). The Deutsch-Jozsa algorithm, an oracle based problem, can efficiently be solved in this model. Although there is no quantum correlations in the initial and final states of the computation, we find quantum correlations in intermediate steps of the algorithm. The presence of quantum correlations is not a sufficient property for computational gain in this case, since the performance of the classical probabilistic algorithm is better than the quantum one. The reason for this unexpected result relies on the fact that we have access to the outcomes of the control qubit only. A comparison between the efficiency of DQC1 and DQCp circuits to solve the Deustch-Jozsa problem is also presented.
Quantum correlations have been pointed out as the most likely source of the speed-up in quantum computation. Here we analyzed the presence of quantum correlations in the implementation of Deutsch-Jozsa algorithm running in the DQC1 and DQCp models of quantum computing. For some balanced functions, the qubits in DQC1 model are quantum correlated just in the intermediate steps of the algorithm for a given decomposition into one and two qubits gates. In the DQCp model the final state is strongly quantum correlated for some balanced functions, so that the pairwise entanglement between blocks scales with the system size. Although the Deutsch-Jozsa algorithm is efficiently implemented in both models of computation, the presence of quantum correlations is not a sufficient property for computational gain in this case, since the performance of the classical probabilistic algorithm is better than the quantum ones. The measurement of other qubits than the control one showed to be inefficient to turn the algorithm deterministic.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch-Jozsa and Simon's problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch-Jozsa problem with probability 1 using only one oracle query, and Simon's problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch-Jozsa and Simon's problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms, and calls for further study of oracle separation between quantum and classical computation.
The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.
The one-clean-qubit model of quantum computation (DQC1) efficiently implements a computational task that is not known to have a classical alternative. During the computation, there is never more than a small but finite amount of entanglement present, and it is typically vanishingly small in the system size. In this paper, we demonstrate that there is nothing unexpected hidden within the DQC1 model---Grover's search, when acting on a mixed state, provably exhibits a speedup over classical, with guarantees as to the presence of only vanishingly small amounts of quantum correlations (entanglement and quantum discord)---while arguing that this is not an artifact of the oracle-based construction. We also present some important refinements in the evaluation of how much entanglement may be present in the DQC1 and how the typical entanglement of the system must be evaluated.
In 1985, David Deutsch challenged the Church-Turing thesis by stating that his quantum model of computation "could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine". While this is thought to be true in general, there is usually no way of knowing that the corresponding classical algorithms are the best possible solutions. Here we provide an efficient classical simulation of the Deutsch-Jozsa algorithm, which was one of the first examples of quantum computational speed-up. Our conclusion is that the Deutsch-Jozsa quantum algorithm owes its speed-up to resources that are not necessarily quantum-mechanical, and when compared with the classical simulation offers no speed-up at all.