01714nas a2200181 4500008004100000245004400041210004400085260001500129490000800144520120900152100002801361700002801389700002101417700002001438700001701458700002001475856003701495 2022 eng d00aResource theory of quantum uncomplexity0 aResource theory of quantum uncomplexity c12/19/20220 v1063 a

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or "uncomplexity," the more useful the state is as input to a quantum computation. Separately, resource theories -- simple models for agents subject to constraints -- are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

1 aHalpern, Nicole, Yunger1 aKothakonda, Naga, B. T.1 aHaferkamp, Jonas1 aMunson, Anthony1 aEisert, Jens1 aFaist, Philippe uhttps://arxiv.org/abs/2110.1137101694nas a2200169 4500008004100000245004400041210004400085260001500129520120900144100002801353700002801381700002101409700002001430700001701450700002001467856003701487 2021 eng d00aResource theory of quantum uncomplexity0 aResource theory of quantum uncomplexity c10/21/20213 a

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or ``uncomplexity,'' the more useful the state is as input to a quantum computation. Separately, resource theories -- simple models for agents subject to constraints -- are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

1 aHalpern, Nicole, Yunger1 aKothakonda, Naga, B. T.1 aHaferkamp, Jonas1 aMunson, Anthony1 aEisert, Jens1 aFaist, Philippe uhttps://arxiv.org/abs/2110.1137102434nas a2200205 4500008004100000245006200041210006200103260001500165300001100180490000800191520186900199100001502068700001902083700001902102700001602121700001702137700001702154700002002171856003702191 2018 eng d00aRecovering quantum gates from few average gate fidelities0 aRecovering quantum gates from few average gate fidelities c2018/03/01 a1705020 v1213 a

Characterising quantum processes is a key task in and constitutes a challenge for the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterising processes is randomised benchmarking, which is robust against state preparation and measurement (SPAM) errors, and can be used to benchmark Clifford gates. A complementing approach asks for full tomographic knowledge. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. So far, guarantees for compressed sensing protocols rely on unstructured random measurements and can not be applied to the data acquired from randomised benchmarking experiments. It has been an open question whether or not the favourable features of both worlds can be combined. In this work, we give a positive answer to this question. For the important case of characterising multi-qubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured respect to random Clifford unitaries. Moreover, for general unital quantum channels we provide an explicit expansion into a unitary 2-design, allowing for a practical and guaranteed reconstruction also in that case. As a side result, we obtain a new statistical interpretation of the unitarity -- a figure of merit that characterises the coherence of a process. In our proofs we exploit recent representation theoretic insights on the Clifford group, develop a version of Collins' calculus with Weingarten functions for integration over the Clifford group, and combine this with proof techniques from compressed sensing.

1 aRoth, Ingo1 aKueng, Richard1 aKimmel, Shelby1 aLiu, Yi-Kai1 aGross, David1 aEisert, Jens1 aKliesch, Martin uhttps://arxiv.org/abs/1803.00572