Comparison of quantum oracles
A comparison of the query complexity analysis of quantum algorithms was presented. Two different ways of representing a permutation in terms of a black box quantum oracle were provided. A simple promise problem that minimal quantum oracles could solve faster that the classical oracles was discussed....
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2002
|
| _version_ | 1797053192069971968 |
|---|---|
| author | Kashefi, E Kent, A Vedral, V Banaszek, K |
| author_facet | Kashefi, E Kent, A Vedral, V Banaszek, K |
| author_sort | Kashefi, E |
| collection | OXFORD |
| description | A comparison of the query complexity analysis of quantum algorithms was presented. Two different ways of representing a permutation in terms of a black box quantum oracle were provided. A simple promise problem that minimal quantum oracles could solve faster that the classical oracles was discussed. Results showed that the possibility of efficiently solving nonautomorphic graph isomorphism (NAGI) could be excluded by simulating a simpler oracle using standard oracle for a one-to-one function. |
| first_indexed | 2024-03-06T18:40:33Z |
| format | Journal article |
| id | oxford-uuid:0cba8198-0df3-4f3e-897b-f8ad446b09a7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:40:33Z |
| publishDate | 2002 |
| record_format | dspace |
| spelling | oxford-uuid:0cba8198-0df3-4f3e-897b-f8ad446b09a72022-03-26T09:36:32ZComparison of quantum oraclesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0cba8198-0df3-4f3e-897b-f8ad446b09a7EnglishSymplectic Elements at Oxford2002Kashefi, EKent, AVedral, VBanaszek, KA comparison of the query complexity analysis of quantum algorithms was presented. Two different ways of representing a permutation in terms of a black box quantum oracle were provided. A simple promise problem that minimal quantum oracles could solve faster that the classical oracles was discussed. Results showed that the possibility of efficiently solving nonautomorphic graph isomorphism (NAGI) could be excluded by simulating a simpler oracle using standard oracle for a one-to-one function. |
| spellingShingle | Kashefi, E Kent, A Vedral, V Banaszek, K Comparison of quantum oracles |
| title | Comparison of quantum oracles |
| title_full | Comparison of quantum oracles |
| title_fullStr | Comparison of quantum oracles |
| title_full_unstemmed | Comparison of quantum oracles |
| title_short | Comparison of quantum oracles |
| title_sort | comparison of quantum oracles |
| work_keys_str_mv | AT kashefie comparisonofquantumoracles AT kenta comparisonofquantumoracles AT vedralv comparisonofquantumoracles AT banaszekk comparisonofquantumoracles |