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/0307190 · Physical Review A

Lower bounds on the complexity of simulating quantum gates

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

Published Nov 18, 2003• 36 citations
arXivHTMLPDF

Abstract

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.
DOI
10.1103/physreva.68.052311

Related papers

Gate simulation and lower bounds on the simulation time

Robert Zeier, Markus Grassl, Thomas Beth

Unitary operations are the building blocks of quantum programs. Our task is to design efficient or optimal implementations of these unitary operations by employing the intrinsic physical resources of a given $n$-qubit system. The most common versions of this task are known as Hamiltonian simulation and gate simulation, where Hamiltonian simulation can be seen as an infinitesimal version of the general task of gate simulation. We present a Lie-theoretic approach to Hamiltonian simulation and gate simulation. From this, we derive lower bounds on the time complexity in the $n$-qubit case, generalizing known results to both even and odd $n$. To achieve this we develop a generalization of the so-called magic basis for two-qubits. As a corollary, we note a connection to entanglement measures of concurrence-type.

arXiv:quant-ph/0403082•Physical Review A•Sep 22, 2004•26 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

Finding small two-qubit circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•13 citations

Universal quantum computation and simulation using any entangling Hamiltonian and local unitaries

Jennifer L. Dodd, Michael A. Nielsen, Michael J. Bremner +1 more

What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? We provide an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling n-qubit Hamiltonian and local unitary operations. It follows that universal quantum computation can be performed using any entangling interaction and local unitary operations.

arXiv:quant-ph/0106064•Physical Review A•Apr 4, 2002•156 citations

Exact Two-Qubit Universal Quantum Circuit

Jun Zhang, Jiří Vala, Shankar Sastry +1 more

We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.

arXiv:quant-ph/0212109•Physical Review Letters•Jul 11, 2003•68 citations

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
Unitary operations are the building blocks of quantum programs. Our task is to design efficient or optimal implementations of these unitary operations by employing the intrinsic physical resources of a given nnn-qubit system. The most common versions of this task are known as Hamiltonian simulation and gate simulation, where Hamiltonian simulation can be seen as an infinitesimal version of the general task of gate simulation. We present a Lie-theoretic approach to Hamiltonian simulation and gate simulation. From this, we derive lower bounds on the time complexity in the nnn-qubit case, generalizing known results to both even and odd nnn. To achieve this we develop a generalization of the so-called magic basis for two-qubits. As a corollary, we note a connection to entanglement measures of concurrence-type.
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.
An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.
We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.
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.