Search NASA⌕ Search

Engineering topics

Reitzner, Daniel

Publications and source records attributed to Reitzner, Daniel.

Finding structural anomalies in graphs by means of quantum walks

We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are N spokes, we show that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in O({radical}(N)) steps. We initially find that if all except one of the spokes have loops, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Approximating incompatible von Neumann measurements simultaneously

We study the problem of performing orthogonal qubit measurements simultaneously. Since these measurements are incompatible, one has to accept additional imprecision. An optimal joint measurement is the one with the least possible imprecision. All earlier considerations of this problem have concerned only joint measurability of observables, while in this work we also take into account conditional state transformations (i.e., instruments). We characterize the optimal joint instrument for two orthogonal von Neumann instruments as being the Lueders instrument of the optimal joint observable.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Searching via walking: How to find a marked clique of a complete graph using quantum walks

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.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗