This proposal is about quantum walks and about quantum state discrimination. A preliminary study indicates that it should be possible to distinguish between different types of graphs by applying unambiguous state discrimination to the output state of a quantum walk (a quantum version of a classical random walk), which can take place on an arbitrary graph. The scattering quantum walk will be used, in which the particle making the walk resides on the edges of the graph, and scatters at the vertices at each time step. Quantum searches on graphs will be studied in order to find how the number of steps necessary to find a distinguished vertex depends on the structure of the graph. One goal is to determine how the presence of a distinguished vertex affects the S matrix of a graph, and whether this can be used to detect the presence of a distinguished vertex. Another goal is to compare graphs by placing them in parallel into a larger graph. Theoretical research will be done in the area of quantum state discrimination, an emerging subfield in quantum information and quantum computing. To discriminate two known quantum states the states can be hard-wired into the discriminating device. It is possible, however, to discriminate two completely unknown states when the states are provided in some form of program for the state discriminator [J. Bergou and M. Hillery, PRL 94, 160501 (2005)]. Programmable state discriminators will be examined in order to optimize the read-out of quantum computers for applications to operator testing and quantum algorithms. Their optical implementations and connection to the discrimination of mixed quantum states will be studied. The broader impact of this proposal will be in the training of graduate students and postdocs.
Our research is in the area of quantum information, a field that studies the processing and transmission of information by systems that obey quantum mechanical rules. One goal of the field is to understand what the capabilities of a quantum computer would be. The original proposal was for work in two subfields, quantum walks and quantum state discrimination. Quantum walks can model search problems whose object is to find a special element of a set. A quantum particle moves around a graph, a collection of points connected by lines, trying to find a special structure. Usually one is trying to find a special point, but we showed that much more general structures can be found. In quantum state discrimination, one is given a particle in one of a number of possible quantum states, and the object is to determine which state the particle is in. There are a number of strategies for accomplishing this, and we developed new strategies and expanded the situations that can be treated using some known strategies. State discrimination is useful in both quantum communication and in quantum algorithms. In addition to the proposed work, we developed some new projects. One was on property testing of Boolean functions. A Boolean function maps n-bit sequences to 0 or 1, and we wish to determine whether the function has certain properties or not. We found a quantum algorithm for this problem, which is faster than the best know classical algorithm. Several graduate students participated in this work, and it formed the core of their Ph.D. theses.
