Log in

Relevant bibliographies by topics / Quantum query complexity / Journal articles

To see the other types of publications on this topic, follow the link: Quantum query complexity.

Journal articles on the topic 'Quantum query complexity'

Author: Grafiati

Published: 4 June 2021

Last updated: 5 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Quantum query complexity.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Sardharwalla, Imdad S. B., Sergii Strelchuk, and Richard Jozsa. "Quantum conditional query complexity." Quantum Information and Computation 17, no. 7&8 (2017): 541–67. http://dx.doi.org/10.26421/qic17.7-8-1.

Full text

Abstract:

We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an n-input m-output boolean function is balanced or e-far from balanced; and (c) give an algorithm, requiring O˜(n/e) queries, for testing whether an n-dimensional quantum state is maximally mixed or not.

APA, Harvard, Vancouver, ISO, and other styles

2

Montanaro, Ashley. "Nonadaptive quantum query complexity." Information Processing Letters 110, no. 24 (2010): 1110–13. http://dx.doi.org/10.1016/j.ipl.2010.09.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Montanaro, Ashley, Harumichi Nishimura, and Rudy Raymond. "Unbounded-error quantum query complexity." Theoretical Computer Science 412, no. 35 (2011): 4619–28. http://dx.doi.org/10.1016/j.tcs.2011.04.043.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Ambainis, Andris, and Ronald de Wolf. "Average-case quantum query complexity." Journal of Physics A: Mathematical and General 34, no. 35 (2001): 6741–54. http://dx.doi.org/10.1088/0305-4470/34/35/302.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Montanaro, Ashley, Richard Jozsa, and Graeme Mitchison. "On Exact Quantum Query Complexity." Algorithmica 71, no. 4 (2013): 775–96. http://dx.doi.org/10.1007/s00453-013-9826-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ambainis, A., A. M. Childs, F. Le Gall, and S. Tani. "The quantum query complexity of certification." Quantum Information and Computation 10, no. 3&4 (2010): 181–89. http://dx.doi.org/10.26421/qic10.3-4-1.

Full text

Abstract:

We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

APA, Harvard, Vancouver, ISO, and other styles

7

Beame, Paul, and Widad Machmouchi. "The quantum query complexity of AC0." Quantum Information and Computation 12, no. 7&8 (2012): 670–76. http://dx.doi.org/10.26421/qic12.7-8-11.

Full text

Abstract:

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\Omega(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $\Omega ((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $\Omega(n^{2/3})$ lower bound for the element distinctness problem.

APA, Harvard, Vancouver, ISO, and other styles

8

Li, Tongyang, and Xiaodi Wu. "Quantum Query Complexity of Entropy Estimation." IEEE Transactions on Information Theory 65, no. 5 (2019): 2899–921. http://dx.doi.org/10.1109/tit.2018.2883306.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Ambainis, Andris. "Polynomial degree vs. quantum query complexity." Journal of Computer and System Sciences 72, no. 2 (2006): 220–38. http://dx.doi.org/10.1016/j.jcss.2005.06.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Copeland, Daniel, and Jamie Pommersheim. "Quantum query complexity of symmetric oracle problems." Quantum 5 (March 7, 2021): 403. http://dx.doi.org/10.22331/q-2021-03-07-403.

Full text

Abstract:

We study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t-query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn. More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G, we want to learn which coset of H the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a t-query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on n which require n+1 queries classically and only 1 query quantumly.

APA, Harvard, Vancouver, ISO, and other styles

11

KAWACHI, Akinori, Kenichi KAWANO, François LE GALL, and Suguru TAMAKI. "Quantum Query Complexity of Unitary Operator Discrimination." IEICE Transactions on Information and Systems E102.D, no. 3 (2019): 483–91. http://dx.doi.org/10.1587/transinf.2018fcp0012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Dürr, Christoph, Mark Heiligman, Peter HOyer, and Mehdi Mhalla. "Quantum Query Complexity of Some Graph Problems." SIAM Journal on Computing 35, no. 6 (2006): 1310–28. http://dx.doi.org/10.1137/050644719.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Heinrich, Stefan. "The quantum query complexity of elliptic PDE." Journal of Complexity 22, no. 5 (2006): 691–725. http://dx.doi.org/10.1016/j.jco.2006.04.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

de, Beaudrap, Not Available Not Available, and Not Available Not Available. "Sharp Quantum versus Classical Query Complexity Separations." Algorithmica 34, no. 4 (2002): 449–61. http://dx.doi.org/10.1007/s00453-002-0978-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Dörn, Sebastian, and Thomas Thierauf. "The quantum query complexity of the determinant." Information Processing Letters 109, no. 6 (2009): 325–28. http://dx.doi.org/10.1016/j.ipl.2008.11.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Xu, Guoliang, and Daowen Qiu. "Partial Boolean Functions With Exact Quantum Query Complexity One." Entropy 23, no. 2 (2021): 189. http://dx.doi.org/10.3390/e23020189.

Full text

Abstract:

We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.

APA, Harvard, Vancouver, ISO, and other styles

17

ZHU, YECHAO. "QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT." International Journal of Quantum Information 10, no. 03 (2012): 1250019. http://dx.doi.org/10.1142/s0219749912500190.

Full text

Abstract:

We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether a n-vertex graph contains a triangle, clique or star of some size. For a general subgraph H with k vertices, we show that H containment can be solved with quantum query complexity [Formula: see text], with g(H) a strictly positive function of H. This is better than Õ(n2-2/k) by Magniez et al. This result is obtained in the learning graph model of Belovs.

APA, Harvard, Vancouver, ISO, and other styles

18

Johansson, Niklas, and Jan-Åke Larsson. "Quantum Simulation Logic, Oracles, and the Quantum Advantage." Entropy 21, no. 8 (2019): 800. http://dx.doi.org/10.3390/e21080800.

Full text

Abstract:

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simon’s algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shor’s algorithm for integer factorization.

APA, Harvard, Vancouver, ISO, and other styles

19

Jeffery, Stacey, and Shelby Kimmel. "Quantum algorithms for graph connectivity and formula evaluation." Quantum 1 (August 17, 2017): 26. http://dx.doi.org/10.22331/q-2017-08-17-26.

Full text

Abstract:

We give a new upper bound on the quantum query complexity of decidingst-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm forst-connectivity to Boolean formula evaluation problems, we match theO(N)bound on the quantum query complexity of evaluating formulas onNvariables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that thisst-connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.

APA, Harvard, Vancouver, ISO, and other styles

20

Childs, Andrew M., and Robin Kothari. "Quantum Query Complexity of Minor-Closed Graph Properties." SIAM Journal on Computing 41, no. 6 (2012): 1426–50. http://dx.doi.org/10.1137/110833026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Montanaro, Ashley. "The quantum query complexity of learning multilinear polynomials." Information Processing Letters 112, no. 11 (2012): 438–42. http://dx.doi.org/10.1016/j.ipl.2012.03.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Childs, A. M., and J. M. Eisenberg. "Quantum algorithms for subset finding." Quantum Information and Computation 5, no. 7 (2005): 593–604. http://dx.doi.org/10.26421/qic5.7-7.

Full text

Abstract:

Recently, Ambainis gave an $O(N^{2/3})$-query discrete-time quantum walk algorithm for the element distinctness problem, and more generally, an $O(N^{L/(L+1)})$-query algorithm for finding $L$ equal numbers. We review this algorithm and give a simplified and tightened analysis of its query complexity using techniques previously applied to the analysis of continuous-time quantum walk. We also briefly discuss applications of the algorithm and pose two open problems regarding continuous-time quantum walk and lower bounds.

APA, Harvard, Vancouver, ISO, and other styles

23

Beigi, Salman, and Leila Taghavi. "Quantum Speedup Based on Classical Decision Trees." Quantum 4 (March 2, 2020): 241. http://dx.doi.org/10.22331/q-2020-03-02-241.

Full text

Abstract:

Lin and Lin \cite{LL16} have recently shown how starting with a classical query algorithm (decision tree) for a function, we may find upper bounds on its quantum query complexity. More precisely, they have shown that given a decision tree for a function f:{0,1}n→[m] whose input can be accessed via queries to its bits, and a guessing algorithm that predicts answers to the queries, there is a quantum query algorithm for f which makes at most O(GT) quantum queries where T is the depth of the decision tree and G is the maximum number of mistakes of the guessing algorithm. In this paper we give a simple proof of and generalize this result for functions f:[ℓ]n→[m] with non-binary input as well as output alphabets. Our main tool for this generalization is non-binary span program which has recently been developed for non-binary functions, and the dual adversary bound. As applications of our main result we present several quantum query upper bounds, some of which are new. In particular, we show that topological sorting of vertices of a directed graph G can be done with O(n3/2) quantum queries in the adjacency matrix model. Also, we show that the quantum query complexity of the maximum bipartite matching is upper bounded by O(n3/4m+n) in the adjacency list model.

APA, Harvard, Vancouver, ISO, and other styles

24

S, Manjula Gandhi, and R. Prabhakar. "Quantum Query Complexity to Determine Radius of a Graph." i-manager's Journal on Software Engineering 2, no. 4 (2008): 64–69. http://dx.doi.org/10.26634/jse.2.4.498.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Lee, Troy, and Jérémie Roland. "A strong direct product theorem for quantum query complexity." computational complexity 22, no. 2 (2013): 429–62. http://dx.doi.org/10.1007/s00037-013-0066-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Zhandry, Mark. "A note on the quantum collision and set equality problems." Quantum Information and Computation 15, no. 7&8 (2015): 557–67. http://dx.doi.org/10.26421/qic15.7-8-2.

Full text

Abstract:

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

APA, Harvard, Vancouver, ISO, and other styles

27

Montanaro, A. "Quantum search of partially ordered sets." Quantum Information and Computation 9, no. 7&8 (2009): 628–47. http://dx.doi.org/10.26421/qic9.7-8-6.

Full text

Abstract:

We investigate the generalisation of quantum search of unstructured and totally ordered sets to search of partially ordered sets (posets). Two models for poset search are considered. In both models, we show that quantum algorithms can achieve at most a quadratic improvement in query complexity over classical algorithms, up to logarithmic factors; we also give quantum algorithms that almost achieve this optimal reduction in complexity. In one model, we give an improved quantum algorithm for searching forest-like posets; in the other, we give an optimal $O(\sqrt{m})$-query quantum algorithm for searching posets derived from $m \times m$ arrays sorted by rows and columns. This leads to a quantum algorithm that finds the intersection of two sorted lists of $n$ integers in $O(\sqrt{n})$ time, which is optimal.

APA, Harvard, Vancouver, ISO, and other styles

28

Dinh, H., and A. Russell. "Quantum and randomized lower bounds for local search on vertex-transitive graphs." Quantum Information and Computation 10, no. 7&8 (2010): 638–52. http://dx.doi.org/10.26421/qic10.7-8-5.

Full text

Abstract:

We study the problem of \emph{local search} on a graph. Given a real-valued black-box function $f$ on the graph's vertices, this is the problem of determining a local minimum of $f$---a vertex $v$ for which $f(v)$ is no more than $f$ evaluated at any of $v$'s neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires $\Omega(2^{n/2 - o(n)} )$ queries to determine a local minima on the $n$-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to $\Omega(2^{n/2}/n^2)$ and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph $G$ of $N$ vertices and diameter $d$, the randomized and quantum query complexities for local search on $G$ are $\Omega\left({\sqrt{N}}/{d\log N}\right)$ and $\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)$, respectively.

APA, Harvard, Vancouver, ISO, and other styles

29

Sherstov, Alexander A. "Strong Direct Product Theorems for Quantum Communication and Query Complexity." SIAM Journal on Computing 41, no. 5 (2012): 1122–65. http://dx.doi.org/10.1137/110842661.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Koiran, Pascal, Vincent Nesme, and Natacha Portier. "The quantum query complexity of the abelian hidden subgroup problem." Theoretical Computer Science 380, no. 1-2 (2007): 115–26. http://dx.doi.org/10.1016/j.tcs.2007.02.057.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Magnin, Loïck, and Jérémie Roland. "Explicit relation between all lower bound techniques for quantum query complexity." International Journal of Quantum Information 13, no. 04 (2015): 1350059. http://dx.doi.org/10.1142/s0219749913500597.

Full text

Abstract:

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending the polynomial method from Boolean functions to quantum state generation problems. In the process, the bound is even strengthened. We then show that this extended polynomial method is a special case of the multiplicative adversary method with an adversary matrix that is independent of the function. This new result therefore provides insight on the reason why in some cases the adversary method is stronger than the polynomial method. It also reveals a clear picture of the relation between the different lower bound techniques, as it implies that all known techniques reduce to the multiplicative adversary method.

APA, Harvard, Vancouver, ISO, and other styles

32

Berry, Dominic, and Leonardo Novo. "Corrected quantum walk for optimal Hamiltonian simulation." Quantum Information and Computation 16, no. 15&16 (2016): 1295–317. http://dx.doi.org/10.26421/qic16.15-16-3.

Full text

Abstract:

We describe a method to simulate Hamiltonian evolution on a quantum computer by repeatedly using a superposition of steps of a quantum walk, then applying a correction to the weightings for the numbers of steps of the quantum walk. This correction enables us to obtain complexity which is the same as the lower bound up to doublelogarithmic factors for all parameter regimes. The scaling of the query complexity is given. This technique should also be useful for improving the scaling of the Taylor series approach to simulation, which is relevant to applications such as quantum chemistry.

APA, Harvard, Vancouver, ISO, and other styles

33

Fei, Shao-Ming. "What is the largest separation between quantum and classical query complexity?" Science Bulletin 62, no. 14 (2017): 980–81. http://dx.doi.org/10.1016/j.scib.2017.06.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Laplante, Sophie, and Frédéric Magniez. "Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments." SIAM Journal on Computing 38, no. 1 (2008): 46–62. http://dx.doi.org/10.1137/050639090.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Jeffery, Stacey, Robin Kothari, François Le Gall, and Frédéric Magniez. "Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision." Algorithmica 76, no. 1 (2015): 1–16. http://dx.doi.org/10.1007/s00453-015-9985-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Ettinger, Mark, Peter Høyer, and Emanuel Knill. "The quantum query complexity of the hidden subgroup problem is polynomial." Information Processing Letters 91, no. 1 (2004): 43–48. http://dx.doi.org/10.1016/j.ipl.2004.01.024.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Zhang, Chi. "An improved lower bound on query complexity for quantum PAC learning." Information Processing Letters 111, no. 1 (2010): 40–45. http://dx.doi.org/10.1016/j.ipl.2010.10.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Montanaro, Ashley. "The quantum complexity of approximating the frequency moments." Quantum Information and Computation 16, no. 13&14 (2016): 1169–90. http://dx.doi.org/10.26421/qic16.13-14-5.

Full text

Abstract:

The k’th frequency moment of a sequence of integers is defined as F_k = Sum_ j n^k _j , where n_j is the number of times that j occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate F_k up to relative error epsilon. We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate F_k. We describe quantum algorithms for F_0, F_2 and F_∞ in this model which substantially outperform the best possible classical algorithms in certain parameter regimes.

APA, Harvard, Vancouver, ISO, and other styles

39

Berry, Dominic W., Richard Cleve, and Sevag Gharibian. "Gate-efficient discrete simulations of continuous-time quantum query algorithms." Quantum Information and Computation 14, no. 1&2 (2014): 1–30. http://dx.doi.org/10.26421/qic14.1-2-1.

Full text

Abstract:

We show how to efficiently simulate continuous-time quantum query algorithms that run in time T in a manner that preserves the query complexity (within a polylogarithmic factor) while also incurring a small overhead cost in the total number of gates between queries. By small overhead, we mean T within a factor that is polylogarithmic in terms of T and a cost measure that reflects the cost of computing the driving Hamiltonian. This permits any continuous-time quantum algorithm based on an efficiently computable driving Hamiltonian to be converted into a gate-efficient algorithm with similar running time.

APA, Harvard, Vancouver, ISO, and other styles

40

IWAMA, KAZUO, and HARUMICHI NISHIMURA. "RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC." International Journal of Foundations of Computer Science 24, no. 07 (2013): 979–93. http://dx.doi.org/10.1142/s0129054113400261.

Full text

Abstract:

Recovering unknown inputs in oracles with as few queries as possible is one of the most basic problems in theoretical computer science. In this paper, we survey the classical and quantum query complexity of this problem for various types of oracles with different types of queries.

APA, Harvard, Vancouver, ISO, and other styles

41

MANCINI, STEFANO, and LORENZO MACCONE. "USING QUANTUM MECHANICS TO COPE WITH LIARS." International Journal of Quantum Information 03, no. 04 (2005): 729–33. http://dx.doi.org/10.1142/s0219749905001559.

Full text

Abstract:

We propose the use of a quantum algorithm to deal with the problem of searching with errors in the framework of two-person games. Specifically, we present a solution to the Ulam's problem that polynomially reduces its query complexity and makes it independent of the dimension of the search space.

APA, Harvard, Vancouver, ISO, and other styles

42

Bin, Shang. "Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database." Communications in Theoretical Physics 48, no. 2 (2007): 264–66. http://dx.doi.org/10.1088/0253-6102/48/2/013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Barnum, Howard, and Michael Saks. "A lower bound on the quantum query complexity of read-once functions." Journal of Computer and System Sciences 69, no. 2 (2004): 244–58. http://dx.doi.org/10.1016/j.jcss.2004.02.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Ambainis, Andris, Kazuo Iwama, Masaki Nakanishi, et al. "Quantum Query Complexity of Almost All Functions with Fixed On-set Size." computational complexity 25, no. 4 (2016): 723–35. http://dx.doi.org/10.1007/s00037-016-0139-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Zhang, Chenyi, Jiaqi Leng, and Tongyang Li. "Quantum algorithms for escaping from saddle points." Quantum 5 (August 20, 2021): 529. http://dx.doi.org/10.22331/q-2021-08-20-529.

Full text

Abstract:

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function f:Rn→R, our quantum algorithm outputs an ϵ-approximate second-order stationary point using O~(log2⁡(n)/ϵ1.75) queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al. with O~(log6⁡(n)/ϵ1.75) queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of log⁡n and matches its complexity in terms of 1/ϵ. Technically, our main contribution is the idea of replacing the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the improvement in the quantum query complexity with log⁡n factors for escaping from saddle points. We also show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries by quantum evaluation queries with the same complexity. Finally, we also perform numerical experiments that support our theoretical findings.

APA, Harvard, Vancouver, ISO, and other styles

46

Gocwin, Maciej. "On the quantum complexity of computing the median of continuous distributions." Quantum Information and Computation 19, no. 11&12 (2019): 952–66. http://dx.doi.org/10.26421/qic19.11-12-4.

Full text

Abstract:

We study the approximation of the median of an absolutely continuous distribution with respect to the Lebesgue measure given by a probability density function f. We assume that f has r continuous derivatives, with derivative of order r being H\"older continuous with the exponent \rho. We study the quantum query complexity of this problem. We show that the \ve-complexity up to a logarithmic factor is of order \ve^{-1/(r+\rho+1)}. We also extend the results to the problem of computing the vector of quantiles of an absolutely continuous distribution.

APA, Harvard, Vancouver, ISO, and other styles

47

Stadelhofer, Ralf, Wolfgang Banzhaf, and Dieter Suter. "Evolving blackbox quantum algorithms using genetic programming." Artificial Intelligence for Engineering Design, Analysis and Manufacturing 22, no. 3 (2008): 285–97. http://dx.doi.org/10.1017/s089006040800019x.

Full text

Abstract:

AbstractAlthough it is known that quantum computers can solve certain computational problems exponentially faster than classical computers, only a small number of quantum algorithms have been developed so far. Designing such algorithms is complicated by the rather nonintuitive character of quantum physics. In this paper we present a genetic programming system that uses some new techniques to develop and improve quantum algorithms. We have used this system to develop two formerly unknown quantum algorithms. We also address a potential deficiency of the quantum decision tree model used to prove lower bounds on the query complexity of the parity problem.

APA, Harvard, Vancouver, ISO, and other styles

48

Brandao, Fernando G. S. L., and Michal Horodecki. "Exponential quantum speed-ups are generic." Quantum Information and Computation 13, no. 11&12 (2013): 901–24. http://dx.doi.org/10.26421/qic13.11-12-1.

Full text

Abstract:

A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation. We address this question in the setting of query complexity and show that for almost any sufficiently long quantum circuit one can construct a black-box problem which is solved by the circuit with a constant number of quantum queries, but which requires exponentially many classical queries, even if the classical machine has the ability to postselect. We prove the result in two steps. In the first, we show that almost any element of an approximate unitary 3-design is useful to solve a certain black-box problem efficiently. The problem is based on a recent oracle construction of Aaronson and gives an exponential separation between quantum and classical post-selected bounded-error query complexities. In the second step, which may be of independent interest, we prove that linear-sized random quantum circuits give an approximate unitary 3-design. The key ingredient in the proof is a technique from quantum many-body theory to lower bound the spectral gap of local quantum Hamiltonians.

APA, Harvard, Vancouver, ISO, and other styles

49

Sun, Xiaoming, and Andrew Chi-Chih Yao. "On the Quantum Query Complexity of Local Search in Two and Three Dimensions." Algorithmica 55, no. 3 (2008): 576–600. http://dx.doi.org/10.1007/s00453-008-9170-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Mahadev, Urmila, and Ronald de Wolf. "Rational approximations and quantum algorithms with postselection." Quantum Information and Computation 15, no. 3&4 (2015): 295–307. http://dx.doi.org/10.26421/qic15.3-4-5.

Full text

Abstract:

We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newman's classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!