Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMatrix product states and the quantum max-flow/min-cut conjectures
146
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problems approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3- or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).
The Potts model has many applications. It is equivalent to some min-cut and max-flow models. Primal-dual algorithms have been used to solve these problems. Due to the special structure of the models, convergence proof is still a difficult problem. In this work, we developed two novel, preconditioned, and over-relaxed alternating direction methods of multipliers (ADMM) with convergence guarantee for these models. Using the proposed preconditioners or block preconditioners, we get accelerations with the over-relaxation variants of preconditioned ADMM. The preconditioned and over-relaxed Douglas-Rachford splitting methods are also considered for the Potts model. Our framework can handle both the two-labeling or multi-labeling problems with appropriate block preconditioners based on Eckstein-Bertsekas and Fortin-Glowinski splitting techniques.
We demonstrate that the optimal states in lossy quantum interferometry may be efficiently simulated using low rank matrix product states. We argue that this should be expected in all realistic quantum metrological protocols with uncorrelated noise and is related to the elusive nature of the Heisenberg precision scaling in presence of decoherence.
In the ${-1,0,1}$-APSP problem the goal is to compute all-pairs shortest paths (APSP) on a directed graph whose edge weights are all from ${-1,0,1}$. In the (min,max)-product problem the input is two $ntimes n$ matrices $A$ and $B$, and the goal is to output the (min,max)-product of $A$ and $B$. This paper provides a new algorithm for the ${-1,0,1}$-APSP problem via a simple reduction to the target-(min,max)-product problem where the input is three $ntimes n$ matrices $A,B$, and $T$, and the goal is to output a Boolean $ntimes n$ matrix $C$ such that the $(i,j)$ entry of $C$ is 1 if and only if the $(i,j)$ entry of the (min,max)-product of $A$ and $B$ is exactly the $(i,j)$ entry of the target matrix $T$. If (min,max)-product can be solved in $T_{MM}(n) = Omega(n^2)$ time then it is straightforward to solve target-(min,max)-product in $O(T_{MM}(n))$ time. Thus, given the recent result of Bringmann, Kunnemann, and Wegrzycki [STOC 2019], the ${-1,0,1}$-APSP problem can be solved in the same time needed for solving approximate APSP on graphs with positive weights. Moreover, we design a simple algorithm for target-(min,max)-product when the inputs are restricted to the family of inputs generated by our reduction. Using fast rectangular matrix multiplication, the new algorithm is faster than the current best known algorithm for (min,max)-product.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
