A Complexity Measure for Continuous Time Quantum Algorithms
By Dominik Janzing, T. Beth. 2000
7 citations recorded by the source corpus.
We consider unitary dynamical evolutions on n qubits caused by time dependent pair-interaction Hamiltonians and show that the running time of a parallelized two-qubit gate network simulating the evolution is given by the time integral over the chromatic index of the interaction graph. This defines a complexity measure of continuous and discrete quantum algorithms which are in exact one-to-one correspondence. Furthermore we prove a lower bound on the growth of large-scale entanglement depending on the chromatic index.
Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- B. Schoelkopf
- Dominik Janzing
- Rafael Chaves
- Bernhard Schölkopf
- Jan Peters
- Kun Zhang
- David Lopez-Paz
- Joris M. Mooij
In Atomic and Molecular Physics, and Optics
Citations in the corpus
- Algorithmic independence of initial condition and dynamical law in thermodynamics and causal inference (2015, background): “ the laws of computation [29], future research may dene a ’more physical version’ of Kby computation models whose elementary steps directly use physically realistic particle 2 interactions, see e.g. [30, 31, 32]. Moreover, quantum thermodynamics [33] should rather rely on quantum Kolmogorov complexi”
- Simulating Hamiltonians in quantum networks: Efficient schemes and complexity bounds (2001, background): “This concept has been introduced in [11] in a related context in order to quantify the complexity of a general pair-interaction Hamiltonian on n qubits.”