Abstract
Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (exactness). Second, through careful accounting (thriftiness), the total query complexity is smaller if subroutines are mostly run on cheaper inputs – a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity. In this work, we show how to achieve both exactness and thriftiness in a more practically relevant setting of quantum time complexity. We generalize the quantum subroutine composition results of (Jeffery 2022) so that, in particular, there is no log factor stemming from error reduction.
We achieve this by employing a novel approach to the design of quantum algorithms based on what we call transducers, and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.
About EQSI
European Quantum Software Institute (EQSI) is an initiative for quantum software research and education in Europe.
The initiative unites 6 leading research institutions to conduct joint research projects and educational and outreach activities, in collaboration with providers of quantum computing infrastructure and industry partners interested in developing quantum algorithms.
EQSI activities include annual workshops and monthly online seminars.
Subscribe to the EQSI mailing list to receive the announcements of the EQSI Colloquium, as well as other news and events from EQSI: https://mlists.ist.utl.pt/mailman/listinfo/groups.pqi.eqsi-info