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:quant-ph/0112168 · Physical Review Letters

Interaction Cost of Nonlocal Gates

Guifré Vidal, Klemens Hammerer, J. I. Cirac

Published May 24, 2002• 88 citations
arXivHTMLPDF

Abstract

We introduce the interaction cost of a nonlocal gate as the minimal time of interaction required to perform the gate when assisting the process with fast local unitaries. This cost, of interest both in the areas of quantum control and quantum information, depends on the specific interaction, and allows one to compare in an operationally meaningful manner any two nonlocal gates. In the case of a two-qubit system, an analytical expression for the interaction cost of any unitary operation given any coupling Hamiltonian is obtained. One gate may be more time consuming than another for any possible interaction. This defines a partial order structure in the set of nonlocal gates, that compares their degree of nonlocality. We analytically characterize this partial order in a region of the set of two-qubit gates.

DOI
10.1103/physrevlett.88.237902

Related papers

Characterization of nonlocal gates

Klemens Hammerer, Guifré Vidal, J. I. Cirac

A nonlocal unitary transformation of two-qubits occurs when some Hamiltonian interaction couples them. Here we characterize the amount, as measured by time, of interaction required to perform two-qubit gates, when also arbitrarily fast, local unitary transformations can be applied on each qubit. The minimal required time of interaction, or interaction cost, defines an operational notion of the degree of nonlocality of gates. We characterize a partial order structure based on this notion. We also investigate the interaction cost of several communication tasks, and determine which gates are able to accomplish them. This classifies two-qubit gates into four categories, differing in their capability to transmit classical, as well as quantum, bits of information.

arXiv:quant-ph/0205100•Physical Review A•Dec 31, 2002•90 citations

Optimal simulation of two-qubit Hamiltonians using general local operations

C. H. Bennett, J. I. Cirac, Matthew Leifer +4 more

We consider the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian $H\ensuremath{\ne}{H}_{A}{+H}_{B}.$ We consider the achievable space of Hamiltonians ${H}^{\ensuremath{'}}$ such that the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}t}$ can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and ${H}^{\ensuremath{'}},$ there exists a scale factor s such that for all times t the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}\mathrm{st}}$ can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and ${H}^{\ensuremath{'}},$ we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.

arXiv:quant-ph/0107035•Physical Review A•Jul 19, 2002•110 citations

Optimal simulations of two-qubit Hamiltonians using general local operations

CH Bennett, JI Cirac, MS Leifer +4 more

We consider the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian Hnot equalH(A)+H-B. We consider the achievable space of Hamiltonians H-' such that the evolution e(-iH')t can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and H-', there exists a scale factor s such that for all times t the evolution e(-iH')st can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and H-', we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.

•Jul 1, 2002•0 citations

Lower bounds on non-local computation from controllable correlation

Richard Cleve, Alex May

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\text{SWAP}}$, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.

quant-pharXiv:2602.00255•Feb 3, 2026•0 citations

Practicality of time-optimal two-qubit Hamiltonian simulation

Henry L. Haselgrove, Michael A. Nielsen, Tobias J. Osborne

What is the time-optimal way of using a set of control Hamiltonians to obtain a desired interaction? Vidal, Hammerer, and Cirac [Phys. Rev. Lett. $88,$ 237902 (2002)] have obtained a set of powerful results characterizing the time-optimal simulation of a two-qubit quantum gate using a fixed interaction Hamiltonian and fast local control over the individual qubits. How practically useful are these results? We prove that there are two-qubit Hamiltonians such that time-optimal simulation requires infinitely many steps of evolution, each infinitesimally small, and thus is physically impractical. A procedure is given to determine which two-qubit Hamiltonians have this property, and we show that almost all Hamiltonians do. Finally, we determine some bounds on the penalty that must be paid in the simulation time if the number of steps is fixed at a finite number, and show that the cost in simulation time is not too great.

arXiv:quant-ph/0303070•Physical Review A•Oct 6, 2003•10 citations

Lower bounds on the complexity of simulating quantum gates

Andrew M. Childs, Henry L. Haselgrove, Michael A. Nielsen

We give a simple proof of a formula for the minimal time required to simulate a two-qubit unitary operation using a fixed two-qubit Hamiltonian together with fast local unitaries. We also note that a related lower bound holds for arbitrary n-qubit gates.

arXiv:quant-ph/0307190•Physical Review A•Nov 18, 2003•36 citations
We introduce the interaction cost of a nonlocal gate as the minimal time of interaction required to perform the gate when assisting the process with fast local unitaries. This cost, of interest both in the areas of quantum control and quantum information, depends on the specific interaction, and allows one to compare in an operationally meaningful manner any two nonlocal gates. In the case of a two-qubit system, an analytical expression for the interaction cost of any unitary operation given any coupling Hamiltonian is obtained. One gate may be more time consuming than another for any possible interaction. This defines a partial order structure in the set of nonlocal gates, that compares their degree of nonlocality. We analytically characterize this partial order in a region of the set of two-qubit gates.
A nonlocal unitary transformation of two-qubits occurs when some Hamiltonian interaction couples them. Here we characterize the amount, as measured by time, of interaction required to perform two-qubit gates, when also arbitrarily fast, local unitary transformations can be applied on each qubit. The minimal required time of interaction, or interaction cost, defines an operational notion of the degree of nonlocality of gates. We characterize a partial order structure based on this notion. We also investigate the interaction cost of several communication tasks, and determine which gates are able to accomplish them. This classifies two-qubit gates into four categories, differing in their capability to transmit classical, as well as quantum, bits of information.
We consider the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian $H\ensuremath{\ne}{H}_{A}{+H}_{B}.$ We consider the achievable space of Hamiltonians ${H}^{\ensuremath{'}}$ such that the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}t}$ can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and ${H}^{\ensuremath{'}},$ there exists a scale factor s such that for all times t the evolution ${e}^{\ensuremath{-}{\mathrm{iH}}^{\ensuremath{'}}\mathrm{st}}$ can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and ${H}^{\ensuremath{'}},$ we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.
We consider the simulation of the dynamics of one nonlocal Hamiltonian by another, allowing arbitrary local resources but no entanglement or classical communication. We characterize notions of simulation, and proceed to focus on deterministic simulation involving one copy of the system. More specifically, two otherwise isolated systems A and B interact by a nonlocal Hamiltonian Hnot equalH(A)+H-B. We consider the achievable space of Hamiltonians H-' such that the evolution e(-iH')t can be simulated by the interaction H interspersed with local operations. For any dimensions of A and B, and any nonlocal Hamiltonians H and H-', there exists a scale factor s such that for all times t the evolution e(-iH')st can be simulated by H acting for time t interspersed with local operations. For two-qubit Hamiltonians H and H-', we calculate the optimal s and give protocols achieving it. The optimal protocols do not require local ancillas, and can be understood geometrically in terms of a polyhedron defined by a partial order on the set of two-qubit Hamiltonians.
Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, SWAP\sqrt{\text{SWAP}}SWAP​, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.
What is the time-optimal way of using a set of control Hamiltonians to obtain a desired interaction? Vidal, Hammerer, and Cirac [Phys. Rev. Lett. 88,88,88, 237902 (2002)] have obtained a set of powerful results characterizing the time-optimal simulation of a two-qubit quantum gate using a fixed interaction Hamiltonian and fast local control over the individual qubits. How practically useful are these results? We prove that there are two-qubit Hamiltonians such that time-optimal simulation requires infinitely many steps of evolution, each infinitesimally small, and thus is physically impractical. A procedure is given to determine which two-qubit Hamiltonians have this property, and we show that almost all Hamiltonians do. Finally, we determine some bounds on the penalty that must be paid in the simulation time if the number of steps is fixed at a finite number, and show that the cost in simulation time is not too great.