More Like this

1. Linear growth of quantum circuit complexity

   https://doi.org/10.1038/s41567-022-01539-6  

   Haferkamp, Jonas; Faist, Philippe; Kothakonda, Naga B.; Eisert, Jens; Yunger Halpern, Nicole (May 2022, Nature Physics)

   Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits. 

   more » « less
2. Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes

   https://doi.org/10.22331/q-2019-08-26-180  

   Lavasani, Ali; Zhu, Guanyu; Barkeshli, Maissam (August 2019, Quantum)

   A basic question in the theory of fault-tolerant quantum computation is to understand the fundamental resource costs for performing a universal logical set of gates on encoded qubits to arbitrary accuracy. Here we consider qubits encoded with constant space overhead (i.e. finite encoding rate) in the limit of arbitrarily large code distance d through the use of topological codes associated to triangulations of hyperbolic surfaces. We introduce explicit protocols to demonstrate how Dehn twists of the hyperbolic surface can be implemented on the code through constant depth unitary circuits, without increasing the space overhead. The circuit for a given Dehn twist consists of a permutation of physical qubits, followed by a constant depth local unitary circuit, where locality here is defined with respect to a hyperbolic metric that defines the code. Applying our results to the hyperbolic Fibonacci Turaev-Viro code implies the possibility of applying universal logical gate sets on encoded qubits through constant depth unitary circuits and with constant space overhead. Our circuits are inherently protected from errors as they map local operators to local operators while changing the size of their support by at most a constant factor; in the presence of noisy syndrome measurements, our results suggest the possibility of universal fault tolerant quantum computation with constant space overhead and time overhead of O ( d / log ⁡ d ) . For quantum circuits that allow parallel gate operations, this yields the optimal scaling of space-time overhead known to date. 

   more » « less
3. Quantum Circuit Synthesis Using Fuzzy-Logic-Assisted Genetic Algorithms

   https://doi.org/10.3390/a18040178  

   Islam, Ishraq; Jha, Vinayak; Thomas, Sneha; Egan, Kieran F; Nobel, Alvir; Kim, Serom; Chaudhary, Manu; Ogundele, Sunday; Kneidel, Dylan; Phillips, Ben; et al (April 2025, Algorithms)

   Quantum algorithms will likely play a key role in future high-performance-computing (HPC) environments. These algorithms are typically expressed as quantum circuits composed of arbitrary gates or as unitary matrices. Executing these on physical devices, however, requires translation to device-compatible circuits, in a process called quantum compilation or circuit synthesis, since these devices support a limited number of native gates. Moreover, these devices typically have specific qubit topologies, which constrain how and where gates can be applied. Consequently, logical qubits in input circuits and unitaries may need to be mapped to and routed between physical qubits. Furthermore, current Noisy Intermediate-Scale Quantum (NISQ) devices present additional constraints. They are vulnerable to errors during gate application and their short decoherence times lead to qubits rapidly succumbing to accumulated noise and possibly corrupting computations. Therefore, circuits synthesized for NISQ devices need to minimize gates and execution times. The problem of synthesizing device-compatible circuits, while optimizing for low gate count and short execution times, can be shown to be computationally intractable using analytical methods. Therefore, interest has grown towards heuristics-based synthesis techniques, which are able to produce approximations of the desired algorithm, while optimizing depth and gate-count. In this work, we investigate using genetic algorithms (GA)—a proven gradient-free optimization technique based on natural selection—for circuit synthesis. In particular, we formulate the quantum synthesis problem as a multi-objective optimization (MOO) problem, with the objectives of minimizing the approximation error, number of multi-qubit gates, and circuit depth. We also employ fuzzy logic for runtime parameter adaptation of GA to enhance search efficiency and solution quality in our proposed method. 

   more » « less
4. Quantum circuit cutting with maximum-likelihood tomography

   https://doi.org/10.1038/s41534-021-00390-6  

   Perlin, Michael A.; Saleem, Zain H.; Suchara, Martin; Osborn, James C. (December 2021, npj Quantum Information)

   null (Ed.)

   Abstract We introduce maximum-likelihood fragment tomography (MLFT) as an improved circuit cutting technique for running clustered quantum circuits on quantum devices with a limited number of qubits. In addition to minimizing the classical computing overhead of circuit cutting methods, MLFT finds the most likely probability distribution for the output of a quantum circuit, given the measurement data obtained from the circuit’s fragments. We demonstrate the benefits of MLFT for accurately estimating the output of a fragmented quantum circuit with numerical experiments on random unitary circuits. Finally, we show that circuit cutting can estimate the output of a clustered circuit with higher fidelity than full circuit execution, thereby motivating the use of circuit cutting as a standard tool for running clustered circuits on quantum hardware. 

   more » « less
5. Revolutionizing Computations: Quantum Circuit Analogues with Nonlinear Acoustic Waves

   Hasan, M Arif; Deymier, Pierre; Runge, Keith; Levine, Josh (March 2024, The American Institute of Physics, publisher, Bulletin of the American Physical Society)

   Quantum computing utilizes superposition and entanglement to surpass classical computer capabilities. Central to this are qubits and their use to realize parallel quantum algorithms through circuits of simple one or two qubit gates. Controlling and measuring quantum systems is challenging. Here, we introduce a paradigm utilizing logical phi-bits, classical analogues of qubits using nonlinear acoustic waves, supported by an externally driven acoustic metastructure. These phi-bits bridge a low-dimensional linearly scaling physical space to a high-dimensional exponentially scaling Hilbert space in which parallel processing of information can be realized in the form of unitary operations. Here, we show the implementation of a nontrivial three-phi-bit unitary operation analogous to a quantum circuit but achieved via a single action on the metastructure, whereby the qubit-based equivalent requires sequences of qubit gates. A phi-bit-based approach might offer advantages over quantum systems, especially in tasks requiring large complex unitary operations. This breakthrough hints at a fascinating intersection of classical and quantum worlds, potentially redefining computational paradigms by harnessing nonlinear classical mechanical systems in quantum-analogous manners, blending the best of both domains. 

   more » « less