Are controlled unitaries helpful?

• URL: http://arxiv.org/abs/2508.00055v1
• Date: Thu, 31 Jul 2025 18:00:01 GMT
• Title: Are controlled unitaries helpful?
• Authors: Ewin Tang, John Wright,
• Abstract summary: We show that having access to $cU$ does not help for a large class of quantum problems.<n>We show how to decontrol'' a quantum circuit into one which uses only $U$ and $Udagger$ and outputs $|psi(varphi U)rangle$.
• Score: 3.084918555654188
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many quantum algorithms, to compute some property of a unitary $U$, require access not just to $U$, but to $cU$, the unitary with a control qubit. We show that having access to $cU$ does not help for a large class of quantum problems. For a quantum circuit which uses $cU$ and $cU^\dagger$ and outputs $|\psi(U)\rangle$, we show how to ``decontrol'' the circuit into one which uses only $U$ and $U^\dagger$ and outputs $|\psi(\varphi U)\rangle$ for a uniformly random phase $\varphi$, with a small amount of time and space overhead. When we only care about the output state up to a global phase on $U$, then the decontrolled circuit suffices. Stated differently, $cU$ is only helpful because it contains global phase information about $U$. A version of our procedure is described in an appendix of Sheridan, Maslov, and Mosca [SMM09]. Our goal with this work is to popularize this result by generalizing it and investigating its implications, in order to counter negative results in the literature which might lead one to believe that decontrolling is not possible. As an application, we give a simple proof for the existence of unitary ensembles which are pseudorandom under access to $U$, $U^\dagger$, $cU$, and $cU^\dagger$.

Related papers

• Learning junta distributions, quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counterparts (quantum junta states) and $mathsfQAC0$ circuits.<n>We show that $n$-qubit $mathsfQAC0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2O(log(s22a)d)log (n)$ copies of the Choi state.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Efficient Circuit-Based Quantum State Tomography via Sparse Entry Optimization [0.6008132390640295]
  We propose an efficient circuit-based quantum state tomography scheme to reconstruct $n$-qubit states with $k$ nonzero entries. We provide an upper limit on the number of CNOT gates based on the nonzero entries' positions in $|psirangle$.
  arXiv  Detail & Related papers  (2024-07-29T02:59:13Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  We show that a phase estimation algorithm with precision $delta$ and error probability $epsilon$ has cost $Omegaleft(frac1deltalog1epsilonright)$. We also show that having lots advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$.
  arXiv  Detail & Related papers  (2023-05-08T17:46:01Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
  arXiv  Detail & Related papers  (2022-09-29T03:34:03Z)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip. We propose a method to efficiently verify such noisy intermediate-scale quantum computation.
  arXiv  Detail & Related papers  (2021-09-30T08:56:30Z)
• Simplest non-additive measures of quantum resources [77.34726150561087]
  We study measures that can be described by $cal E(rhootimes N) =E(e;N) ne Ne$.
  arXiv  Detail & Related papers  (2021-06-23T20:27:04Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Tamper Detection against Unitary Operators [0.0]
  We extend the scope of the theory of tamper detection codes against an adversary with quantum capabilities. A quantum codeword $vert psi_m rangle$ can be adversarially tampered via a unitary $U$ from some known tampering unitary family. We show that quantum tamper detection codes exist for any family of unitary operators.
  arXiv  Detail & Related papers  (2021-05-10T16:26:41Z)
• Unitarization Through Approximate Basis [0.0]
  Unitarization is the problem of taking $k$ input circuits that produce quantum states from the all $0$ state. We find an approximate basis in time for the following parameters.
  arXiv  Detail & Related papers  (2021-04-01T22:11:05Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.