Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSymmetry and Quantum Query-to-Communication Simulation
365
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Buhrman, Cleve and Wigderson (STOC98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) < 2 R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC20) exhibited a total function for which the log n overhead in the BCW simulation is required. We improve upon their result in several ways. We show that the log n overhead is not required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing05). This upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. To prove this, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. In view of our first result, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
rate research
Read More
Buhrman, Cleve and Wigderson (STOC98) observed that for every Boolean function $f : {-1, 1}^n to {-1, 1}$ and $bullet : {-1, 1}^2 to {-1, 1}$ the two-party bounded-error quantum communication complexity of $(f circ bullet)$ is $O(Q(f) log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. Note that the bounded-error randomized communication complexity of $(f circ bullet)$ is bounded by $O(R(f))$, where $R(f)$ denotes the bounded-error randomized query complexity of $f$. Thus, the BCW simulation has an extra $O(log n)$ factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. H{o}yer and de Wolf (STACS02) showed that for the Set-Disjointness function, this can be reduced to $c^{log^* n}$ for some constant $c$, and subsequently Aaronson and Ambainis (FOCS03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is $mathsf{NOR}_n circ wedge$) is $O(Q(mathsf{NOR}_n))$. Perhaps somewhat surprisingly, we show that when $ bullet = oplus$, then the extra $log n$ factor in the BCW simulation is unavoidable. In other words, we exhibit a total function $F : {-1, 1}^n to {-1, 1}$ such that $Q^{cc}(F circ oplus) = Theta(Q(F) log n)$. To the best of our knowledge, it was not even known prior to this work whether there existed a total function $F$ and 2-bit function $bullet$, such that $Q^{cc}(F circ bullet) = omega(Q(F))$.
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.
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems -- from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.
We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does indeed reduce the query complexity of decision problems. Under traditional complexity assumptions, we obtain an exponential speedup between the quantum and the classical query complexity of function classes. For decision problems and function classes we obtain the following results: o P_||^NP[2k] is included in EQP_||^NP[k] o P_||^NP[2^(k+1)-2] is included in EQP^NP[k] o FP_||^NP[2^(k+1)-2] is included in FEQP^NP[2k] o FP_||^NP is included in FEQP^NP[O(log n)] For sets A that are many-one complete for PSPACE or EXP we show that FP^A is included in FEQP^A[1]. Sets A that are many-one complete for PP have the property that FP_||^A is included in FEQP^A[1]. In general we prove that for any set A there is a set X such that FP^A is included in FEQP^X[1], establishing that no set is superterse in the quantum setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
