We introduce a quantum divide and conquer algorithm that enables the use of distributed computing for constrained combinatorial optimization problems. The algorithm consists of three major components: classical partitioning of a target graph into mul
tiple subgraphs, variational optimization over these subgraphs, and a quantum circuit cutting procedure that allows the optimization to take place independently on separate quantum processors. We simulate the execution of the quantum divide and conquer algorithm to find approximate solutions to instances of the Maximum Independent Set problem which have nearly twice as many nodes than the number of qubits available on a single quantum processor.
We consider the task of performing quantum state tomography on a $d$-state spin qudit, using only measurements of spin projection onto different quantization axes. By an exact mapping onto the classical problem of signal recovery on the sphere, we pr
ove that full reconstruction of arbitrary qudit states requires a minimal number of measurement axes, $r_d^{mathrm{min}}$, that is bounded by $2d-1le r_d^{mathrm{min}}le d^2$. We conjecture that $r_d^{mathrm{min}}=2d-1$, which we verify numerically for all $dle200$. We then provide algorithms with $O(rd^3)$ serial runtime, parallelizable down to $O(rd^2)$, for (i) computing a priori upper bounds on the expected error with which spin projection measurements along $r$ given axes can reconstruct an unknown qudit state, and (ii) estimating a posteriori the statistical error in a reconstructed state. Our algorithms motivate a simple randomized tomography protocol, for which we find that using more measurement axes can yield substantial benefits that plateau after $rapprox3d$.
We investigate many-body spin squeezing dynamics in an XXZ model with interactions that fall off with distance $r$ as $1/r^alpha$ in $D=2$ and $3$ spatial dimensions. In stark contrast to the Ising model, we find a broad parameter regime where spin s
queezing comparable to the infinite-range $alpha=0$ limit is achievable even when interactions are short-ranged, $alpha>D$. A region of collective behavior in which optimal squeezing grows with system size extends all the way to the $alphatoinfty$ limit of nearest-neighbor interactions. Our predictions, made using the discrete truncated Wigner approximation (DTWA), are testable in a variety of experimental cold atomic, molecular, and optical platforms.
We introduce maximum likelihood fragment tomography (MLFT) as an improved circuit cutting technique for running clustered quantum circuits on quantum devices with a limited number of qubits. In addition to minimizing the classical computing overhead
of circuit cutting methods, MLFT finds the most likely probability distribution for the output of a quantum circuit, given the measurement data obtained from the circuits fragments. We demonstrate the benefits of MLFT for accurately estimating the output of a fragmented quantum circuit with numerical experiments on random unitary circuits. Finally, we show that circuit cutting can estimate the output of a clustered circuit with higher fidelity than full circuit execution, thereby motivating the use of circuit cutting as a standard tool for running clustered circuits on quantum hardware.
We study a driven, spin-orbit coupled fermionic system in a lattice at the resonant regime where the drive frequency equals the Hubbard repulsion, for which non-trivial constrained dynamics emerge at fast timescales. An effective density-dependent tu
nneling model is derived, and examined in the sparse filling regime in 1D. The system exhibits entropic self-localization, where while even numbers of atoms propagate ballistically, odd numbers form localized bound states induced by an effective attraction from a higher configurational entropy. These phenomena occur in the strong coupling limit where interactions only impose a constraint with no explicit Hamiltonian term. We show how the constrained dynamics lead to quantum few-body scars and map to an Anderson impurity model with an additional intriguing feature of non-reciprocal scattering. Connections to many-body scars and localization are also discussed.
