arXiv:1512.01874 · Physical Review A

Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation

Mark S. Hillery

Published Jan 13, 2016• 277 citations

Abstract

That superpositions of states can be useful for performing tasks in quantum systems has been known since the early days of quantum information, but only recently has a quantitative theory of quantum coherence been proposed. Here we apply that theory to an analysis of the Deutsch-Jozsa algorithm, which depends on quantum coherence for its operation. The Deutsch-Jozsa algorithm solves a decision problem, and we focus on a probabilistic version of that problem, comparing probability of being correct for both classical and quantum procedures. In addition, we study a related decision problem in which the quantum procedure has one-sided error while the classical procedure has two-sided error. The role of coherence on the quantum success probabilities in both of these problems is examined.

DOI: 10.1103/physreva.93.012111

Related papers

Coherence Depletion in Quantum Algorithms

Ye-Chao Liu, Jiangwei Shang, Xiangdong Zhang

Besides the superior efficiency compared to their classical counterparts, quantum algorithms known so far are basically task-dependent, and scarcely any common features are shared between them. In this work, however, we show that the depletion of quantum coherence turns out to be a common phenomenon in these algorithms. For all the quantum algorithms that we investigated, including Grover's algorithm, Deutsch-Jozsa algorithm, and Shor's algorithm, quantum coherence of the system states reduces to the minimum along with the successful execution of the respective processes. Notably, a similar conclusion cannot be drawn using other quantitative measures such as quantum entanglement. Thus, we expect that coherence depletion as a common feature can be useful for devising new quantum algorithms in the future.

arXiv:1808.02222EntropyMar 7, 201922 citations

The continuous-variable Deutsch–Jozsa algorithm using realistic quantum systems

Rob C. Wagner, Viv M. Kendon

This paper is a study of the continuous-variable Deutsch–Jozsa algorithm. First, we review an existing version of the algorithm for qunat states (Pati and Braunstein 2002 arXiv:0207108v1), and then, we present a realistic version of the Deutsch–Jozsa algorithm for continuous variables, which can be implemented in a physical quantum system given the appropriate oracle. Under these conditions, we have a probabilistic algorithm for deciding the function with a very high success rate with a single call to the oracle. Finally, we look at the effects of errors in both of these continuous-variable algorithms and how they affect the chances of success. We find that the algorithm is generally robust for errors in initialization and the oracle, but less so for errors in the measurement apparatus and the Fourier transform. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to 'Coherent states: mathematical and physical aspects'.

Journal of Physics A Mathematical and TheoreticalMay 30, 20124 citations

A Good First Impression for Quantum Algorithms

Sandeep K. Shukla

What is the first quantum algorithm that students should learn? A common choice is the Deutsch-Jozsa algorithm because of its historical importance. However, the algorithm and the problem it solves are disconnected from familiar computational tasks and approaches. This paper provides an alternate starting point: the decision version of search. The main algorithmic idea is simple, involving encoding a function into a quantum state, and checking whether this quantum state is equal to a reference state. Moreover, we retain the Deutsch-Jozsa problem and algorithm as a special case of this presentation. We hope that students will find this a more satisfying start to studying quantum algorithms.

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Models and Methods for Information Security Management: Quantum Computing and the Deutsch–Jozsa Algorithm

Mikhail Pavlov

Abstract In the field of quantum computing, the Deutsch–Jozsa problem serves as a classical example illustrating the computational advantages of quantum algorithms over classical counterparts in specific scenarios. The problem involves efficiently determining the nature of a multi-valued function, showcasing how quantum parallelism can accelerate problem-solving. The Deutsch–Jozsa algorithm provides a framework for exploring these quantum advantages and offers insights into optimization tasks such as the minimum spanning tree (MST) problem in network design. Applications include network engineering, routing optimization, and resource allocation, where quantum-enhanced approaches can potentially outperform classical methods. This study examines the implementation of the Deutsch–Jozsa algorithm on quantum simulators and its adaptation in quantum versions of classical MST algorithms, such as the Ambainis–Spalek quantum variant of Edmonds–Karp. The analysis highlights the role of Grover’s search as a foundational component, integrating it with quantum MST techniques. Practical simulations using IBM Quantum platforms illustrate the algorithm’s potential for network optimization and broader information security applications.

Mar 4, 20260 citations

Oracle Quantum Computing

André Berthiaume, Gilles Brassard A

Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.

Journal of Modern OpticsDec 1, 199499 citations

Deutsch-Jozsa algorithm via deterministic quantum computaion with one qubit model

Marcio M. Santos, Eduardo I. Duzzioni

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.

Jul 24, 20130 citations