Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution
can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al.
A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding correspo
nds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting.
Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the e
ven more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two lobes separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.
It is well-known that deciding equivalence of logic circuits is a coNP-complete problem. As a corollary, the problem of deciding weak equivalence of reversible circuits, i.e. ignoring the ancilla bits, is also coNP-complete. The complexity of decidin
g strong equivalence, including the ancilla bits, is less obvious and may depend on gate set. Here we use Barringtons theorem to show that deciding strong equivalence of reversible circuits built from the Fredkin gate is coNP-complete. This implies coNP-completeness of deciding strong equivalence for other commonly used universal reversible gate sets, including any gate set that includes the Toffoli or Fredkin gate.
An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mai
nly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.
