Source-linked AI summary
Computational advantage from quantum-controlled ordering of gates
Mateus Araújo, Fabio Costa, Časlav Brukner
TL;DR
The paper asks whether its algorithmic analogy extends to arbitrary hidden-subgroup functions. It constructs an n-router from polynomially many elementary resources and shows that its circuit implementation has running time n, while implementing all permutations requires at least n^2 queries.
Problem
The paper asks whether the algorithm can find the period of any function that is constant on hidden-subgroup cosets and distinct across different cosets.
Method
The paper constructs an n-router by decomposing control values into factoradic representations and implementing the associated mode permutations with elementary resources.
Results
The algorithm finds y and therefore the period r for the specified hidden-subgroup function, while implementing all permutations requires at least n^2 queries.
Takeaways & Limitations
The construction provides a circuit implementation of the n-router with running time n, alongside a query lower bound of n^2 for circuits capable of all permutations.
Abstract
from arXiv · showhide
It is usually assumed that a quantum computation is performed by applying gates in a specific order. One can relax this assumption by allowing a control quantum system to switch the order in which the gates are applied. This provides a more general kind of quantum computing, that allows transformations on blackbox quantum gates that are impossible in a circuit with fixed order. Here we show that this model of quantum computing is physically realizable, by proposing an interferometric setup that can implement such a quantum control of the order between the gates. We show that this new resource provides a reduction in computational complexity: we propose a problem that can be solved using $O(n)$ blackbox queries, whereas the best known quantum algorithm with fixed order between the gates requires $O(n^2)$ queries. Furthermore, we conjecture that solving this problem in a classical computer takes exponential time, which may be of independent interest.
Appendix A: Existence proof of the sets of unitaries
The appendix constructs sets of n unitary matrices realizing every promised property P_y, using generalized X and Z matrices and permutation phase relations. The construction requires dimension d ≥ n!, while explicit implementations remain polynomial-size.
- Existence of the constructions: For every n ≥ 1 and y ∈ {0, …, n! − 1}, there exists a set of n unitaries satisfying property P_y.This ensures the promise problem is nontrivial for every promised label.
- Permutation phases: The construction labels permutations through factoradic representations and assigns distinct phases to their ordered products.A permutation is encoded by coefficients (a_n−1, …, a_1), with 0 ≤ a_k ≤ k.
- Unitary construction: Generalized X and Z matrices generate the required pairwise commutation relations and can be adapted from ω to ω^y for arbitrary y.The same construction therefore realizes property P_1 and its generalization to all P_y.
- Existence of the constructions: The construction yields infinitely many valid unitary sets because the basis used to define X and Z is arbitrary.This establishes multiplicity beyond a single explicit realization.
- Resource requirements: The explicit construction has dimension d = n!^(n−1) and acts on O(n^2 log n) qubits, while remaining implementable with polynomially many elementary gates.Its matrices are tensor products of Z and X^k operators.
- Lower-dimensional examples: For n = 3, a 6-dimensional construction works, and this saturates the lower bound d ≥ n!.Whether dimension n! is achievable for every n remains open in the appendix.
Appendix B: Tolerating experimental error
The appendix modifies the promise problem to tolerate experimental deviations from exact properties by using Hilbert–Schmidt-norm conditions and a maximally mixed input state. These conditions preserve a probabilistic separation between the correct and incorrect labels.
- Error-tolerant formulation: Experimental error is handled by replacing exact property P_y with a modified property P′_y expressed through the Hilbert–Schmidt norm.The norm-based formulation follows from its definition through an inner product.
- Choice of input state: An arbitrary pure state cannot generally be used because the outcome probabilities may depend on the chosen state.The appendix gives cases where the norm condition is nearly satisfied while the probability p_y vanishes for some |ψ⟩.
- Choice of input state: The maximally mixed state makes the measurement probabilities directly related to the Hilbert–Schmidt norm.This removes the dependence on an arbitrary pure input state in the error-tolerant protocol.
- Decision guarantees: The promise gives p_s ≥ 2/3 for s = y and p_s < 1/3 for s ≠ y.These bounds provide the separation required by the probabilistic decision procedure.
- Decision guarantees: Repeating the algorithm k times and selecting the most common answer reduces the probability of error exponentially in k.The conclusion follows from the stated probability gap between the correct and incorrect outcomes.
Appendix C: Implementing the n-switch gate in the quantum circuit model
The appendix gives a circuit-model simulation of the n-switch using a permutation-encoded control register, ancillas, controlled swaps, and n layers containing all n unitaries. This construction has running time n but uses n^2 queries and is restricted to suitable unitary sequences.
- Simulation architecture: The circuit simulation extends a prior construction to quantum control of the order rather than only classical control.The scheme is based on a circuit introduced in Ref. [5].
- Control representation: The control register uses n⌈log_2 n⌉ qubits, with each register component specifying the unitary placed at a position.For example, |102⟩ encodes the order U_1, then U_0, then U_2.
- Simulation architecture: The circuit composes n elements, each using controlled swaps between the target and ancillas to select the unitary indicated by the control.Each element contains n unitaries and uses a linear number of elementary gates for its swap operation.
- Query and time costs: The construction uses n^2 queries because n layers each contain all n unitaries.This matches the operational definition of gate uses introduced in the main text.
- Scope of the simulation: Ancillas disentangle when the control encodes permutations or sequences applying each unitary a fixed number of times, but not for arbitrary sequences.Thus the circuit does not implement quantum control of arbitrary sequences of n unitaries.
- Query and time costs: With swap-gate time neglected, the circuit has running time n, but no implementation with fewer than Ω(n^2) queries is possible for the n-switch.Reducing queries is possible only at the expense of increased running time in the discussed constructions.
Appendix D: Relationship with other quantum algorithms
The appendix compares the algorithm with hidden-subgroup and period-finding methods. Although both use the quantum Fourier transform, the analogy breaks down because the relevant superposition is nonuniform and can require exponentially many repetitions.
- Comparison with hidden-subgroup methods: The paper investigates whether the algorithm has a deeper relationship with hidden-subgroup algorithms beyond their shared use of the quantum Fourier transform.The comparison is motivated by similarities to abelian hidden-subgroup methods.
- Hidden-subgroup formulation: In the hidden subgroup problem, a black-box function is constant on cosets of a hidden subgroup and distinct across different cosets.This supplies the comparison framework for the appendix.
- A related hidden-subgroup instance: For f(x) = ω^(xy), the paper identifies period r = n! / gcd(y, n!) and shows that its algorithm finds y and therefore r.The function satisfies the hidden-subgroup promise over Z_n! with addition modulo n!.
- Limits of the analogy: The proposed analogy does not extend to arbitrary hidden-subgroup functions f′(x) = ω^g(x) that are constant on cosets and distinct between cosets.The appendix explicitly poses this broader period-finding question before showing the limitation.
- Limits of the analogy: For the nonuniform superposition arising here, the worst case requires exponentially many repetitions rather than the constant repetitions sufficient for period finding.When g(l) = l mod n!, obtaining an informative outcome can require O(n!^2) measurements for constant r.
- Limits of the analogy: The appendix concludes that the true connection to period finding and hidden-subgroup algorithms is only their common use of the quantum Fourier transform.The authors do not identify a deeper connection to those algorithmic classes.
Appendix E: Decomposition of the n-router
The n-router realizes permutations of input modes by decomposing factoradic control data into controlled neighboring-mode swaps. This construction uses a polynomial number of PBS-equivalent resources, although its encoding is not asymptotically optimal.
- Construction: The n-router maps each input mode |j⟩in to the output mode |σ_x(j)⟩out specified by control value x.The control value is represented in factoradic form to identify the permutation.
- Construction: Each factoradic coefficient a_k is encoded with k bits, where the first a_k bits are 1 and the remainder are 0.This encoding uses O(n^2) bits rather than the minimal O(n log n).
- Construction: The router decomposes each factoradic shift into neighboring controlled swaps, with one swap associated with each control bit.The resulting controlled swap is equivalent to a polarizing beam splitter and is treated as a new elementary resource.
- Construction: The swaps are applied successively in increasing k and, for each k, increasing j, thereby realizing the permutation encoded by the control system.This ordering applies the |b^1_1⟩ swap first, followed by the swaps for k=2, k=3, and so on.
- Example: A coefficient a_3=2 applies two swaps, producing the cycle |3⟩→|1⟩, |1⟩→|2⟩, and |2⟩→|3⟩.The third controlled swap is omitted because its control bit is 0.