Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1307.1196 · Physical Review A

Entangling power in deterministic quantum computation with one qubit

Chang‐shui Yu, X. X. Yi, He‐Shan Song, Heng Fan

Published Feb 19, 2013• 8 citations
arXivHTMLPDF

Abstract

Deterministic quantum computing with one qubit (DQC1) is a mixed-state quantum computation algorithm that evaluates the normalized trace of a unitary matrix and is more powerful than the classical counterpart. We find that the normalized trace of the unitary matrix can be directly described by the entangling power of the quantum circuit of DQC1, so the nontrivial DQC1 is always accompanied by nonvanishing entangling power. In addition, it is shown that the entangling power also determines the intrinsic complexity of this quantum computation algorithm, i.e., larger entangling power corresponds to higher complexity. In addition, it is also shown that nonvanishing entangling power always exists in other similar tasks of DQC1.

DOI
10.1103/physreva.87.022322

Related papers

Entanglement and deterministic quantum computing with one qubit

Michel Boyer, Aharon Brodutch, Tal Mor

The role of entanglement and quantum correlations in complex physical systems and quantum information processing devices has become a topic of intense study in the past two decades. In this work we present tools for learning about entanglement and quantum correlations in dynamical systems where the quantum states are mixed and the eigenvalue spectrum is highly degenerate. We apply these results to the deterministic quantum computing with one qubit (DQC1) computation model and show that the states generated in a DQC1 circuit have an eigenvalue structure that makes them difficult to entangle, even when they are relatively far from the completely mixed state. Our results strengthen the conjecture that it may be possible to find quantum algorithms that do not generate entanglement and yet still have an exponential advantage over their classical counterparts.

arXiv:1606.05283•Physical Review A•Feb 21, 2017•22 citations

Quantum dissonance and deterministic quantum computation with a single qubit

Mazhar Ali

Mixed state quantum computation can perform certain tasks which are believed to be efficiently intractable on a classical computer. For a specific model of mixed state quantum computation, namely, deterministic quantum computation with a single qubit (DQC1), recent investigations suggest that quantum correlations other than entanglement might be responsible for the power of DQC1 model. However, strictly speaking, the role of entanglement in this model of computation was not entirely clear. We provide conclusive evidence that there are instances where quantum entanglement is not present in any part of this model, nevertheless we have advantage over classical computation. This establishes the fact that quantum dissonance (a kind of quantum correlations) present in fully separable (FS) states provide power to DQC1 model.

arXiv:1312.1572•International Journal of Quantum Information•Sep 1, 2014•7 citations

Studies on the Role of Entanglement in Mixed-state Quantum Computation

Animesh Datta

In this thesis, I look at the role of quantum entanglement in mixed-state quantum computation. The model we consider is the DQC1 or `power of one qubit' model. I show that there is minimal bipartite entanglement in a typical instance of the DQC1 circuit and even put an upper bound on the possible amount of entanglement. This limited amount of entanglement, however, does not imply that the system is classically simulatable. A matrix product state (MPS) algorithm for a typical instance of the DQC1 system requires exponential classical resources. This exposes a gap between the amount of entanglement and the amount of purely nonclassical correlations in a quantum system. This gap, I suggest, can be filled by quantum discord. I calculate it in a typical instance of the DQC1 circuit and find that the amount of discord is a constant fraction of the maximum possible discord for a system of that size. This allows an interpretation of quantum discord as the resource that drives mixed-state quantum computation. I also study quantum discord as a quantity of independent interest. Its role in the phenomenon of entanglement distribution is studied through an easily comprehensible example. This thesis also contains discussions on the relation between the complexity classes P, BQP and DQC1. Additional material is presented on the connections between the DQC1 model, Jones polynomials and statistical mechanics. The thesis concludes with a discussion of a few open problems related to the DQC1 model, the quantum discord and their scope in quantum information science.

arXiv:0807.4490•Jul 28, 2008•20 citations

Entanglement and the power of one qubit

Animesh Datta, Steven T. Flammia, Carlton M. Caves

The ``power of one qubit'' refers to a computational model that has access to only one pure bit of quantum information, along with $n$ qubits in the totally mixed state. This model, though not as powerful as a pure-state quantum computer, is capable of performing some computational tasks exponentially faster than any known classical algorithm. One such task is to estimate with fixed accuracy the normalized trace of a unitary operator that can be implemented efficiently in a quantum circuit. We show that circuits of this type generally lead to entangled states, and we investigate the amount of entanglement possible in such circuits, as measured by the multiplicative negativity. We show that the multiplicative negativity is bounded by a constant, independent of $n$, for all bipartite divisions of the $n+1$ qubits, and so becomes, when $n$ is large, a vanishingly small fraction of the maximum possible multiplicative negativity for roughly equal divisions. This suggests that the global nature of entanglement is a more important resource for quantum computation than the magnitude of the entanglement.

arXiv:quant-ph/0505213•Physical Review A•Oct 18, 2005•372 citations

Hardness of Classically Simulating the One-Clean-Qubit Model

Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons

Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.

arXiv:1312.2496•Physical Review Letters•Apr 2, 2014•99 citations

Promoting quantum correlations in deterministic quantum computation with a one-qubit model via postselection

Elisa I. Goettems, Thiago O. Maciel, Diogo O. Soares-Pinto +1 more

The deterministic quantum computation with one qubit (DQC1) model is a restricted model of quantum computing able to calculate efficiently the normalized trace of a unitary matrix. In this work, we analyze the quantum correlations called entanglement, Bell's nonlocality, quantum discord, and coherence generated by the DQC1 circuit considering only two qubits (auxiliary and control). For the standard DQC1 model, only quantum discord and coherence appear. By introducing a filter in the circuit we purify the auxiliary qubit, taking it out from the totally mixed state and consequently promoting other quantum correlations between the qubits, such as entanglement and Bell's nonlocality. Through the optimization of the purification process, we conclude that even a small purification is enough to generate entanglement and Bell's nonlocality. We obtain, that by applying the purification process repeatedly an average of 12 times, the auxiliary qubit becomes $99%$ pure. In this situation, almost maximally entangled states are achieved, which almost maximally violate Bell's inequality. This result suggests that with a simple modification, the DQC1 model can be promoted to a universal model of quantum computing.

arXiv:2010.10898•Physical Review A•Apr 19, 2021•11 citations
Deterministic quantum computing with one qubit (DQC1) is a mixed-state quantum computation algorithm that evaluates the normalized trace of a unitary matrix and is more powerful than the classical counterpart. We find that the normalized trace of the unitary matrix can be directly described by the entangling power of the quantum circuit of DQC1, so the nontrivial DQC1 is always accompanied by nonvanishing entangling power. In addition, it is shown that the entangling power also determines the intrinsic complexity of this quantum computation algorithm, i.e., larger entangling power corresponds to higher complexity. In addition, it is also shown that nonvanishing entangling power always exists in other similar tasks of DQC1.
The role of entanglement and quantum correlations in complex physical systems and quantum information processing devices has become a topic of intense study in the past two decades. In this work we present tools for learning about entanglement and quantum correlations in dynamical systems where the quantum states are mixed and the eigenvalue spectrum is highly degenerate. We apply these results to the deterministic quantum computing with one qubit (DQC1) computation model and show that the states generated in a DQC1 circuit have an eigenvalue structure that makes them difficult to entangle, even when they are relatively far from the completely mixed state. Our results strengthen the conjecture that it may be possible to find quantum algorithms that do not generate entanglement and yet still have an exponential advantage over their classical counterparts.
Mixed state quantum computation can perform certain tasks which are believed to be efficiently intractable on a classical computer. For a specific model of mixed state quantum computation, namely, deterministic quantum computation with a single qubit (DQC1), recent investigations suggest that quantum correlations other than entanglement might be responsible for the power of DQC1 model. However, strictly speaking, the role of entanglement in this model of computation was not entirely clear. We provide conclusive evidence that there are instances where quantum entanglement is not present in any part of this model, nevertheless we have advantage over classical computation. This establishes the fact that quantum dissonance (a kind of quantum correlations) present in fully separable (FS) states provide power to DQC1 model.
In this thesis, I look at the role of quantum entanglement in mixed-state quantum computation. The model we consider is the DQC1 or `power of one qubit' model. I show that there is minimal bipartite entanglement in a typical instance of the DQC1 circuit and even put an upper bound on the possible amount of entanglement. This limited amount of entanglement, however, does not imply that the system is classically simulatable. A matrix product state (MPS) algorithm for a typical instance of the DQC1 system requires exponential classical resources. This exposes a gap between the amount of entanglement and the amount of purely nonclassical correlations in a quantum system. This gap, I suggest, can be filled by quantum discord. I calculate it in a typical instance of the DQC1 circuit and find that the amount of discord is a constant fraction of the maximum possible discord for a system of that size. This allows an interpretation of quantum discord as the resource that drives mixed-state quantum computation. I also study quantum discord as a quantity of independent interest. Its role in the phenomenon of entanglement distribution is studied through an easily comprehensible example. This thesis also contains discussions on the relation between the complexity classes P, BQP and DQC1. Additional material is presented on the connections between the DQC1 model, Jones polynomials and statistical mechanics. The thesis concludes with a discussion of a few open problems related to the DQC1 model, the quantum discord and their scope in quantum information science.
The ``power of one qubit'' refers to a computational model that has access to only one pure bit of quantum information, along with nnn qubits in the totally mixed state. This model, though not as powerful as a pure-state quantum computer, is capable of performing some computational tasks exponentially faster than any known classical algorithm. One such task is to estimate with fixed accuracy the normalized trace of a unitary operator that can be implemented efficiently in a quantum circuit. We show that circuits of this type generally lead to entangled states, and we investigate the amount of entanglement possible in such circuits, as measured by the multiplicative negativity. We show that the multiplicative negativity is bounded by a constant, independent of nnn, for all bipartite divisions of the n+1n+1n+1 qubits, and so becomes, when nnn is large, a vanishingly small fraction of the maximum possible multiplicative negativity for roughly equal divisions. This suggests that the global nature of entanglement is a more important resource for quantum computation than the magnitude of the entanglement.
Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.
The deterministic quantum computation with one qubit (DQC1) model is a restricted model of quantum computing able to calculate efficiently the normalized trace of a unitary matrix. In this work, we analyze the quantum correlations called entanglement, Bell's nonlocality, quantum discord, and coherence generated by the DQC1 circuit considering only two qubits (auxiliary and control). For the standard DQC1 model, only quantum discord and coherence appear. By introducing a filter in the circuit we purify the auxiliary qubit, taking it out from the totally mixed state and consequently promoting other quantum correlations between the qubits, such as entanglement and Bell's nonlocality. Through the optimization of the purification process, we conclude that even a small purification is enough to generate entanglement and Bell's nonlocality. We obtain, that by applying the purification process repeatedly an average of 12 times, the auxiliary qubit becomes 9999%99 pure. In this situation, almost maximally entangled states are achieved, which almost maximally violate Bell's inequality. This result suggests that with a simple modification, the DQC1 model can be promoted to a universal model of quantum computing.