quantum-computing

Efficient Classical Simulation of the DQC1 Circuit with Zero Discord

Shalin Jose, Akshay Kannan Sairam, and Anil Shaji

15 min read

0 likes

⚡ Quantum Brief

Researchers demonstrated that the DQC1 quantum circuit—known for estimating unitary traces—can be efficiently simulated classically when quantum discord is zero, disproving a 2010 conjecture suggesting potential quantum advantage under such conditions. The study confirms quantum discord as a critical resource for exponential speedups in mixed-state quantum computing, aligning with prior theories but refuting claims that DQC1 could outperform classical systems without it. Experiments involved a 12-qubit zero-discord unitary, analyzing output probabilities to show classical simulability, reinforcing the link between non-classical correlations and computational power. This work advances the understanding of quantum resources in mixed-state models, where entanglement alone (unlike in pure states) doesn’t fully explain speedups, highlighting discord’s unique role. Published in Quantum (October 2025), the findings resolve a long-standing debate, clarifying that zero discord eliminates DQC1’s quantum advantage, with implications for resource theories in quantum algorithms.

AI Audio Summary

0:00 / 0:00

Click to play

Unsplash · Validated Fallback

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractA 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 summaryIdentifying 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.5Cited byCould not fetch Crossref cited-by data during last attempt 2025-10-28 15:12:04: Could not fetch cited-by data for 10.22331/q-2025-10-28-1895 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-10-28 15:12:04: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractA 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 summaryIdentifying 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.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Efficient Classical Simulation of the DQC1 Circuit with Zero Discord

Tags

Source Information