arXiv daily

Quantum Physics (quant-ph)

Thu, 22 Jun 2023

Other arXiv digests in this category:Thu, 14 Sep 2023; Wed, 13 Sep 2023; Tue, 12 Sep 2023; Mon, 11 Sep 2023; Fri, 08 Sep 2023; Tue, 05 Sep 2023; Fri, 01 Sep 2023; Thu, 31 Aug 2023; Wed, 30 Aug 2023; Tue, 29 Aug 2023; Mon, 28 Aug 2023; Fri, 25 Aug 2023; Thu, 24 Aug 2023; Wed, 23 Aug 2023; Tue, 22 Aug 2023; Mon, 21 Aug 2023; Fri, 18 Aug 2023; Thu, 17 Aug 2023; Wed, 16 Aug 2023; Tue, 15 Aug 2023; Mon, 14 Aug 2023; Fri, 11 Aug 2023; Thu, 10 Aug 2023; Wed, 09 Aug 2023; Tue, 08 Aug 2023; Mon, 07 Aug 2023; Fri, 04 Aug 2023; Thu, 03 Aug 2023; Wed, 02 Aug 2023; Tue, 01 Aug 2023; Mon, 31 Jul 2023; Fri, 28 Jul 2023; Thu, 27 Jul 2023; Wed, 26 Jul 2023; Tue, 25 Jul 2023; Mon, 24 Jul 2023; Fri, 21 Jul 2023; Thu, 20 Jul 2023; Wed, 19 Jul 2023; Tue, 18 Jul 2023; Mon, 17 Jul 2023; Fri, 14 Jul 2023; Thu, 13 Jul 2023; Wed, 12 Jul 2023; Tue, 11 Jul 2023; Mon, 10 Jul 2023; Fri, 07 Jul 2023; Thu, 06 Jul 2023; Wed, 05 Jul 2023; Tue, 04 Jul 2023; Mon, 03 Jul 2023; Fri, 30 Jun 2023; Thu, 29 Jun 2023; Wed, 28 Jun 2023; Tue, 27 Jun 2023; Mon, 26 Jun 2023; Fri, 23 Jun 2023; Wed, 21 Jun 2023; Tue, 20 Jun 2023; Fri, 16 Jun 2023; Thu, 15 Jun 2023; Tue, 13 Jun 2023; Mon, 12 Jun 2023; Fri, 09 Jun 2023; Thu, 08 Jun 2023; Wed, 07 Jun 2023; Tue, 06 Jun 2023; Mon, 05 Jun 2023; Fri, 02 Jun 2023; Thu, 01 Jun 2023; Wed, 31 May 2023; Tue, 30 May 2023; Mon, 29 May 2023; Fri, 26 May 2023; Thu, 25 May 2023; Wed, 24 May 2023; Tue, 23 May 2023; Mon, 22 May 2023; Fri, 19 May 2023; Thu, 18 May 2023; Wed, 17 May 2023; Tue, 16 May 2023; Mon, 15 May 2023; Fri, 12 May 2023; Thu, 11 May 2023; Wed, 10 May 2023; Tue, 09 May 2023; Mon, 08 May 2023; Fri, 05 May 2023; Thu, 04 May 2023; Wed, 03 May 2023; Tue, 02 May 2023; Mon, 01 May 2023; Fri, 28 Apr 2023; Thu, 27 Apr 2023; Wed, 26 Apr 2023; Tue, 25 Apr 2023; Mon, 24 Apr 2023; Fri, 21 Apr 2023; Thu, 20 Apr 2023; Wed, 19 Apr 2023; Tue, 18 Apr 2023; Mon, 17 Apr 2023; Fri, 14 Apr 2023; Thu, 13 Apr 2023; Wed, 12 Apr 2023; Tue, 11 Apr 2023; Mon, 10 Apr 2023
1.Towards quantum enhanced adversarial robustness in machine learning

Authors:Maxwell T. West, Shu-Lok Tsang, Jia S. Low, Charles D. Hill, Christopher Leckie, Lloyd C. L. Hollenberg, Sarah M. Erfani, Muhammad Usman

Abstract: Machine learning algorithms are powerful tools for data driven tasks such as image classification and feature detection, however their vulnerability to adversarial examples - input samples manipulated to fool the algorithm - remains a serious challenge. The integration of machine learning with quantum computing has the potential to yield tools offering not only better accuracy and computational efficiency, but also superior robustness against adversarial attacks. Indeed, recent work has employed quantum mechanical phenomena to defend against adversarial attacks, spurring the rapid development of the field of quantum adversarial machine learning (QAML) and potentially yielding a new source of quantum advantage. Despite promising early results, there remain challenges towards building robust real-world QAML tools. In this review we discuss recent progress in QAML and identify key challenges. We also suggest future research directions which could determine the route to practicality for QAML approaches as quantum computing hardware scales up and noise levels are reduced.

2.Certifying the quantum Fisher information from a given set of mean values: a semidefinite programming approach

Authors:Guillem Müller-Rigat, Anubhav Kumar Srivastava, Stanisław Kurdziałek, Grzegorz Rajchel-Mieldzioć, Maciej Lewenstein, Irénée Frérot

Abstract: We introduce a semidefinite programming algorithm to find the minimal quantum Fisher information compatible with an arbitrary dataset of mean values. This certification task allows one to quantify the resource content of a quantum system for metrology applications without complete knowledge of the quantum state. We implement the algorithm to study quantum spin ensembles. We first focus on Dicke states, where our findings challenge and complement previous results in the literature. We then investigate states generated during the one-axis twisting dynamics, where in particular we find that the metrological power of the so-called multi-headed cat states can be certified using simple collective spin observables, such as fourth-order moments for small systems, and parity measurements for arbitrary system sizes.

3.Noninvertibility and non-Markovianity of quantum dynamical maps

Authors:Vinayak Jagadish, R. Srikanth, Francesco Petruccione

Abstract: We identify two broad types of noninvertibilities in quantum dynamical maps, one necessarily associated with CP-indivisibility and one not so. Next, we study the production of (non-)Markovian, invertible maps by the process of mixing noninvertible Pauli maps. The memory kernel perspective appears to be less transparent on the issue of invertibility than the approaches based on maps or master equations. Here we consider a related and potentially helpful issue: that of identifying criteria of parameterized families of maps leading to the existence of a well-defined semigroup limit.

4.Temporal witnesses of non-classicality in a macroscopic biological system

Authors:Giuseppe Di Pietra, Vlatko Vedral, Chiara Marletto

Abstract: Exciton transfer along a polymer is essential for many biological processes, for instance light harvesting in photosynthetic biosystems. Here we apply a new witness of non-classicality to this phenomenon, to conclude that, if an exciton can mediate the coherent quantum evolution of a photon, then the exciton is non-classical. We then propose a general qubit model for the quantum transfer of an exciton along a polymer chain, also discussing the effects of environmental decoherence. The generality of our results makes them ideal candidates to design new tests of quantum features in complex bio-molecules.

5.Violation of Bell inequality by photon scattering on a two-level emitter

Authors:Shikai Liu, Oliver August Dall'Alba Sandberg, Ming Lai Chan, Björn Schrinski, Yiouli Anyfantaki, Rasmus Bruhn Nielsen, Robert Garbecht Larsen, Andrei Skalkin, Ying Wang, Leonardo Midolo, Sven Scholz, Andreas Dirk Wieck, Arne Ludwig, Anders Søndberg Sørensen, Alexey Tiranov, Peter Lodahl

Abstract: Entanglement, the non-local correlations present in multipartite quantum systems, is a curious feature of quantum mechanics and the fuel of quantum technology. It is therefore a major priority to develop energy-conserving and simple methods for generating high-fidelity entangled states. In the case of light, entanglement can be realized by interactions with matter, although the required nonlinear interaction is typically weak, thereby limiting its applicability. Here, we show how a single two-level emitter deterministically coupled to light in a nanophotonic waveguide is used to realize genuine photonic quantum entanglement for excitation at the single photon level. By virtue of the efficient optical coupling, two-photon interactions are strongly mediated by the emitter realizing a giant nonlinearity that leads to entanglement. We experimentally generate and verify energy-time entanglement by violating a Bell inequality (Clauder-Horne-Shimony-Holt Bell parameter of $S=2.67(16)>2$) in an interferometric measurement of the two-photon scattering response. As an attractive feature of this approach, the two-level emitter acts as a passive scatterer initially prepared in the ground state, i.e., no advanced spin control is required. This experiment is a fundamental advancement that may pave a new route for ultra-low energy-consuming synthesis of photonic entangled states for quantum simulators or metrology.

6.A zigzag optical cavity for sensing and controlling torsional motion

Authors:Sofia Agafonova, Umang Mishra, Fritz Diorico, Onur Hosten

Abstract: Precision sensing and manipulation of milligram-scale mechanical oscillators has attracted growing interest in the fields of table-top explorations of gravity and tests of quantum mechanics at macroscopic scales. Torsional oscillators present an opportunity in this regard due to their remarked isolation from environmental noise. For torsional motion, an effective employment of optical cavities to enhance optomechanical interactions -- as already established for linear oscillators -- so far faced certain challenges. Here, we propose a novel concept for sensing and manipulating torsional motion, where exclusively the torsional rotations of a pendulum are mapped onto the path length of a single two-mirror optical cavity. The concept inherently alleviates many limitations of previous approaches. A proof-of-principle experiment is conducted with a rigidly controlled pendulum to explore the sensing aspects of the concept and to identify practical limitations in a potential state-of-the art setup. Based on this work, we anticipate development of precision torque sensors with sensitivities below $10^{-19}~\mathrm{N\cdot m/\sqrt{Hz}}$ and with the motion of the pendulums dominated by quantum radiation pressure noise at sub-microwatts of incoming laser power. This work, therefore, paves the way to new horizons for experiments at the interface of quantum mechanics and gravity.

7.Efficient detection for quantum states containing fewer than $k$ unentangled particles in multipartite quantum systems

Authors:Yabin Xing, Yan Hong, Limin Gao, Ting Gao, Fengli Yan

Abstract: In this paper, we mainly investigate the detection of quantum states containing fewer than $k$ unentangled particles in multipartite quantum systems. Based on calculations about operators, we derive two practical criteria for judging $N$-partite quantum states owning fewer than $k$ unentangled particles. In addition, we demonstrate the effectiveness of our frameworks through some concrete examples, and specifically point out the quantum states having fewer than $k$ unentangled particles that our methods can detect, while other criteria cannot recognize.

8.Optimization tools for distance-preserving flag fault-tolerant error correction

Authors:Balint Pato, Theerapat Tansuwannont, Shilin Huang, Kenneth R. Brown

Abstract: Lookup table decoding is fast and distance preserving, making it attractive for near-term quantum computer architectures with small-distance quantum error correcting codes. In this work, we develop several optimization tools which can potentially reduce the space and time overhead required for flag fault-tolerant error correction (FTEC) with lookup table decoding on Calderbank-Shor-Steane (CSS) codes. Our techniques include the compact lookup table construction, the Meet-in-the-Middle technique, the adaptive time decoding for flag FTEC, the classical processing technique for flag information, and the separated $X$ and $Z$ counting technique. We evaluate the performance of our tools using numerical simulation of hexagonal color codes of distances 3, 5, 7, and 9 under circuit-level noise. Combining all tools can result in more than an order of magnitude increase in pseudothreshold for the hexagonal color code of distance 9, from $(1.34 \pm 0.01) \times 10^{-4}$ to $(1.42 \pm 0.12) \times 10^{-3}$.

9.Solving the time-complexity problem and tuning the performance of quantum reservoir computing by artificial memory restriction

Authors:Saud Čindrak, Brecht Donvil, Kathy Lüdge, Lina Jaurigue

Abstract: Quantum reservoir computing is a computing approach which aims at utilising the complexity and high-dimensionality of small quantum systems, together with the fast trainability of reservoir computing, in order to solve complex tasks. The suitability of quantum reservoir computing for solving temporal tasks is hindered by the collapse of the quantum system when measurements are made. This leads to the erasure of the memory of the reservoir. Hence, for every output, the entire input signal is needed to reinitialise the reservoir, leading to quadratic time complexity. Overcoming this issue is critical to the hardware implementation of quantum reservoir computing. We propose artificially restricting the memory of the quantum reservoir by only using a small number inputs to reinitialise the reservoir after measurements are performed, leading to linear time complexity. This not only substantially reduces the number of quantum operations needed to perform timeseries prediction tasks, it also provides a means of tuning the nonlinearity of the response of the reservoir, which can lead to significant performance improvement. We numerically study the linear and quadratic algorithms for a fully connected transverse Ising model and a quantum processor model. We find that our proposed linear algorithm not only significantly reduces the computational cost but also provides an experimental accessible means to optimise the task specific reservoir computing performance.

10.Generating optical cat states via quantum interference of multi-path free-electron-photons interactions

Authors:Feng-Xiao Sun, Yiqi Fang, Qiongyi He, Yunquan Liu

Abstract: The novel quantum effects induced by the free-electron-photons interaction have attracted increasing interest due to their potential applications in ultrafast quantum information processing. Here, we propose a scheme to generate optical cat states based on the quantum interference of multi-path free-electron-photons interactions that take place simultaneously with strong coupling strength. By performing a projection measurement on the electron, the state of light changes significantly from a coherent state into a non-Gaussian state with either Wigner negativity or squeezing property, both possess metrological power to achieve quantum advantage. More importantly, we show that the Wigner negativity oscillates with the coupling strength, and the optical cat states are successfully generated with high fidelity at all the oscillation peaks. This oscillation reveals the quantum interference effect of the multiple quantum pathways in the interaction of the electron with photons, by that various nonclassical states of light are promising to be fast prepared and manipulated. These findings inspire further exploration of emergent quantum phenomena and advanced quantum technologies with free electrons.

11.Are Ideal Measurements of Real Scalar Fields Causal?

Authors:Emma Albertini, Ian Jubb

Abstract: Half a century ago a local and (seemingly) causally consistent implementation of the projection postulate was formulated for local projectors in Quantum Field Theory (QFT) by utilising the basic property that spacelike local observables commute. This was not the end of the story for whether projective, or ideal measurements in QFT respect causality. In particular, the causal consistency of ideal measurements was brought into question by Sorkin 20 years later using a scenario previously overlooked. Sorkin's example, however, involved a non-local operator, and thus the question remained whether ideal measurements of local operators are causally consistent, and hence whether they are physically realisable. Considering both continuum and discrete spacetimes such as causal sets, we focus on the basic local observables of real scalar field theory -- smeared field operators -- and show that the corresponding ideal measurements violate causality, and are thus impossible to realise in practice. We show this using a causality condition derived for a general class of update maps for smeared fields that includes unitary kicks, ideal measurements, and approximations to them such as weak measurements. We discuss the various assumptions that go into our result. Of note is an assumption that Sorkin's scenario can actually be constructed in the given spacetime setup. This assumption can be evaded in certain special cases in the continuum, and in a particularly natural way in Causal Set Theory. In such cases one can then freely use the projection postulate in a causally consistent manner. In light of the generic acausality of ideal measurements, we also present examples of local update maps that offer causality-respecting alternatives to the projection postulate as an operationalist description of measurement in QFT.

12.Measurement-induced quantum synchronization and multiplexing

Authors:Finn Schmolke, Eric Lutz

Abstract: Measurements are able to fundamentally affect quantum dynamics. We here show that a continuously measured quantum many-body system can undergo a spontaneous transition from asynchronous stochastic dynamics to noise-free stable synchronization at the level of single trajectories. We formulate general criteria for this quantum phenomenon to occur, and demonstrate that the number of synchronized realizations can be controlled from none to all. We additionally find that ergodicity is typically broken, since time and ensemble averages may exhibit radically different synchronization behavior. We further introduce a quantum type of multiplexing that involves individual trajectories with distinct synchronization frequencies. Measurement-induced synchronization appears as a genuine nonclassical form of synchrony that exploits quantum superpositions.

13.Stabilization of symmetry-protected long-range entanglement in stochastic quantum circuits

Authors:Iosifina Angelidi, Marcin Szyniszewski, Arijeet Pal

Abstract: Long-range entangled states are vital for quantum information processing and quantum metrology. Preparing such entangled states by combining measurements with unitary gates has opened new possibilities for efficient protocols with finite-depth quantum circuits. The complexity of these algorithms is crucial for the resource requirements on a quantum device. The stability of the preparation protocols to perturbations decides the fate of their implementation in large-scale noisy quantum devices. In this work, we consider stochastic quantum circuits in one and two dimensions consisting of randomly applied unitary gates and local measurements. These quantum operations preserve a class of discrete local symmetries, which can be broken due to the stochasticity arising from timing and gate imperfections. In the absence of randomness, the protocol is known to generate a symmetry-protected long-range entangled state in a finite-depth circuit. In the general case, by studying the time evolution under this hybrid quantum circuit, we analyze the time to reach the target entangled state. We find two important time scales which we associate with the emergence of certain symmetry generators. The quantum trajectories embody the local symmetry with a time that scales logarithmically with system size, whereas global symmetries require exponentially long times to appear. We devise error-mitigation protocols that provide significant improvement on both time scales and investigate the stability of the algorithm to perturbations that naturally arise in experiments. We also generalize the protocol to realize the toric code and Xu-Moore states in two dimensions, and open avenues for future studies of anyonic excitations present in those systems. Our work paves the way for efficient error correction for quantum state preparation.

14.Generation of heralded optical `Schroedinger cat' states by photon-addition

Authors:Yi-Ru Chen, Hsien-Yi Hsieh, Jingyu Ning, Hsun-Chung Wu, Hua Li Chen, Zi-Hao Shi, Popo Yang, Ole Steuernagel, Chien-Ming Wu, Ray-Kuang Lee

Abstract: Optical "Schr\"odinger cat" states, the non-classical superposition of two quasi-classical coherent states, serve as a basis for gedanken experiments testing quantum physics on mesoscopic scales and are increasingly recognized as a resource for quantum information processing. Here, we report the first experimental realization of optical "Schr\"odinger cats" by adding a photon to a squeezed vacuum state, so far only photon-subtraction protocols have been realized. Photon-addition gives us the advantage of using heralded signal photons as experimental triggers, and we can generate "Schr\"odinger cats" at rates exceeding $8.5 \times 10^4$ counts per second; at least one order of magnitude higher than all previously reported realizations. Wigner distributions with pronounced negative parts are demonstrated at down to -8.89 dB squeezing, even when the initial squeezed vacuum input state has low purity. Benchmarking against such a degraded squeezed input state we report a maximum fidelity of more than 80% with a maximum cat amplitude of $|\alpha| \approx 1.66$. Our experiment uses photon-addition from pairs, one of those photons is used for monitoring, giving us enhanced control; moreover the pair production rates are high and should allow for repeated application of photon-addition via repeat-stages.

15.Modelling non-Markovian noise in driven superconducting qubits

Authors:Abhishek Agarwal, Lachlan P. Lindoy, Deep Lall, Francois Jamet, Ivan Rungger

Abstract: Non-Markovian noise can be a significant source of errors in superconducting qubits. We develop gate sequences utilising mirrored pseudoidentities that allow us to characterise and model the effects of non-Markovian noise on both idle and driven qubits. We compare three approaches to modelling the observed noise: (i) a Markovian noise model, (ii) a model including interactions with a two-level system (TLS), (iii) a model utilising the post Markovian master equation (PMME), which we show to be equivalent to the qubit-TLS model in certain regimes. When running our noise characterisation circuits on a superconducting qubit device we find that purely Markovian noise models cannot reproduce the experimental data. Our model based on a qubit-TLS interaction, on the other hand, is able to closely capture the observed experimental behaviour for both idle and driven qubits. We investigate the stability of the noise properties of the hardware over time, and find that the parameter governing the qubit-TLS interaction strength fluctuates significantly even over short time-scales of a few minutes. Finally, we evaluate the changes in the noise parameters when increasing the qubit drive pulse amplitude. We find that although the hardware noise parameters fluctuate significantly over different days, their drive pulse induced relative variation is rather well defined within computed uncertainties: both the phase error and the qubit-TLS interaction strength change significantly with the pulse strength, with the phase error changing quadratically with the amplitude of the applied pulse. Since our noise model can closely describe the behaviour of idle and driven qubits, it is ideally suited to be used in the development of quantum error mitigation and correction methods.

16.Practical limitations of quantum data propagation on noisy quantum processors

Authors:Gaurav Saxena, Ahmed Shalabi, Thi Ha Kyaw

Abstract: The variational quantum imaginary time evolution algorithm is efficient in finding the ground state of a quantum Hamiltonian. This algorithm involves solving a system of linear equations in a classical computer and the solution is then used to propagate a quantum wavefunction. Here, we show that owing to the noisy nature of current quantum processors, such a quantum algorithm or the family of quantum algorithms that require classical computation of inverting a matrix with high condition number will require single- and two-qubit gates with very low error probability. Failure to meet such condition will result in erroneous quantum data propagation even for a relatively small quantum circuit ansatz. Specifically, we find the upper bounds on how the quantum algorithmic error scales with the probability of errors in quantum hardware. Our work challenges the mainstream notion of hybrid quantum-classical quantum algorithms being able to perform under noisy environments while we show such algorithms in fact require very low error quantum gates to get reliable results.

17.Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems

Authors:Theshani Nuradha, Ziv Goldfeld, Mark M. Wilde

Abstract: We propose a versatile privacy framework for quantum systems, termed quantum pufferfish privacy (QPP). Inspired by classical pufferfish privacy, our formulation generalizes and addresses limitations of quantum differential privacy by offering flexibility in specifying private information, feasible measurements, and domain knowledge. We show that QPP can be equivalently formulated in terms of the Datta-Leditzky information spectrum divergence, thus providing the first operational interpretation thereof. We reformulate this divergence as a semi-definite program and derive several properties of it, which are then used to prove convexity, composability, and post-processing of QPP mechanisms. Parameters that guarantee QPP of the depolarization mechanism are also derived. We analyze the privacy-utility tradeoff of general QPP mechanisms and, again, study the depolarization mechanism as an explicit instance. The QPP framework is then applied to privacy auditing for identifying privacy violations via a hypothesis testing pipeline that leverages quantum algorithms. Connections to quantum fairness and other quantum divergences are also explored and several variants of QPP are examined.

18.Gain-loss induced non-Abelian Bloch braids

Authors:B. Midya

Abstract: Onsite gain-loss induced topological braiding principles of non-Hermitian energy bands is theoretically formulated in multiband lattice models with Hermitian hopping amplitudes. Braid phase transition occurs when the gain-loss parameter is tuned across exceptional point degeneracies. Laboratory realizable effective-Hamiltonians are proposed to realize braid groups $\mathbb{B}_2$ and $\mathbb{B}_3$ of two and three bands respectively. While $\mathbb{B}_2$ is trivially Abelian, the group $\mathbb{B}_3$ features non-Abelian braiding and energy permutation. Phase diagrams with respect to lattice parameters to realize braid group generators and their non-commutativity are shown. The proposed theory is conducive to synthesize exceptional materials for applications in topological quantum photonic computation and information processing.

19.Bell nonlocality in maximal-length quantum mechanics

Authors:Pasquale Bosso, Fabrizio Illuminati, Luciano Petruzziello, Fabian Wagner

Abstract: In this paper, we investigate the consequences of maximal length as well as minimal momentum scales on nonlocal correlations shared by two parties of a bipartite quantum system. To this aim, we rely on a general phenomenological scheme which is usually associated with the non-negligible spacetime curvature at cosmological scales, namely the extended uncertainty principle. In so doing, we find that quantum correlations are degraded if the deformed quantum mechanical model mimics a positive cosmological constant. This opens up the possibility to recover classicality at sufficiently large distances.

20.Perfect transfer of arbitrary continuous variable states across optical waveguide lattices

Authors:Tonipe Anuradha, Ayan Patra, Rivu Gupta, Aditi Sen De

Abstract: We demonstrate that perfect state transfer can be achieved in an optical waveguide lattice governed by a Hamiltonian with modulated nearest-neighbor couplings. In particular, we report the condition that the evolution Hamiltonian should satisfy in order to achieve perfect transfer of any continuous variable input state. The states that can be transmitted need not have any specific properties - they may be pure or mixed, Gaussian or non-Gaussian in character, and comprise an arbitrary number of modes. We illustrate that the proposed protocol is scalable to two- and three-dimensional waveguide geometries. With the help of local phase gates on all the modes, our results can also be applied to realize a SWAP gate between mirror-symmetric modes about the centre of the waveguide setup.

21.Unitary Complexity and the Uhlmann Transformation Problem

Authors:John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen

Abstract: State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.