Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight adversary bounds for composite functions
124
0
0.0
(
0
)
Authors
Peter Hoyer
Ask ChatGPT about the research
No Arabic abstract
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many equivalent formulations, and has natural connections to classical lower bounds. A further nice property of the adversary method is that it behaves very well with respect to composition of functions. We generalize the adversary method to include costs--each bit of the input can be given an arbitrary positive cost representing the difficulty of querying that bit. We use this generalization to exactly capture the adversary bound of a composite function in terms of the adversary bounds of its component functions. Our results generalize and unify previously known composition properties of adversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of Barnum and Saks on the quantum query complexity of read-once functions.
rate research
Read More
The goal of the ordered search problem is to find a particular item in an ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi proved a quantum lower bound for this problem of (1/pi) ln n + Theta(1). Here, we find the exact value of the best possible quantum adversary lower bound for a symmetrized version of ordered search (whose query complexity differs from that of the original problem by at most 1). Thus we show that the best lower bound for ordered search that can be proved by the adversary method is (1/pi) ln n + O(1). Furthermore, we show that this remains true for the generalized adversary method allowing negative weights.
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound lifts to a lower bound on randomized communication complexity with a constant-sized gadget. We also show that the classical adversary bound is a strictly stronger lower bound technique than the previously-lifted measure known as critical block sensitivity, making our lifting theorem one of the strongest lifting theorems for randomized communication complexity using a constant-sized gadget. 2. Turning to quantum models, we show a connection between lifting theorems for quantum adversary bounds and secure 2-party quantum computation in a certain honest-but-curious model. Under the assumption that such secure 2-party computation is impossible, we show that a simplified version of the positive-weight adversary bound lifts to a quantum communication lower bound using a constant-sized gadget. We also give an unconditional lifting theorem which lower bounds bounded-round quantum communication protocols. 3. Finally, we give some new results in query complexity. We show that the classical adversary and the positive-weight quantum adversary are quadratically related. We also show that the positive-weight quantum adversary is never larger than the square of the approximate degree. Both relations hold even for partial functions.
Changs lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each positive threshold $t$, Changs lemma provides a lower bound on $wt(f):=Pr[f(x)=-1]$ in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least $1/t$. We examine the tightness of Changs lemma w.r.t. the following three natural settings of the threshold: - the Fourier sparsity of $f$, denoted $k(f)$, - the Fourier max-supp-entropy of $f$, denoted $k(f)$, defined to be $max {1/|hat{f}(S)| : hat{f}(S) eq 0}$, - the Fourier max-rank-entropy of $f$, denoted $k(f)$, defined to be the minimum $t$ such that characters whose Fourier coefficients are at least $1/t$ in absolute value span a space of dimension $r(f)$. We prove new lower bounds on $wt(f)$ in terms of these measures. One of our lower bounds subsumes and refines the previously best known upper bound on $r(f)$ in terms of $k(f)$ by Sanyal (ToC, 2019). Another lower bound is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of the absolute values of the level-$1$ Fourier coefficients. We also show that Changs lemma for the these choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions (which are modifications of the Addressing function) witnessing their tightness. Finally we construct Boolean functions $f$ for which - our lower bounds asymptotically match $wt(f)$, and - for any choice of the threshold $t$, the lower bound obtained from Changs lemma is asymptotically smaller than $wt(f)$.
The entanglement content of superpositions of quantum states is investigated based on a measure called {it concurrence}. Given a bipartite pure state in arbitrary dimension written as the quantum superposition of two other such states, we find simple inequalities relating the concurrence of the state to that of its components. We derive an exact expression for the concurrence when the component states are biorthogonal, and provide elegant upper and lower bounds in all other cases. For quantum bits, our upper bound is tighter than the previously derived bound in [Phys. Rev. Lett. 97, 100502 (2006).]
The estimation of multiple parameters in quantum metrology is important for a vast array of applications in quantum information processing. However, the unattainability of fundamental precision bounds for incompatible observables has greatly diminished the applicability of estimation theory in many practical implementations. The Holevo Cramer-Rao bound (HCRB) provides the most fundamental, simultaneously attainable bound for multi-parameter estimation problems. A general closed form for the HCRB is not known given that it requires a complex optimisation over multiple variables. In this work, we develop an analytic approach to solving the HCRB for two parameters. Our analysis reveals the role of the HCRB and its interplay with alternative bounds in estimation theory. For more parameters, we generate a lower bound to the HCRB. Our work greatly reduces the complexity of determining the HCRB to solving a set of linear equations that even numerically permits a quadratic speedup over previous state-of-the-art approaches. We apply our results to compare the performance of different probe states in magnetic field sensing, and characterise the performance of state tomography on the codespace of noisy bosonic error-correcting codes. The sensitivity of state tomography on noisy binomial codestates can be improved by tuning two coding parameters that relate to the number of correctable phase and amplitude damping errors. Our work provides fundamental insights and makes significant progress towards the estimation of multiple incompatible observables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
