Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Algorithms for Evaluating MIN-MAX Trees
297
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this problem.
rate research
Read More
The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating an integral capacity to each edge and a tensor to each vertex in a flow network, we can also interpret it as a tensor network, and more specifically, as a linear map from the input space to the output space. The quantum max flow is defined to be the maximal rank of this linear map over all choices of tensors. The quantum min cut is defined to be the minimum product of the capacities of edges over all cuts of the tensor network. We show that unlike the classical case, the quantum max-flow=min-cut conjecture is not true in general. Under certain conditions, e.g., when the capacity on each edge is some power of a fixed integer, the quantum max-flow is proved to equal the quantum min-cut. However, concrete examples are also provided where the equality does not hold. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem. We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.
This paper presents an efficient parallel approximation scheme for a new class of min-max problems. The algorithm is derived from the matrix multiplicative weights update method and can be used to find near-optimal strategies for competitive two-party classical or quantum interactions in which a referee exchanges any number of messages with one party followed by any number of additional messages with the other. It considerably extends the class of interactions which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for an interaction in which one party reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a specific class of semidefinite programs whose feasible region consists of lists of semidefinite matrices that satisfy a transcript-like consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.
A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise $min_k sum_v c_{kv} x_v$ subject to $sum_v a_{iv} x_v le 1$ for each $i$ and $x_v ge 0$ for each $v$. Here $c_{kv} ge 0$, $a_{iv} ge 0$, and the support sets $V_i = {v : a_{iv} > 0 }$, $V_k = {v : c_{kv}>0 }$, $I_v = {i : a_{iv} > 0 }$ and $K_v = {k : c_{kv} > 0 }$ have bounded size. In the distributed setting, each agent $v$ is responsible for choosing the value of $x_v$, and the communication network is a hypergraph $mathcal{H}$ where the sets $V_k$ and $V_i$ constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if $|V_i|$ and $|V_k|$ are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in $mathcal{H}$.
In this note we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut. In the first we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions. In the second we generalize this result to a 2d-cycle. In the third we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely a gap of at least 2^{d-2} between the quantum max-flow and the quantum min-cut.
We show that the conditional min-entropy Hmin(A|B) of a bipartite state rho_AB is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the B-part of rho_AB are allowed. In the special case where A is classical, this overlap corresponds to the probability of guessing A given B. In a similar vein, we connect the conditional max-entropy Hmax(A|B) to the maximum fidelity of rho_AB with a product state that is completely mixed on A. In the case where A is classical, this corresponds to the security of A when used as a secret key in the presence of an adversary holding B. Because min- and max-entropies are known to characterize information-processing tasks such as randomness extraction and state merging, our results establish a direct connection between these tasks and basic operational problems. For example, they imply that the (logarithm of the) probability of guessing A given B is a lower bound on the number of uniform secret bits that can be extracted from A relative to an adversary holding B.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
