{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T04:28:16Z","timestamp":1648700896070},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,10]]},"abstract":"<jats:p> The most popular model of quantum computation is the quantum circuit model using single and two qubit gates as elementary transformations. Definitions of quantum complexity usually refer to this model. In contrast, we consider the physical interactions among the qubits as the basic computational resource that allows to carry out complex transformations on the quantum register. One method to compare the computational power of different interactions is to examine the complexity of the so-called mutual simulation of interaction Hamiltonians. The physical interaction can simulate other interactions by interspersing the natural time evolution with external control operations. In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the required number of time steps only for special cases (decoupling and time-reversal). These two complexity measures differ significantly. Here we derive lower bounds on the number of time steps for simulations of general interaction graphs. In particular, the simulation of interaction graphs with irrational spectrum requires at least n steps. We discuss as examples graphs that correspond to graph codes and nearest neighbor interactions in 1- and 2-dimensional lattices. In the latter case the lower bounds are almost tight. <\/jats:p>","DOI":"10.1142\/s0129054103002072","type":"journal-article","created":{"date-parts":[[2003,11,24]],"date-time":"2003-11-24T09:26:19Z","timestamp":1069665979000},"page":"889-903","source":"Crossref","is-referenced-by-count":1,"title":["ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING  ARBITRARY INTERACTION GRAPHS"],"prefix":"10.1142","volume":"14","author":[{"given":"DOMINIK","family":"JANZING","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algorithmen und Kognitive Systeme, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, Am Fasanengarten 5, 76 131 Karlsruhe, Germany"}]},{"given":"PAWEL","family":"WOCJAN","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Algorithmen und Kognitive Systeme, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, Am Fasanengarten 5, 76 131 Karlsruhe, Germany"}]},{"given":"THOMAS","family":"BETH","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Algorithmen und Kognitive Systeme, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, Am Fasanengarten 5, 76 131 Karlsruhe, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Spectra of Graphs","author":"Cvetkovi\u0107 D. M.","year":"1995"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"rf10","first-page":"323","volume":"141","author":"Jones J. A.","journal-title":"J. Magn. Resonance"},{"key":"rf12","first-page":"042310\u20130","volume":"61","author":"Leung D. W.","journal-title":"Phys. Rev. A"},{"key":"rf14","series-title":"Santa Fee Institute Studies","volume-title":"Complexity, entropy, and the physics of information","author":"Margolus N.","year":"1990"},{"key":"rf16","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M.","year":"2000"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.25.218"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09441-9"},{"key":"rf26","first-page":"117","volume":"2","author":"Wocjan P.","journal-title":"Quant. Inform. & Comp."},{"key":"rf27","first-page":"133","volume":"2","author":"Wocjan P.","journal-title":"Quant. Inform. & Comp."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.65.042309"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103002072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:37:58Z","timestamp":1565138278000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103002072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":12,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,10]]}},"alternative-id":["10.1142\/S0129054103002072"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103002072","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}