Efficient Classical Simulation of the DQC1 Circuit with Zero Discord

Shalin Jose; Akshay Kannan Sairam; Anil Shaji

doi:10.22331/q-2025-10-28-1895

Efficient Classical Simulation of the DQC1 Circuit with Zero Discord

Shalin Jose¹, Akshay Kannan Sairam², and Anil Shaji^1,3

¹School of Physics, Indian Institute of Science Education and Research Thiruvananthapuram, Maruthamala PO, Vithura, Kerala, 695551, India
²Department of Instrumentation and Applied Physics, Indian Institute of Science, Bengaluru, Karnataka, 560012, India
³Center for High Performance Computing, Indian Institute of Science Education and Research Thiruvananthapuram, Maruthamala PO, Vithura, Kerala, 695551, India

Published:	2025-10-28, volume 9, page 1895
Editor:	Himadri Shekhar Dhar
Eprint:	arXiv:2411.18348v4
Doi:	https://doi.org/10.22331/q-2025-10-28-1895
Citation:	Quantum 9, 1895 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A path for efficient classical simulation of the DQC1 circuit that estimates the trace of an implementable unitary under the zero discord condition [17] is presented. This result reinforces the status of non-classical correlations quantified by quantum discord and related measures as the key resource enabling exponential speedups in mixed state quantum computation.

Featured image: Probability, Pq of measuring |00 · · · 0⟩ at the output of a randomly generated 12-qubit zero discord unitary, for input state |00 · · · 0⟩, is plotted against number of -1 eigenvalues of the unitary.

Popular summary

Identifying the quantum resources that enable exponential speedup in quantum computing is one of the biggest challenges in the field. Entanglement is already proven to be a necessary resource for speedup in the case of pure state quantum computing. However, for mixed state quantum computing, a comprehensive understanding of the resources that enable exponential speedup is still missing.

Our work represents a substantial advance in settling the open problem of identifying the quantum resources that enable exponential speedup in mixed state quantum computing. Our focus here is specifically the DQC1 model. To explain the quantum speedup observed in the DQC1 algorithm, the presence of Quantum Discord, a measure of non-classical correlations, was used in Phys. Rev. Lett. 100, 050502. However, it was conjectured by Dakic et al. [PRL 105, 19052 (2010)], that even under zero discord conditions, the DQC1 model may yield a quantum advantage implying that quantum discord may not be resource for mixed state quantum computing. We falsify this conjecture by showing that in the absence of quantum discord between the top qubit of DQC1 and the rest, it is possible to simulate the DQC1 circuit efficiently using classical means.

► BibTeX data

@article{Jose2025efficientclassical,
  doi = {10.22331/q-2025-10-28-1895},
  url = {https://doi.org/10.22331/q-2025-10-28-1895},
  title = {Efficient {C}lassical {S}imulation of the {DQC}1 {C}ircuit with {Z}ero {D}iscord},
  author = {Jose, Shalin and Sairam, Akshay Kannan and Shaji, Anil},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1895},
  month = oct,
  year = {2025}
}

► References

[1] Frank Arute et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[2] Davide Castelvecchi. ``Ibm releases first-ever 1,000-qubit quantum chip''. Nature 624, 238 (2023).
https://doi.org/10.1038/D41586-023-03854-1

[3] Richard Jozsa and Noah Linden. ``On the role of entanglement in quantum-computational speed-up''. Proc. Roy. Soc. London. Ser. A: Math. Phys. and Engg. Sci. 459, 2011–2032 (2003).
https://doi.org/10.1098/rspa.2002.1097

[4] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).
https://doi.org/10.1103/PhysRevA.70.052328

[5] Guifré Vidal. ``Efficient classical simulation of slightly entangled quantum computations''. Phys. Rev. Lett. 91, 147902 (2003).
https://doi.org/10.1103/PhysRevLett.91.147902

[6] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

[7] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. ``Estimating outcome probabilities of quantum circuits using quasiprobabilities''. Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/10.1103/PhysRevLett.115.070501

[8] Andrew Jackson, Theodoros Kapourniotis, and Animesh Datta. ``Partition-function estimation: Quantum and quantum-inspired algorithms''. Phys. Rev. A 107, 012421 (2023).
https://doi.org/10.1103/PhysRevA.107.012421

[9] S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu, and R. Schack. ``Separability of very noisy mixed states and implications for nmr quantum computing''. Phys. Rev. Lett. 83, 1054–1057 (1999).
https://doi.org/10.1103/PhysRevLett.83.1054

[10] E. Knill and R. Laflamme. ``Power of one bit of quantum information''. Phys. Rev. Lett. 81, 5672–5675 (1998).
https://doi.org/10.1103/PhysRevLett.81.5672

[11] David A. Meyer. ``Sophisticated quantum search without entanglement''. Phys. Rev. Lett. 85, 2014–2017 (2000).
https://doi.org/10.1103/PhysRevLett.85.2014

[12] Juan Bermejo-Vega, Nicolas Delfosse, Dan E Browne, Cihan Okay, and Robert Raussendorf. ``Contextuality as a resource for models of quantum computation with qubits''. Phys. Rev. Lett. 119, 120505 (2017).
https://doi.org/10.1103/PhysRevLett.119.120505

[13] Victor Veitch, Christopher Ferrie, David Gross, and Joseph Emerson. ``Negative quasi-probability as a resource for quantum computation''. New J. Phys. 14, 113011 (2012).
https://doi.org/10.1088/1367-2630/14/11/113011

[14] Harold Ollivier and Wojciech H. Zurek. ``Quantum discord: A measure of the quantumness of correlations''. Phys. Rev. Lett. 88, 017901 (2001).
https://doi.org/10.1103/PhysRevLett.88.017901

[15] Leah Henderson and Vlatko Vedral. ``Classical, quantum and total correlations''. J. Phys. A: Math. Gen. 34, 6899 (2001).
https://doi.org/10.1088/0305-4470/34/35/315

[16] Animesh Datta, Anil Shaji, and Carlton M Caves. ``Quantum discord and the power of one qubit''. Phys. Rev. Lett. 100, 050502 (2008).
https://doi.org/10.1103/PhysRevLett.100.050502

[17] Borivoje Dakić, Vlatko Vedral, and Časlav Brukner. ``Necessary and sufficient condition for nonzero quantum discord''. Phys. Rev. Lett. 105, 190502 (2010).
https://doi.org/10.1103/PhysRevLett.105.190502

[18] Animesh Datta and Anil Shaji. ``Quantum discord and quantum computing—an appraisal''. Int. J. Quant. Info. 9, 1787–1805 (2011).
https://doi.org/10.1142/S0219749911008416

[19] Jiajun Ma, Benjamin Yadin, Davide Girolami, Vlatko Vedral, and Mile Gu. ``Converting coherence to quantum correlations''. Phys. Rev. Lett. 116, 160407 (2016).
https://doi.org/10.1103/PhysRevLett.116.160407

[20] Bryan Eastin. ``Simulating concordant computations'' (2010). arXiv:1006.4402.
arXiv:1006.4402

[21] David Poulin, Robin Blume-Kohout, Raymond Laflamme, and Harold Ollivier. ``Exponential speedup with a single bit of quantum information: Measuring the average fidelity decay''. Phys. Rev. Lett. 92, 177906 (2004).
https://doi.org/10.1103/PhysRevLett.92.177906

[22] Emanuel Knill and Raymond Laflamme. ``Quantum computing and quadratically signed weight enumerators''. Inf. Process. Lett. 79, 173–179 (2001).
https://doi.org/10.1016/S0020-0190(00)00222-2

[23] Peter W. Shor and Stephen P. Jordan. ``Estimating jones polynomials is a complete problem for one clean qubit''. Quant. Info. Comput. 8, 681–714 (2008).
https://doi.org/10.26421/QIC8.8-9-1

[24] Sergio Boixo and Rolando D Somma. ``Parameter estimation with mixed-state quantum computation''. Phys. Rev. A 77, 052320 (2008).
https://doi.org/10.1103/PhysRevA.77.052320

[25] Animesh Datta, Steven T. Flammia, and Carlton M. Caves. ``Entanglement and the power of one qubit''. Phys. Rev. A 72, 042316 (2005).
https://doi.org/10.1103/PhysRevA.72.042316

[26] Fumio Hiai and Dénes Petz. ``The semicircle law, free random variables and entropy''. Number 77 in Mathematical Surveys and Monographs. American Mathematical Society. (2000).
https://doi.org/10.1090/surv/077

[27] A Yu Kitaev. ``Quantum computations: algorithms and error correction''. Russian Math. Surveys 52, 1191 (1997).
https://doi.org/10.1070/RM1997v052n06ABEH002155

[28] Christopher M. Dawson and Michael A. Nielsen. ``The solovay-kitaev algorithm'' (2005). arXiv:quant-ph/0505030.
arXiv:quant-ph/0505030

[29] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. ``Elementary gates for quantum computation''. Phys. Rev. A 52, 3457–3467 (1995).
https://doi.org/10.1103/PhysRevA.52.3457

[30] Adriano Barenco. ``A universal two-bit gate for quantum computation''. Proc. R. Soc. Lond. 449:, 679––683 (1995).
https://doi.org/10.1098/rspa.1995.0066

[31] Alastair Kay. ``Perfect, efficient, state transfer and its application as a constructive tool''. Int. J. Quant. Info. 08, 641–676 (2010).
https://doi.org/10.1142/S0219749910006514

[32] Daniel Nagaj. ``Universal two-body-hamiltonian quantum computing''. Phys. Rev. A 85, 32330 (2012).
https://doi.org/10.1103/PhysRevA.85.032330

[33] Rüdiger Achilles and Andrea Bonfiglioli. ``The early proofs of the theorem of campbell, baker, hausdorff, and dynkin''. Archive for History of Exact Sciences 66, 295–358 (2012).
https://doi.org/10.1007/s00407-012-0095-8

[34] Dorit Aharonov and Amnon Ta-Shma. ``Adiabatic quantum state generation and statistical zero knowledge''. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing. Page 20–29. STOC '03New York, NY, USA (2003). Association for Computing Machinery.
https://doi.org/10.1145/780542.780546

[35] Seth Lloyd. ``Universal quantum simulators''. Science 273, 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073

[36] Maarten Van Den Nest. ``Simulating quantum computers with probabilistic methods''. Quantum Info. Comput. 11, 784–812 (2011).
https://doi.org/10.26421/QIC11.9-10-5

[37] Animesh Datta and Guifre Vidal. ``Role of entanglement and correlations in mixed-state quantum computation''. Phys. Rev. A 75, 042310 (2007).
https://doi.org/10.1103/PhysRevA.75.042310

[38] Elliott H. Lieb and Derek W. Robinson. ``The finite group velocity of quantum spin systems''. Comm. Math. Phys. 28, 251–257 (1972).
https://doi.org/10.1007/BF01645779

[39] Mona Arabzadeh, Mahboobeh Houshmand, Mehdi Sedighi, and Morteza Saheb Zamani. ``Quantum-logic synthesis of hermitian gates''. J. Emerg. Technol. Comput. Syst. 12 (2016).
https://doi.org/10.1145/2794263

[40] Mahboobeh Houshmand, Morteza Saheb Zamani, Mehdi Sedighi, and Mona Arabzadeh. ``Decomposition of diagonal hermitian quantum gates using multiple-controlled pauli z gates''. J. Emerg. Technol. Comput. Syst. 11 (2015).
https://doi.org/10.1145/2629526

[41] Shihao Zhang, Junda Wu, and Lvzhou Li. ``Characterization, synthesis, and optimization of quantum circuits over multiple-control $\mathit{Z}$-rotation gates: A systematic study''. Phys. Rev. A 108, 022603 (2023).
https://doi.org/10.1103/PhysRevA.108.022603

[42] Jonathan Welch, Alex Bocharov, and Krysta M. Svore. ``Efficient approximation of diagonal unitaries over the clifford+t basis''. Quantum Info. Comput. 16, 87–104 (2016).
https://doi.org/10.26421/QIC16.1-2-6

[43] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. Cambridge (2010).
https://doi.org/10.1017/CBO9780511976667

[44] Ken M. Nakanishi, Takahiko Satoh, and Synge Todo. ``Decompositions of multiple controlled-$z$ gates on various qubit-coupling graphs''. Phys. Rev. A 110, 012604 (2024).
https://doi.org/10.1103/PhysRevA.110.012604

[45] Nicolas Loizeau, J. Clayton Peacock, and Dries Sels. ``Codebase release 1.5 for PauliStrings.jl''. SciPost Phys. CodebasesPages 54–r1.5 (2025).
https://doi.org/10.21468/SciPostPhysCodeb.54-r1.5

Cited by

[1] Takato Mori, "Quantum correlation beyond entanglement: Holographic discord and multipartite generalizations", arXiv:2506.02131, (2025).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-12 04:59:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-12 04:59:23).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.