Show simple item record

dc.contributor.authorUyanık, Kıvanç
dc.date.accessioned2020-07-25T22:03:13Z
dc.date.available2020-07-25T22:03:13Z
dc.date.issued2019-06
dc.identifier.issn1570-0755
dc.identifier.issn1573-1332
dc.identifier.urihttps://doi.org/10.1007/s11128-019-2297-3
dc.identifier.urihttps://hdl.handle.net/11147/9033
dc.description.abstractOne 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.en_US
dc.language.isoengen_US
dc.publisherSpringeren_US
dc.relation.isversionof10.1007/s11128-019-2297-3en_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectQuantum algorithmsen_US
dc.subjectSemidefinite programmingen_US
dc.subjectExact query complexityen_US
dc.titleEvaluation of exact quantum query complexities by semidefinite programmingen_US
dc.typearticleen_US
dc.relation.journalQuantum Information Processingen_US
dc.contributor.departmentIzmir Institute of Technology. Physicsen_US
dc.identifier.volume18en_US
dc.identifier.issue6en_US
dc.identifier.wosWOS:000466047100003
dc.identifier.scopusSCOPUS:2-s2.0-85064894175
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record