Decision problems in quantum information

The birth of the field of quantum information renewed interest in the foundations of quantum mechanics. In this field fundamental concepts and fascinating applications are only a step away from one another. For example, Bell's theorem is the basis for cryptographic protocols, and a quantum computer can perform tasks, such as finding the prime factors of a number, much faster than a classical computer. These examples embody two major trends in the field, quantum communication and quantum algorithms. In both, decision problems play a central role. A decision problem consists of determining what decision a quantum system made, i.e. which of several possible - that is compatible with its present state - alternatives it took at some juncture in the past. Here we propose to develop tools to solve such problems. The problems we propose can occur in communication or algorithmic scenarios and are selected from the areas of state discrimination, quantum walks and complex networks, and function property testing. The results of these studies will be optimized quantum measurements and novel quantum algorithms and will be disseminated in leading peer reviewed journals (about six articles/year), presented as invited talks at major international conferences (about four invited talks/year), and will generate contributed talks (about four/year) and Ph.D. theses (about four during the lifetime of the project). Through this project we expect to move closer toward answering several “Big Questions”: What kinds of tasks can a quantum computer perform better than a classical one? How a past decision is manifest in measurements performed on the quantum system in the present? Can we, aided by the measurement, optimize our own decision about these alternatives and how is that compatible with such universal concepts as the Free Will of the observer? Answers to these questions will have enduring effects. In particular, the question of Free Will has the potential of being paradigm changing.