Although quantum computers have the potential to efficiently solve certain problems considered difficult by known classical approaches, the design of a quantum circuit remains computationally difficult. It is known that the optimal gate-design problem is equivalent to the solution of an associated optimal-control problem; the solution to which is also computationally intensive. Hence, in this article, we introduce the application of a class of numerical methods (termed the max-plus curse of dimensionality-free techniques) that determine the optimal control, thereby synthesizing the desired unitary gate. The application of this technique to quantum systems has a growth in complexity that depends on the cardinality of the control-set approximation rather than the much larger growth with respect to spatial dimensions in approaches based on gridding of the space, which is used in previous research. This technique is demonstrated by obtaining an approximate solution for the gate synthesis on SU(4)---a problem that is computationally intractable by grid-based approaches.
The process of obtaining solutions to optimal control problems via mesh based techniques suffers from the well known problem of the curse of dimensionality. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting elements (qubits) that they contain. In this article we develop a modification of recently introduced curse-of-dimensionality-free max-plus techniques, to the control of quantum systems. This method yields a more manageable growth that is related to the cardinality of the control set. Its efficacy is demonstrated by obtaining an approximate solution to a previously intractable problem on a 2 qubit system.
Solutions to optimal control problems can be obtained via grid-based dynamic programming iterations. However, such an approach is prohibitively expensive for problems with higher state dimensions, due to the exponential increase in grid points required in approximating the state space. This issue is especially severe in quantum systems whose dimensions grow exponentially with the number of interacting subsystems therein. In this paper, we study state synchronisation of two coupled qubits as an optimal control problem by tuning the interaction Hamiltonian of the system, whose dynamic programming equation is solved via a min-plus curse-of-dimensionality-free method. An illustration in the context of numerical examples is also provided.
Recently a new class of techniques termed the max-plus curse of dimensionality-free methods have been developed to solve nonlinear optimal control problems. In these methods the discretization in state space is avoided by using a max-plus basis expansion of the value function. This requires storing only the coefficients of the basis functions used for representation. However, the number of basis functions grows exponentially with respect to the number of time steps of propagation to the time horizon of the control problem. This so called "curse of complexity" can be managed by applying a pruning procedure which selects the subset of basis functions that contribute most to the approximation of the value function. The pruning procedures described thus far in the literature rely on the solution of a sequence of high dimensional optimization problems which can become computationally expensive. In this paper we show that if the max-plus basis functions are linear and the region of interest in state space is convex, the pruning problem can be efficiently solved by the bundle method. This approach combining the bundle method and semidefinite formulations is applied to the quantum gate synthesis problem, in which the state space is the special unitary group (which is non-convex). This is based on the observation that the convexification of the unitary group leads to an exact relaxation. The results are studied and validated via examples.
Recent years have witnessed the fast development of quantum computing. Researchers around the world are eager to run larger and larger quantum algorithms that promise speedups impossible to any classical algorithm. However, the available quantum computers are still volatile and error-prone. Thus, layout synthesis, which transforms quantum programs to meet these hardware limitations, is a crucial step in the realization of quantum computing. In this paper, we present two synthesizers, one optimal and one approximate but nearly optimal. Although a few optimal approaches to this problem have been published, our optimal synthesizer explores a larger solution space, thus is optimal in a stronger sense. In addition, it reduces time and space complexity exponentially compared to some leading optimal approaches. The key to this success is a more efficient spacetime-based variable encoding of the layout synthesis problem as a mathematical programming problem. By slightly changing our formulation, we arrive at an approximate synthesizer that is even more efficient and outperforms some leading heuristic approaches, in terms of additional gate cost, by up to 100%, and also fidelity by up to 10x on a comprehensive set of benchmark programs and architectures. For a specific family of quantum programs named QAOA, which is deemed to be a promising application for near-term quantum computers, we further adjust the approximate synthesizer by taking commutation into consideration, achieving up to 75% reduction in depth and up to 65% reduction in additional cost compared to the tool used in a leading QAOA study.
Gate-model quantum computers provide an experimentally implementable architecture for near-term quantum computations. To design a reduced quantum circuit that can simulate a high-complexity reference quantum circuit, an optimization should be taken on the number of input quantum states, on the unitary operations of the quantum circuit, and on the number of output measurement rounds. Besides the optimization of the physical layout of the hardware layer, the quantum computer should also solve difficult computational problems very efficiently. To yield a desired output system, a particular objective function associated with the computational problem fed into the quantum computer should be maximized. The reduced gate structure should be able to produce the maximized value of the objective function. These parallel requirements must be satisfied simultaneously, which makes the optimization difficult. Here, we demonstrate a method for designing quantum circuits for gate-model quantum computers and define the Quantum Triple Annealing Minimization (QTAM) algorithm. The aim of QTAM is to determine an optimal reduced topology for the quantum circuits in the hardware layer at the maximization of the objective function of an arbitrary computational problem.
Circuit synthesis of multi-controlled gates is crucial for qudit (
d-level) quantum computing. This paper presents efficient synthesis schemes that reduce the elementary gate count for multi-controlled single-qudit gates. For synthesizing general
(n−1)-controlled unitaries on
n qudits, we reduce the controlled-increment (CINC) and generalized controlled-
X (GCX) gate counts to
O(n2), improving upon existing
O(n2+log2d) CINC and
O(n3) GCX bounds. For
(n−1)-controlled special unitaries, this complexity is further reduced to
O(n). Furthermore, we present a method for approximately synthesizing multi-controlled unitary gates with a linear complexity in the number of control qudits. By utilizing the proposed circuit, we present qudit-based circuit constructions for isometries and quantum channels from
n to
m qudits. Moreover, for the first time, we present a circuit synthesis scheme for single-controlled gates using SUM gates and single-qudit gates when
d is prime. This enables all CINC-based circuits for various quantum operations to be converted into SUM-gate circuits while preserving the same asymptotic complexity. Finally, we establish a theoretical lower bound on the number of SUM and CINC gates required to synthesize general
n-qudit unitaries.