pith. sign in

arxiv: 2508.00055 · v2 · submitted 2025-07-31 · 🪐 quant-ph · cs.CC· cs.DS

Are controlled unitaries helpful?

Ewin Tang , John Wright This is my paper

Pith reviewed 2026-05-19 01:37 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DS
keywords controlled unitariesdecontrolquantum query complexityglobal phaseunitary accesspseudorandom ensemblesquantum algorithms
0
0 comments X

The pith

Access to controlled unitaries adds no advantage beyond global phase information for many quantum problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that circuits using controlled versions of a unitary U and its inverse can be replaced by circuits using only the uncontrolled U and U inverse. The replacement produces an output state that matches the original except for a uniformly random global phase factor on U. When an algorithm cares only about its output state up to that global phase, the simpler uncontrolled circuit works equally well. This result shows that controlled unitaries are useful in practice only because they encode global phase details about U. A reader should care because the finding removes an apparent barrier in quantum algorithm design and supplies a concrete way to simplify many existing constructions.

Core claim

For a quantum circuit that uses cU and cU† and outputs |ψ(U)⟩, there exists a decontrol procedure that produces an equivalent circuit using only U and U† and outputting |ψ(ϕU)⟩ for a uniformly random phase ϕ. When the algorithm needs the output only up to global phase on U, the decontrolled circuit is sufficient. Equivalently, cU helps only by supplying global phase information about U.

What carries the argument

The decontrol procedure that rewrites any circuit containing controlled-U and controlled-U dagger gates into an equivalent uncontrolled circuit that applies U and U dagger plus a random phase.

If this is right

  • Quantum algorithms that appear to require controlled unitaries can be rewritten using only direct access to U and U† when global phase is irrelevant.
  • The existence of unitary ensembles that remain pseudorandom even under access to U, U†, cU, and cU† follows directly from the decontrol step.
  • Query complexity lower bounds proved for uncontrolled unitaries automatically apply to the controlled case for problems insensitive to global phase.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Hardware implementations of quantum oracles may avoid extra control qubits in many cases without changing the problem's computational power.
  • Phase estimation routines that deliberately extract global phase information remain outside the reach of this simplification.
  • The result invites checking whether similar decontrol techniques apply to controlled versions of other quantum operations such as measurements or channels.

Load-bearing premise

The algorithm needs only the output state up to a global phase on U and does not rely on information carried by the phase itself.

What would settle it

Exhibit one concrete quantum problem where a circuit using cU solves the task with strictly fewer queries or lower error than any circuit using only U and U†, even after ignoring global phases.

Figures

Figures reproduced from arXiv: 2508.00055 by Ewin Tang, John Wright.

Figure 1
Figure 1. Figure 1: A simple one-query circuit. Letting |Circ(c(ϕU))⟩ denote the output of this circuit, our goal is to simulate the mixed state E ϕ∼Cq h |Circ(c(ϕU))⟩⟨Circ(c(ϕU))| i for some reasonably large number q. In this case, we can write the output state as |Circ(c(ϕU))⟩ = c(ϕU)A |0⟩ = (I ⊗ |0⟩⟨0|C) · A |0⟩ + (ϕU ⊗ |1⟩⟨1|C) · A |0⟩ =: |FP0⟩ + ϕ |FP1⟩, where |FPb⟩ is the Feynman path corresponding to the part of the st… view at source ↗
Figure 2
Figure 2. Figure 2: Simulating the one-query circuit with a mid-circuit measurement. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Simulating the one-query circuit without mid-circuit measurements. The area in the dashed box is [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A generic circuit which uses controlled queries to [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The circuit diagram for |FP1,1,0⟩, as defined in Definition 2.2. With these definitions, we can decompose the output of the circuit, when the black-box unitary is c(φU). Claim 2.3 (Decomposing a single output into Feynman paths). Let φ ∈ C have unit magnitude. Then |Circ(c(φU))⟩ = X bn,...,b1∈{0,1} φ ?nbn · · · φ ?1b1 |FPb1,...,bn ⟩ = X∞ k=−∞ φ k |FP(k)⟩ Proof. First, notice that (c(φU))? CR = (c((φU) ? ))… view at source ↗
Figure 6
Figure 6. Figure 6: The circuit diagram for the decontrolled circuit [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Shown are the outputs of S applied to controlled queries. We “decontrol” a general circuit by replacing the controlled queries by their corresponding gadgets ( [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
read the original 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 (arXiv:0810.3843). 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper shows that controlled unitaries cU are not helpful for a large class of quantum problems where the output state is only required up to a global phase on U. It provides an explicit 'decontrol' transformation that replaces uses of cU and cU† in a circuit with uses of U and U†, resulting in an output state |ψ(ϕU)⟩ where ϕ is a uniformly random phase. This transformation incurs only a small overhead in time and space. The result generalizes an appendix from Sheridan, Maslov, and Mosca (arXiv:0810.3843) and is applied to prove the existence of pseudorandom unitary ensembles that are secure even when the adversary has access to cU and cU†.

Significance. This clarification on the role of controlled unitaries has the potential to simplify the design of quantum algorithms and circuits by showing that cU access can often be replaced without loss of functionality when global phases are irrelevant. The straightforward proof for pseudorandom ensembles under full access (including controls) is a notable contribution that could find use in quantum cryptography. By popularizing this decontrol technique, the paper helps mitigate the impact of negative results that might suggest decontrolling is impossible.

minor comments (3)
  1. [Abstract] The abstract states that the transformation has 'a small amount of time and space overhead' but does not quantify it; the main text should give an explicit bound (e.g., O(1) additional qubits and linear overhead in the number of controlled gates) to make the claim precise.
  2. [Decontrol procedure] The decontrol construction would benefit from a short worked example (a 2- or 3-qubit circuit before and after transformation) to illustrate how the random phase is introduced and how the output state is preserved up to that phase.
  3. [Application] In the pseudorandom-ensemble application, the argument that the random phase ϕ does not increase the distinguishing advantage should be stated explicitly rather than left implicit, even if it follows directly from the main theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review and recommendation for minor revision. The referee's summary accurately captures our main results on the decontrol transformation for controlled unitaries and its application to pseudorandom ensembles. We appreciate the recognition of the work's potential to simplify quantum circuit design and to counter misconceptions about decontrolling.

Circularity Check

0 steps flagged

No significant circularity; derivation rests on independent 2008 citation

full rationale

The paper attributes its core decontrol transformation to an appendix in Sheridan, Maslov, and Mosca (arXiv:0810.3843) and states its goal is to generalize and popularize that result for new applications such as pseudorandom unitary ensembles. No load-bearing self-citation exists, no parameter is fitted and then renamed as a prediction, and no ansatz or uniqueness claim is smuggled via the authors' own prior work. The central equivalence (cU circuit to U circuit plus random phase) is presented as a direct, explicit construction whose correctness is independent of the present paper's fitted values or definitions. The result is therefore self-contained against the cited external reference.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard quantum circuit axioms and the definition of controlled unitaries; no new free parameters, invented entities, or ad-hoc assumptions are introduced beyond those already standard in the field.

axioms (1)
  • standard math Quantum circuits are composed of unitary gates and measurements in the standard circuit model.
    Invoked throughout the description of decontrolling circuits.

pith-pipeline@v0.9.0 · 5787 in / 1229 out tokens · 47197 ms · 2026-05-19T01:37:29.731971+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Split-Evolution Quantum Phase Estimation for Particle-Conserving Hamiltonians

    quant-ph 2026-04 unverdicted novelty 7.0

    SE-QPE modifies canonical QPE by using CSWAP interference to remove controlled-simulation overhead while preserving phase outcomes for particle-conserving Hamiltonians with shared eigenbases, yielding resource reducti...

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Shadow Tomography of Quantum States

    [Aar20] Scott Aaronson. “Shadow tomography of quantum states”. In:SIAM Journal on Computing(2020). doi: 10.1137/18m120275x. arXiv: 1711.01053 [quant-ph] (page 4). [AFCB14] Mateus Araújo, Adrien Feix, Fabio Costa, and Časlav Brukner. “Quantum circuits cannot control unknown operations”. In:New Journal of Physics(2014). doi: 10.1088/1367- 2630/16/9/093026 ....

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/18m120275x 2020

  2. [2]

    Quantum approximate counting, simplified

    doi: 10.1145/1132516.1132579. arXiv: quant-ph/0511096 (page 5). [AR20] Scott Aaronson and Patrick Rall. “Quantum approximate counting, simplified”. In:Symposium on Simplicity in Algorithms

    work page doi:10.1145/1132516.1132579

  3. [3]

    Quantum event learning and gentle random measurements

    doi: 10.1137/1.9781611976014.5 . arXiv: 1908.10846 [quant-ph] (page 5). [BB24] Adam Bene Watts and John Bostanci. “Quantum event learning and gentle random measurements”. en. In:15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

    work page doi:10.1137/1.9781611976014.5 1908

  4. [4]

    Quantum fingerprinting

    4230/LIPIcs.ITCS.2024.97. arXiv: 2210.09155 [quant-ph] (page 4). [BCWW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. “Quantum fingerprinting”. In: Physical Review Letters(2001). doi: 10.1103/physrevlett.87.167902 . arXiv: quant- ph/0102001 [quant-ph] (page 5). [BDP16] Alessandro Bisio, Michele Dall’Arno, and Paolo Perinotti. “Quantum ...

    work page doi:10.1103/physrevlett.87.167902 2024

  5. [5]

    Minor containment and disjoint paths in almost-linear time

    doi: 10.1109/focs61266.2024.00069. arXiv: 2405.00082 [quant-ph] (page 6). [BO24] Costin Bădescu and Ryan O’Donnell. “Improved quantum data analysis”. In:TheoretiCS (2024). doi: 10.46298/theoretics.24.7. arXiv: 2011.10908 [quant-ph] (page 4). [CBW24] Anirban Chowdhury, Ewout van den Berg, and Pawel Wocjan. “Controlization schemes based on orthogonal arrays”

    work page doi:10.1109/focs61266.2024.00069 2024

  6. [6]

    Quantum phase estimation without controlled unitaries

    arXiv:2407.09382 [quant-ph] (pages 6, 8). [CCGMSS24] Laura Clinton, Toby S. Cubitt, Raul Garcia-Patron, Ashley Montanaro, Stasja Stanisic, and Maarten Stroeks. “Quantum phase estimation without controlled unitaries”

    work page arXiv

  7. [7]

    Chiribella, G

    arXiv:2410.21517 [quant-ph] (page 5). [CDP08] G. Chiribella, G. M. D’Ariano, and P. Perinotti. “Quantum circuit architecture”. In:Physical Review Letters (2008). doi: 10.1103/physrevlett.101.060401. arXiv: 0712.1325 [quant-ph] (page 8). 16 [CW12] Andrew M. Childs and Nathan Wiebe. “Hamiltonian simulation using linear combinations of unitary operations”. I...

    work page doi:10.1103/physrevlett.101.060401 2008

  8. [8]

    Implementing quantum control for unknown subroutines

    arXiv: 1911.01645 [quant-ph] (pages 6, 8). [FDDB14] Nicolai Friis, Vedran Dunjko, Wolfgang Dür, and Hans J. Briegel. “Implementing quantum control for unknown subroutines”. In:Physical Review A(2014). doi: 10.1103/physreva.89.030303. arXiv: 1401.8128 [quant-ph] (pages 5, 8). [Gro96] Lov K. Grover. “A fast quantum mechanical algorithm for database search”....

    work page doi:10.1103/physreva.89.030303 1911

  9. [9]

    Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics

    doi: 10.1145/ 237814.237866. arXiv: quant-ph/9605043 (page 1). [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”. In:Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC)

    work page arXiv

  10. [10]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =

    doi: 10.1145/3313276.3316366. arXiv: 1806.01838 (pages 1, 6). [GST24] Zuzana Gavorová, Matan Seidel, and Yonathan Touati. “Topological obstructions to quantum compu- tation with unitary oracles”. In:Physical Review A(2024). doi: 10.1103/physreva.109.032625. arXiv: 2011.10031 [quant-ph] (pages 2, 8). [HHL09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloy...

    work page doi:10.1145/3313276.3316366 2024

  11. [11]

    IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    doi: 10.1109/focs57990.2023.00028. arXiv: 2302.14066 [quant-ph] (page 5). [HLM17] Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. “Sequential measurements, disturbance and property testing”. In:Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

    work page doi:10.1109/focs57990.2023.00028 2023

  12. [12]

    Quantum measurements and the Abelian Stabilizer problem

    doi: 10.1007/978-3-319-96878-0_5. arXiv: 1711.00385 [quant-ph] (page 6). [Kit95] A. Yu. Kitaev. “Quantum measurements and the Abelian Stabilizer problem”. 1995.doi: 10.48550/ ARXIV.QUANT-PH/9511026. arXiv: quant-ph/9511026 (pages 1, 5, 7). [Kre21] William Kretschmer. “Quantum pseudorandomness and classical complexity”. en. In:16th Conference on the Theory...

    work page doi:10.1007/978-3-319-96878-0_5 1995

  13. [13]

    Simplifying quantum logic using higher-dimensional Hilbert spaces

    doi: 10.4230/LIPIcs.TQC.2021.2. arXiv: 2103.09320 [quant-ph] (page 8). [Lan+08] Benjamin P. Lanyon, Marco Barbieri, Marcelo P. Almeida, Thomas Jennewein, Timothy C. Ralph, KevinJ.Resch,GeoffJ.Pryde,JeremyL.O’Brien,AlexeiGilchrist,andAndrewG.White.“Simplifying quantum logic using higher-dimensional Hilbert spaces”. In:Nature Physics(2008). doi: 10.1038/ np...

    work page doi:10.4230/lipics.tqc.2021.2 2021

  14. [14]

    How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs , booktitle =

    doi: 10.1145/3717823.3718254 . arXiv: 2410.10116 [quant-ph] (page 6). [MW16] Ashley Montanaro and Ronald de Wolf. “A Survey of Quantum Property Testing”. In:Theory of Computing (2016) (page 4). [Sho97] Peter W. Shor. “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. In:SIAM Journal on Computing (1997). doi...

    work page doi:10.1145/3717823.3718254 2016

  15. [15]

    Adding control to arbitrary unknown quantum operations

    url: https://ia.cr/2025/1072 (pages 1, 6). [Zho+11] Xiao-Qi Zhou, Timothy C. Ralph, Pruet Kalasuwan, Mian Zhang, Alberto Peruzzo, Benjamin P. Lanyon, and Jeremy L. O’Brien. “Adding control to arbitrary unknown quantum operations”. In: Nature Communications(2011). doi: 10.1038/ncomms1392. arXiv: 1006.2670 [quant-ph] (page 5). 18

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1038/ncomms1392 2025