RCQI Bratislava

17.6.2010
Searching via walking: How to find a marked clique of a complete graph using quantum walks
by Mark Hillery, Daniel Reitzner, and Vladimír Bužek
We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resources needed for a quantitative comparison of the efficiency of classical and quantum searches—the number of oracle calls.
Published in Physical Review A |+++|

11.6.2010
Entanglement-annihilating and entanglement-breaking channels
by Lenka Moravčíková and Mário Ziman
We introduce and investigate a family of entanglement-annihilating channels. These channels are capable of destroying any quantum entanglement within the system they act on. We show that they are not necessarily entanglement breaking. In order to achieve this result we analyze the subset of locally entanglement-annihilating channels. In this case, the same local noise applied on each subsystem individually is less entanglement annihilating (with respect to multi-partite entanglement) as the number of subsystems is increasing. Therefore, the bipartite case provides restrictions on the set of local entanglement-annihilating channels for the multipartite case. The introduced concepts are illustrated on the family of single-qubit depolarizing channels.
Published in Journal of Physics A |+++|

2.6.2010
Fast universal quantum computation with railroad-switch local Hamiltonians
by Daniel Nagaj
We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors and the second one requires only 2-local qubit-qutrit projectors. We build on Feynman’s Hamiltonian computer idea [ R. Feynman, Optics News 11, 11 (1985) ] and use a railroad-switch-type clock register. The resources required to simulate a quantum circuit with L gates in this model are O(L) small-dimensional quantum systems (qubits or qutrits), a time-independent Hamiltonian composed of O(L) local, constant norm, projector terms, the possibility to prepare computational basis product states, a running time O(L log2 L), and the possibility to measure a few qubits in the computational basis. Our models also give a simplified proof of the universality of 3-local adiabatic quantum computation.
Published in Journal of Mathematical Physics |+++|