Please use this identifier to cite or link to this item:
Title: Evaluation of exact quantum query complexities by semidefinite programming
Authors: Uyanık, Kıvanç
Keywords: Quantum algorithms
Semidefinite programming
Exact query complexity
Issue Date: Jun-2019
Publisher: Springer Verlag
Abstract: One of the difficult tasks in quantum computation is inventing efficient exact quantum algorithms, which are the quantum algorithms that output the correct answer with certainty on any input. We improve and generalize the semidefinite programming (SDP) method of Montanaro et al. (Algorithmica 71:775-796, 2015) in order to evaluate exact quantum query complexities of partial functions. We present a more systematical approach to achieve the inspired result by Montanaro et al. for the function EXACT24, which is the Boolean function of 4 bits that output only when 2 of the input bits are equal to 1. The same approach also allows us to reduce the size of the ancilla space used by the algorithms that evaluate symmetric functions like EXACT36. We employ the generalized SDP to verify the complexities of the earliest and best known quantum algorithms in the literature, namely, Deutsch-Jozsa and Grover algorithms for a small number of input bits. We utilized the method to solve the weight decision problem of bit strings with lengths up to 10 bits and observed that the generalized SDP gives better exact quantum query complexities than the known methods. Finally, we test the method on some selected functions and demonstrate that they all exhibit quantum speedup.
ISSN: 1570-0755
Appears in Collections:Physics / Fizik
Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File Description SizeFormat 
Uyanık2019_Article.pdfMakale (Article)679.71 kBAdobe PDFThumbnail
Show full item record

CORE Recommender

Page view(s)

checked on Nov 27, 2023


checked on Nov 27, 2023

Google ScholarTM



Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.