6533b82afe1ef96bd128c120

RESEARCH PRODUCT

Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity

Agnis ăźRiźš

subject

Discrete mathematicsComputer scienceExistential quantificationModel of computationTheoryofComputation_GENERALComputerSystemsOrganization_MISCELLANEOUSBipartite graphGraph (abstract data type)Quantum algorithmAdjacency matrixBoolean functionQuantumComputer Science::DatabasesMathematicsofComputing_DISCRETEMATHEMATICS

description

Span program is a linear-algebraic model of computation which can be used to design quantum algorithms. For any Boolean function there exists a span program that leads to a quantum algorithm with optimal quantum query complexity. In general, finding such span programs is not an easy task. In this work, given a query access to the adjacency matrix of a simple graph G with n vertices, we provide two new span-program-based quantum algorithms:an algorithm for testing if the graph is bipartite that uses $$On\sqrt{n}$$ quantum queries;an algorithm for testing if the graph is connected that uses $$On\sqrt{n}$$ quantum queries.

yearjournalcountryeditionlanguage
2016-01-01
https://doi.org/10.1007/978-3-319-29817-7_4