Source-linked AI summary
Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
Mark Hillery
TL;DR
The paper asks how coherence functions as a resource in the Deutsch-Jozsa algorithm and related probabilistic decision problems. It applies a quantitative coherence measure to quantum-walk procedures and compares them with classical sampling. The analysis finds that reduced coherence worsens discrimination, while a related problem retains a quantum one-sided-error advantage over a classical two-sided-error procedure.
Problem
The paper investigates how quantitatively measured quantum coherence affects Deutsch-Jozsa decision performance and its comparison with classical procedures.
Method
The paper models Deutsch-Jozsa and a related decision problem with quantum walks, decohering path ancillas, coherence measures, and fixed-run quantum-versus-classical comparisons.
Results
Reduced coherence worsens distinction between constant and balanced cases, while the related problem gives the quantum method one-sided error versus the classical method’s two-sided error.
Takeaways & Limitations
Coherence is a resource for these algorithms, and the quantum method has an advantage when mistaking the balanced case for the ε case is costly.
Abstract
from arXiv · showhide
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 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.
I. INTRODUCTION
The paper frames coherence as a resource for the Deutsch-Jozsa algorithm, interpreting the algorithm as interference in a multi-arm quantum walk. It compares quantum and classical decision procedures probabilistically and studies how decoherence affects performance.
- I. INTRODUCTION: Coherence is basis-dependent and depends on offdiagonal density-matrix elements, enabling interference between paths in an interferometer.The paper treats coherence quantitatively using a measure proposed in earlier work.
- I. INTRODUCTION: The Deutsch-Jozsa problem asks whether an oracle’s Boolean function is constant or balanced, with the balanced case differing on half of all inputs.A constant function has the same output for every input, whereas a balanced function outputs 0 and 1 equally often.
- I. INTRODUCTION: Classically, certainty can require 2^n−1 + 1 input checks, while a quantum procedure can determine the promised case through interference.The probabilistic comparison instead evaluates the probability of a correct answer after a fixed number of runs.
- I. INTRODUCTION: The study quantifies how reduced coherence changes the ability to distinguish constant and balanced cases and compares quantum-walk runs with sampled classical phase shifters.It also introduces a related decision problem in which the quantum and classical procedures have different error structures.
- I. INTRODUCTION: The quantum-walk implementation uses N paths between Fourier vertices A and B, with phase shifters applying exp(iφj) along the paths.The walk begins in |0, A⟩ and, after three steps, tests whether the particle is in |B, N +1⟩.
III. ANALYSIS OF THE WALK
The walk’s output distinguishes constant from balanced phase patterns through interference at the edge between B and N + 1. Introducing ancillas models decoherence, and the resulting coherence-dependent bound limits discrimination performance.
- III. ANALYSIS OF THE WALK: N^2/(N +1)^2 is the output probability for identical phases, while half 0 and half π phases give zero when N is even.After three steps, measuring the edge between B and N + 1 therefore distinguishes the two cases up to an error of order 1/N.
- III. ANALYSIS OF THE WALK: Ancilla qubits model decoherence by recording path-dependent states |µj⟩ = αj|0⟩j + βj|1⟩j as the particle traverses phase-shifted vertices.Tracing out these ancillas produces the particle’s reduced output density matrix.
- III. ANALYSIS OF THE WALK: When all ancilla states coincide, X = νN(N −1)/(N + 1)^2, linking the interference term directly to the common ancilla-state overlap ν.This specializes the general coherence-dependent expression to identical ancilla-state overlaps for distinct paths.
- III. ANALYSIS OF THE WALK: The output probability satisfies ⟨B, N + 1|ρout|B, N + 1⟩≤ N/(N + 1)^2 + X, so coherence places an upper limit on discrimination.Here X captures contributions from overlaps between the ancilla states associated with different paths.
- III. ANALYSIS OF THE WALK: With perfect coherence, the constant case reaches |B, N + 1⟩ up to O(1/N), while the balanced case never reaches it.As coherence decreases, the probability of mistaking the constant case for the balanced case increases.
IV. DEUTSCH-JOZSA ALGORITHM
The algorithm compares classical phase-shifter sampling with quantum-walk measurements under reduced coherence. As coherence decreases, quantum errors increase, while the quantum method can outperform the classical method when decoherence is limited.
- Coherence dependence: The output probability for the constant case is ⟨B, N + 1|ρout|B, N + 1⟩ = 1/(N + 1)^2 [N + νN(N −1)].For the balanced case, the corresponding expression contains (1 −ν)^N, showing the dependence on coherence parameter ν.
- One trial: For one quantum-walk run, detection of |B, N + 1⟩ indicates the constant case, while nondetection leads to the balanced guess.The resulting error is almost one-sided: detection identifies the constant case with very high probability, whereas nondetection can still be mistaken under reduced coherence.
- Coherence dependence: The probability of quantum error decreases as coherence increases, establishing coherence as the resource used by this decision procedure.The paper treats ν as the parameter controlling the amount of coherence and compares quantum performance against classical sampling.
- Two trials: With two trials, the optimal rule guesses balanced for (0, 0) and constant otherwise, yielding a quantum error of (1/2)(1 −ν)^2.The non-(0, 0) outcomes identify the constant case with certainty, whereas the (0, 0) outcome remains ambiguous.
- Two trials: For two trials, the quantum method is better than the classical method as long as decoherence is not too great.The comparison is based on the probability of making an incorrect constant-versus-balanced decision.
- Probabilistic decision setting: The analysis assumes equal prior probabilities for constant and balanced cases and examines ambiguous outcomes after sampling or repeated quantum-walk trials.Classically, ambiguity occurs when sampled phase shifters agree; quantumly, it occurs when the particle is never detected in |B, N + 1⟩.
V. VARIATION ON DEUTSCH-JOZSA
The variation distinguishes balanced phase shifts from a nearby biased case, comparing quantum-walk runs with classical phase-shifter samples. Quantum and classical methods require mϵ^2 of order 1 for small error, but the quantum error is one-sided and coherence increases its required runs.
- Problem and strategies: The variation compares a quantum walk with classical phase-shifter sampling for distinguishing balanced phase shifts from an ϵ-biased case.The quantum strategy runs the walk repeatedly; the classical strategy samples m phase shifters.
- Quantum method: In the balanced case, the quantum walk finds |B, N + 1⟩ with probability zero up to O(1/N), while the ϵ case has probability ϵ^2.This makes observing the output state a test for the ϵ case.
- Quantum method: The quantum test declares the ϵ case after any detection in m runs and otherwise declares the balanced case.It is always correct for the balanced case; for the ϵ case, the error is small when mϵ^2 is at least of order 1.
- Error scaling: For both methods, keeping error small requires mϵ^2 to be at least of order 1.The classical analysis uses a threshold on the sampled phase-shifter average and Chernoff bounds.
- Comparison and coherence: The quantum method has one-sided error, whereas the classical method has two-sided error, giving the quantum method an advantage when confusing balanced with ϵ is costly.Decoherence preserves one-sidedness but increases the quantum run count to order 1/(νϵ^2).
VI. CONCLUSION
The paper concludes that coherence is a resource for the Deutsch-Jozsa and related decision algorithms. Reduced coherence worsens distinguishability, while sufficient coherence supports a quantum advantage or preserves one-sided error with comparable measurement scaling.
- VI. CONCLUSION: The Deutsch-Jozsa algorithm ideally answers its decision problem in one run, whereas a classical method may require exponentially many runs in the worst case.The paper also evaluates probabilistic settings rather than only the ideal form.
- VI. CONCLUSION: Lower coherence degrades the algorithm’s ability to distinguish constant and balanced cases, demonstrating that coherence is a resource for the task.The conclusion links the resource directly to decision performance.
- VI. CONCLUSION: With enough coherence, quantum measurements have a higher probability of correct decisions than classical measurements for a fixed number of measurements.This is reported for the probabilistic Deutsch-Jozsa setting.
- VI. CONCLUSION: In the related decision problem, classical and quantum measurement counts are comparable when quantum coherence remains sufficiently high.The supplied conclusion introduces this comparison without specifying the complete continuation.
Appendix
The appendix justifies the ensembles used earlier by considering equally likely ±1 sequences with fixed composition and examining their length-m subsequences. It then derives the subsequence probability and approximates it when m is small relative to N and the composition counts.
- The ensemble contains length-N ±1 sequences with exactly pN ones and (1 −p)N minus ones, all assigned equal probability.
- The analysis fixes each subsequence to the first m positions and denotes its probability by p(m+, m−).
- Equation (37) gives the probability expression for a fixed subsequence in terms of factorials of N, m, pN, and the subsequence counts.
- Assuming m is much smaller than N, pN, and (1−p)N, the derivation applies the Stirling approximation.
- The final factor is approximated by taking its logarithm and expanding in m/N.