Signatures of quantum noise in the operation of Deutsch's algorithm
Pith reviewed 2026-05-20 10:27 UTC · model grok-4.3
The pith
Running Deutsch's algorithm twice exposes differences between quantum and classical models of environmental dephasing that remain hidden in single runs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We model pure dephasing in Deutsch's algorithm using both a full quantum density matrix approach and a classical Kraus operator method. For a single run, both yield identical effects on the algorithm's performance. However, when the algorithm is executed twice, the inclusion of correlations and interplay between decoherence channels results in a slowing of decoherence for balanced functions, with an even stronger and qualitatively altered dependence on decoherence for constant functions. These theoretical distinctions are fully reproduced in experiments on IBM Quantum processors.
What carries the argument
Comparison of full quantum density matrix evolution versus Kraus operator representation for pure dephasing applied to the oracle function in Deutsch's algorithm, with focus on correlations that appear only on repeated execution.
If this is right
- A single execution of Deutsch's algorithm produces the same effect whether dephasing is modeled quantum mechanically or classically.
- Two executions make the two models diverge because correlations between decoherence processes enter the dynamics.
- Decoherence effects slow for balanced functions once those correlations are taken into account.
- Constant functions show a stronger and qualitatively different dependence of final measurement probabilities on the strength of dephasing.
- Results obtained on IBM Quantum hardware match the predicted distinction independently of the modeling assumptions used in the derivation.
Where Pith is reading between the lines
- Repeating simple algorithms could serve as a practical diagnostic for the quantum character of noise on other hardware platforms.
- The stronger sensitivity seen for constant functions indicates that certain output classes may act as sharper probes of environmental quantumness.
- Systems with small environments, such as NV centers, may reveal further signatures that require extensions of the basic correlation treatment.
Load-bearing premise
Deutsch's algorithm serves as a valid stand-in for more complex quantum algorithms when studying how quantum properties of an environment manifest in computational results.
What would settle it
If a quantum processor yields identical statistics of measurement outcomes under the full density matrix model and the Kraus operator model after two runs of Deutsch's algorithm, the claimed distinction would be ruled out.
Figures
read the original abstract
We use Deutsch's algorithm as a stand in for more complex quantum algorithms in order to determine how quantum properties of an environment manifest themselves in results that can be obtained on quantum computers. We model pure dephasing in two different ways; one keeps the full density matrix of the qubits and environments (quantum) while the other uses Kraus operators (classical). We find that a single run of the algorithm yields the same effect in both cases, but running the algorithm twice leads to stark differences. Taking correlations and interplay between different decoherence processes into account leads to a slowing of decoherence effects for balanced functions. For constant functions, the effect is much more pronounced, and there is a qualitative change in the dependence of measurement outcomes on decoherence. We present results obtained on one of the IBM Quantum processors, which fully reproduce the predicted effect regardless of the assumptions made in the derivation. We further illustrate the findings on NV center spin qubits, which show more complex behavior due to a small size of the environment.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper uses Deutsch's algorithm as a proxy for more complex quantum algorithms to distinguish signatures of quantum noise (full density matrix modeling of pure dephasing, retaining environment correlations) from classical noise (Kraus operators). It reports that a single run produces identical effects in both models, but two runs yield stark differences: correlations slow decoherence for balanced functions, while constant functions show more pronounced effects and a qualitative change in measurement outcome dependence on decoherence. IBM Quantum processor experiments fully reproduce the predicted effects independent of modeling assumptions, with additional illustration on NV center spin qubits exhibiting more complex behavior due to small environment size.
Significance. If the central distinctions hold, the work offers a minimal circuit testbed for detecting quantum environmental correlations in computational outcomes, with direct experimental validation on superconducting and spin qubits. The parameter-free reproduction on hardware and the explicit contrast between correlated quantum and uncorrelated classical models are strengths that could inform noise characterization in larger algorithms.
major comments (2)
- [Abstract] Abstract and introduction: the claim that Deutsch's algorithm serves as a valid stand-in for more complex quantum algorithms is load-bearing for the broader significance but receives no further justification or limitation analysis; the single-oracle, two-qubit structure may confine the observed correlation-induced slowing and qualitative shifts to this minimal case rather than revealing universal signatures of quantum environments.
- The abstract states that IBM results 'fully reproduce the predicted effect regardless of the assumptions made in the derivation,' yet the provided text contains no equations, explicit Kraus vs. density-matrix operators, or tabulated measurement probabilities; without these, the support for the reported stark differences after two runs cannot be verified at the level required for the central claim.
minor comments (1)
- The abstract mentions 'one of the IBM Quantum processors' and 'NV center spin qubits' without citing specific device names, run counts, or figure references for the reproduced data.
Simulated Author's Rebuttal
We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below and have revised the manuscript to incorporate the suggested improvements.
read point-by-point responses
-
Referee: [Abstract] Abstract and introduction: the claim that Deutsch's algorithm serves as a valid stand-in for more complex quantum algorithms is load-bearing for the broader significance but receives no further justification or limitation analysis; the single-oracle, two-qubit structure may confine the observed correlation-induced slowing and qualitative shifts to this minimal case rather than revealing universal signatures of quantum environments.
Authors: We agree that additional justification and a limitations analysis are needed to support the use of Deutsch's algorithm as a proxy. In the revised manuscript we have expanded the introduction with a dedicated paragraph explaining that Deutsch's algorithm provides the simplest setting in which a single oracle query exploits quantum interference to distinguish constant from balanced functions; the correlation effects we identify arise precisely from the way environmental memory modifies the relative phases accumulated during the two oracle calls. We have also added a short limitations subsection noting that the two-qubit, single-oracle structure is minimal and that the quantitative slowing or qualitative shifts may not appear identically in larger circuits, while arguing that the underlying mechanism of retained environment-qubit correlations affecting interference is expected to be relevant whenever oracles are implemented via unitary gates on a register coupled to a non-Markovian bath. revision: yes
-
Referee: The abstract states that IBM results 'fully reproduce the predicted effect regardless of the assumptions made in the derivation,' yet the provided text contains no equations, explicit Kraus vs. density-matrix operators, or tabulated measurement probabilities; without these, the support for the reported stark differences after two runs cannot be verified at the level required for the central claim.
Authors: The full manuscript contains explicit derivations of both the quantum density-matrix evolution (retaining system-environment correlations) and the classical Kraus-operator treatment in the Theory and Results sections, together with the resulting measurement probabilities after one and two runs. To address the concern directly, we have added a compact summary table listing the key operators and the analytic probabilities for both models as functions of the dephasing strength, plus a supplementary figure comparing the two-run outcomes. The IBM hardware data are presented with the exact circuit transpilation and post-processing steps, showing quantitative agreement with the quantum-model predictions independent of the modeling assumptions. These additions make the stark differences after two runs and the reproduction on hardware verifiable from the text. revision: yes
Circularity Check
No significant circularity; derivation follows standard methods with independent validation
full rationale
The paper models pure dephasing via full density matrix (quantum) versus Kraus operators (classical) applied to Deutsch's algorithm, deriving that single runs match but double runs differ due to correlations slowing decoherence for balanced functions and causing qualitative shifts for constant ones. These differences are obtained from the open-system equations without reduction to fitted parameters or self-citations. IBM Quantum processor data are presented as an external reproduction of the predicted effect, not a fit or input to the derivation. The stand-in assumption for Deutsch's algorithm is explicit but does not make any reported result equivalent to its inputs by construction. No self-definitional steps, fitted predictions, or load-bearing self-citations are present.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Deutsch's algorithm can serve as a stand-in for more complex quantum algorithms to study environmental noise effects.
Reference graph
Works this paper leans on
-
[1]
L. K. Grover, Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett.80, 4329 (1998)
work page 1998
-
[2]
J. A. Jones, M. Mosca, and R. H. Hansen, Implementa- tion of a quantum search algorithm on a quantum com- puter, Nature393, 344 (1998)
work page 1998
-
[3]
P. R. Giri and V. E. Korepin, A review on quantum search algorithms, Quantum Information Processing16, 315 (2017)
work page 2017
-
[4]
Y. Wang and P. S. Krstic, Prospect of using grover’s searchinthenoisy-intermediate-scalequantum-computer era, Phys. Rev. A102, 042609 (2020)
work page 2020
-
[5]
A. Ajagekar and F. You, Quantum computing for energy systems optimization: Challenges and opportunities, En- ergy179, 76 (2019)
work page 2019
- [6]
-
[7]
Y. Wang, J. E. Kim, and K. Suresh, Opportunities and challenges of quantum computing for engineering opti- mization, Journal of Computing and Information Science in Engineering23, 060817 (2023)
work page 2023
-
[8]
L. Bassman Oftelie, M. Urbanek, M. Metcalf, J. Carter, A. F. Kemper, and W. A. de Jong, Simulating quantum materials with digital quantum computers, Quantum Sci- ence & Technology6, 043002 (2021)
work page 2021
-
[9]
A. Francis, J. Freericks, and A. F. Kemper, Quantum computation of magnon spectra, Physical Review B101, 014411 (2020)
work page 2020
-
[10]
M. Onizhuk and G. Galli, Colloquium: Decoherence of solid-state spin qubits: A computational perspective, Rev. Mod. Phys.97, 021001 (2025)
work page 2025
-
[11]
M. H. Abobeih, Y. Wang, J. Randall, S. Loenen, C. E. Bradley, M. Markham, D. J. Twitchen, B. M. Terhal, and T. H. Taminiau, Fault-tolerant operation of a logical qubit in a diamond quantum processor, Nature606, 884 (2022)
work page 2022
-
[12]
A. R. Mills, C. R. Guinn, M. J. Gullans, A. J. Sigillito, M. M. Feldman, E. Nielsen, and J. R. Petta, Two-qubit silicon quantum processor with operation fidelity exceed- ing 99%, Science Advances8, eabn5130 (2022)
work page 2022
-
[13]
N. Rohling and G. Burkard, Universal quantum comput- ing with spin and valley states, New Journal of Physics 14, 083008 (2012)
work page 2012
-
[14]
Y.-Y. Liao and Y.-N. Chen, Pure dephasing of double- quantum-dot charge qubits in freestanding slabs, Physi- cal Review B—Condensed Matter and Materials Physics 81, 153301 (2010)
work page 2010
-
[15]
T. Salamon and K. Roszak, Entanglement generation be- tween a charge qubit and its bosonic environment during pure dephasing: Dependence on the environment size, Phys. Rev. A96, 032333 (2017)
work page 2017
-
[16]
Y.-D. Li, N. Barraza, G. Alvarado Barrios, E. Solano, and F. Albarrán-Arriagada, Swap test with quantum dot charge qubits, Phys. Rev. Appl.18, 014047 (2022)
work page 2022
-
[17]
A. Ranni, S. Haldar, H. Havir, S. Lehmann, P. Scarlino, A. Baumgartner, C. Schönenberger, C. Thelander, K. A. Dick, P. P. Potts, and V. F. Maisi, Decoherence in a crystal-phase defined double quantum dot charge qubit strongly coupled to a high-impedance resonator, Phys. Rev. Res.6, 043134 (2024)
work page 2024
- [18]
-
[19]
G. Burkard, T. D. Ladd, A. Pan, J. M. Nichol, and J. R. Petta, Semiconductor spin qubits, Rev. Mod. Phys.95, 025003 (2023)
work page 2023
-
[20]
S. Khandelwal, S. Kumar, N. Palazzo, G. Haack, and M. Chipaux, Dynamical nuclear polarization for dissipation-induced entanglement in nv centers, Phys. Rev. B108, 174418 (2023)
work page 2023
-
[21]
F. Fung, E. Rosenfeld, J. D. Schaefer, A. Kabcenell, J. Gieseler, T. X. Zhou, T. Madhavan, N. Aslam, A. Ya- coby, and M. D. Lukin, Toward programmable quantum processors based on spin qubits with mechanically me- diated interactions and transport, Phys. Rev. Lett.132, 263602 (2024)
work page 2024
-
[22]
S. D. Ha, E. Acuna, K. Raach, Z. T. Bloom, T. L. Brecht, J. M. Chappell, M. D. Choi, J. E. Christensen, I. T. Counts, D. Daprano, J. Dodson, K. Eng, D. J. Fialkow, C. A. C. Garcia, W. Ha, T. R. B. Harris, n. holman, I. Khalaf, J. W. Matten, C. A. Peterson, C. E. Plesha, M. J. Ruiz, A. Smith, B. J. Thomas, S. J. Whiteley, T. D. Ladd, M. P. Jura, M. T. Rakh...
work page 2025
-
[23]
H. K. C. Beukers, C. Waas, M. Pasini, H. B. van Om- men, Z. Ademi, M. Iuliano, N. Codreanu, J. M. Brevo- ord, T. Turan, T. H. Taminiau, and R. Hanson, Control of solid-state nuclear spin qubits using an electron spin- 1/2, Phys. Rev. X15, 021011 (2025)
work page 2025
- [24]
-
[25]
Ł. Cywiński, R. M. Lutchyn, C. P. Nave, and S. Das Sarma, How to enhance dephasing time in super- conducting qubits, Physical Review B—Condensed Mat- ter and Materials Physics77, 174509 (2008)
work page 2008
-
[26]
G. C. Knee, K. Kakuyanagi, M.-C. Yeh, Y. Matsuzaki, H. Toida, H. Yamaguchi, S. Saito, A. J. Leggett, and W. J. Munro, A strict experimental test of macroscopic realism in a superconducting flux qubit, Nature Commu- nications7, 13253 (2016)
work page 2016
- [27]
-
[28]
Y. Zhao, Y. Ye, H.-L. Huang, Y. Zhang, D. Wu, H. Guan, Q. Zhu, Z. Wei, T. He, S. Cao, F. Chen, T.-H. Chung, H.Deng, D.Fan, M.Gong, C.Guo, S.Guo, L.Han, N.Li, S. Li, Y. Li, F. Liang, J. Lin, H. Qian, H. Rong, H. Su, L. Sun, S. Wang, Y. Wu, Y. Xu, C. Ying, J. Yu, C. Zha, K. Zhang, Y.-H. Huo, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Realization of an err...
work page 2022
-
[29]
A. Anferov, S. P. Harvey, F. Wan, J. Simon, and D. I. Schuster, Superconducting qubits above 20 ghz operating over 200 mk, PRX Quantum5, 030347 (2024)
work page 2024
-
[30]
M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information(Cambridge University Press, Cambridge, 2000)
work page 2000
-
[31]
Kraus,States, Effects, and Operations: Fundamental Notions of Quantum Theory, edited by A
K. Kraus,States, Effects, and Operations: Fundamental Notions of Quantum Theory, edited by A. Böhm, J. D. Dollard, and W. H. Wootters, Lecture Notes in Physics, Vol. 190 (Springer-Verlag, Berlin/Heidelberg, 1983)
work page 1983
-
[32]
M.J.Hall, J.D.Cresser, L.Li,andE.Andersson,Canon- icalformofmasterequationsandcharacterizationofnon- markovianity, Physical Review A89, 042120 (2014)
work page 2014
-
[33]
S. Nakajima, On quantum theory of transport phenom- ena: Steady diffusion, Progress of Theoretical Physics 20, 948 (1958)
work page 1958
-
[34]
R. Zwanzig, Ensemble method in the theory of irre- versibility, The Journal of Chemical Physics33, 1338 (1960)
work page 1960
-
[35]
H.-P. Breuer and F. Petruccione,The Theory of Open Quantum Systems(Oxford University Press, Oxford, 2002)
work page 2002
-
[36]
T. Harlender and K. Roszak, Transfer and teleportation of system-environment entanglement, Phys. Rev. A105, 11 012407 (2022)
work page 2022
-
[37]
K. Roszak and J. K. Korbicz, Purifying teleportation, Quantum7, 923 (2023)
work page 2023
-
[38]
D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 553 (1992)
work page 1992
-
[39]
K. Roszak and L. Cywiński, Characterization and mea- surement of qubit-environment-entanglement generation during pure dephasing, Phys. Rev. A92, 032310 (2015)
work page 2015
-
[40]
K. Roszak, Criteria for system-environment entangle- ment generation for systems of any size in pure-dephasing evolutions, Phys. Rev. A98, 052344 (2018)
work page 2018
-
[41]
M. W. Doherty, N. B. Manson, P. Delaney, F. Jelezko, J. Wrachtrup, and L. C. Hollenberg, The nitrogen- vacancy colour centre in diamond, Physics Reports528, 1 (2013), the nitrogen-vacancy colour centre in diamond
work page 2013
-
[42]
D. D. Awschalom, R. Hanson, J. Wrachtrup, and B. B. Zhou, Quantum technologies with optically interfaced solid-state spins, Nature Photonics12, 516–527 (2018)
work page 2018
-
[43]
A. A. Wood, E. Lilette, Y. Y. Fein, N. Tomek, L. P. McGuinness, L. C. L. Hollenberg, R. E. Scholten, and A. M. Martin, Quantum measurement of a rapidly rotating spin qubit in diamond, Science Advances4, 10.1126/sciadv.aar7691 (2018)
-
[44]
A. Tchebotareva, S. L. N. Hermans, P. C. Humphreys, D. Voigt, P. J. Harmsma, L. K. Cheng, A. L. Verlaan, N. Dijkhuizen, W. de Jong, A. Dréau, and R. Hanson, Entanglement between a diamond spin qubit and a pho- tonic time-bin qubit at telecom wavelength, Phys. Rev. Lett.123, 063601 (2019)
work page 2019
-
[45]
M. Kuniejand K.Roszak, Estimation ofnuclearpolariza- tion via discrete measurement of nitrogen-vacancy-center spin evolution, Phys. Rev. A111, 032620 (2025)
work page 2025
-
[46]
W. H. Zurek, Decoherence, einselection, and the quan- tum origins of the classical, Rev. Mod. Phys.75, 715 (2003)
work page 2003
-
[47]
Roszak, Measure of qubit-environment entanglement for pure dephasing evolutions, Phys
K. Roszak, Measure of qubit-environment entanglement for pure dephasing evolutions, Phys. Rev. Research2, 043062 (2020)
work page 2020
-
[48]
J. Krzywda and K. Roszak, Phonon-mediated generation of quantum correlations between quantum dot qubits, Scientific reports6, 23753 (2016)
work page 2016
-
[49]
P. Murali, J. M. Baker, A. Javadi-Abhari, F. T. Chong, and M. Martonosi, Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers, inPro- ceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19 (Association for Computing Machinery, New York, NY, USA,...
work page 2019
-
[50]
Preskill, Quantum computing in the nisq era and be- yond, Quantum2, 79 (2018)
J. Preskill, Quantum computing in the nisq era and be- yond, Quantum2, 79 (2018)
work page 2018
-
[51]
L. Childress, M. V. G. Dutt, J. M. Taylor, A. S. Zi- brov, F. Jelezko, J. Wrachtrup, P. R. Hemmer, and M. D. Lukin, Coherent dynamics of coupled electron and nu- clear spin qubits in diamond, Science314, 281 (2006)
work page 2006
-
[52]
N. Zhao, S.-W. Ho, and R.-B. Liu, Decoherence and dy- namical decoupling control of nitrogen vacancy center electron spins in nuclear spin baths, Phys. Rev. B85, 115303 (2012)
work page 2012
-
[53]
D. Kwiatkowski and L. Cywiński, Decoherence of two en- tangled spin qubits coupled to an interacting sparse nu- clear spin bath: Application to nitrogen vacancy centers, Phys. Rev. B98, 155202 (2018)
work page 2018
-
[54]
D. Kwiatkowski, P. Szańkowski, and L. Cywiński, Influ- ence of nuclear spin polarization on the spin-echo signal of an nv-center qubit, Phys. Rev. B101, 155412 (2020)
work page 2020
-
[55]
P. London, J. Scheuer, J.-M. Cai, I. Schwarz, A. Ret- zker, M. B. Plenio, M. Katagiri, T. Teraji, S. Koizumi, J. Isoya, R. Fischer, L. P. McGuinness, B. Naydenov, and F. Jelezko, Detecting and polarizing nuclear spins with double resonance on a single electron spin, Phys. Rev. Lett.111, 067601 (2013)
work page 2013
-
[56]
R. Fischer, C. O. Bretschneider, P. London, D. Budker, D. Gershoni, and L. Frydman, Bulk nuclear polariza- tion enhanced at room temperature by optical pumping, Phys. Rev. Lett.111, 057601 (2013)
work page 2013
-
[57]
D. Pagliero, K. R. K. Rao, P. R. Zangara, S. Dhomkar, H. H. Wong, A. Abril, N. Aslam, A. Parker, J. King, C. E. Avalos, A. Ajoy, J. Wrachtrup, A. Pines, and C. A. Meriles, Multispin-assisted optical pumping of bulk13C nuclear spin polarization in diamond, Phys. Rev. B97, 024422 (2018)
work page 2018
-
[58]
R. Wunderlich, J. Kohlrautz, B. Abel, J. Haase, and J.Meijer,Opticallyinducedcrossrelaxationvianitrogen- related defects for bulk diamond13Chyperpolarization, Phys. Rev. B96, 220407 (2017)
work page 2017
-
[59]
J. Scheuer, I. Schwartz, S. Müller, Q. Chen, I. Dhand, M. B. Plenio, B. Naydenov, and F. Jelezko, Robust tech- niques for polarization and detection of nuclear spin en- sembles, Phys. Rev. B96, 174436 (2017)
work page 2017
-
[60]
F. Poggiali, P. Cappellaro, and N. Fabbri, Measurement of the excited-state transverse hyperfine coupling in nv centers via dynamic nuclear polarization, Phys. Rev. B 95, 195308 (2017)
work page 2017
-
[61]
Y.Hovav, B.Naydenov, F.Jelezko,andN.Bar-Gill,Low- field nuclear polarization using nitrogen vacancy centers in diamonds, Phys. Rev. Lett.120, 060405 (2018)
work page 2018
-
[62]
M. Strzałka and K. Roszak, Detection of entanglement during pure dephasing evolutions for systems and envi- ronments of any size, Phys. Rev. A104, 042411 (2021). Appendix A: Details for quantum computer results The experiment on the quantum computer starts with run of single and double cycles of Deutsch’s algorithm on two neighboring qubits. On a quantum ...
work page 2021
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.