betaFeedback

WorksPhysics and Astronomy

Many Physical Design Problems are Sparse QCQPs

Abstract

Physical design refers to mathematical optimization of a desired objective (e.g. strong light–matter interactions, or complete quantum state transfer) subject to the governing dynamical equations, such as Maxwell's or Schrodinger's differential equations. Computing an optimal design is challenging: generically, these problems are highly nonconvex and finding global optima is NP hard. Here we show that for linear-differential-equation dynamics (as in linear electromagnetism, elasticity, quantum mechanics, etc.), the physical-design optimization problem can be transformed to a sparse-matrix, quadratically constrained quadratic program (QCQP). Sparse QCQPs can be tackled with convex optimization techniques (such as semidefinite programming) that have thrived for identifying global bounds and high-performance designs in other areas of science and engineering, but seemed inapplicable to the design problems of wave physics. We apply our formulation to prototypical photonic design problems, showing the possibility to compute fundamental limits for large-area metasurfaces, as well as the identification of designs approaching global optimality. Looking forward, our approach highlights the promise of developing bespoke algorithms tailored to specific physical design problems.

Precise fabrication techniques and high-quality materials are enabling unprecedented control over photonic and quantum physical systems, opening exciting frontiers for applications from metasurface optics [1, 2] to quantum computing [3, 4]. Yet this flexibility is accompanied by a proportionate complexity: the design spaces are enormous, and classical and quantum wave-interference effects make them highly oscillatory and nonconvex. The corresponding design problem, of discovering optimal patterns in space and/or time, is generically NP hard [5]. In this article, we identify a surprising mathematical structure in design problems arising from the typical differential equations of physics: in many cases, they can be transformed to sparse, quadratically constrained quadratic programs (sparse QCQPs). It is well known that sparse QCQPs can be close to convex optimization problems, in a sense we make precise below, implying that the transformed design problems may have significantly smoother landscapes and that global optima may be easier to approach. The seemingly impenetrable nonconvexity of conventional formulations of physical design has limited scientists and engineers to black-box algorithms or gradient-based local optimization. Our transformations enable direct connection to a wide swath of modern optimization theory, where advances in convex optimization and semidefinite programming have enabled remarkable progress in trajectory optimization (e.g., rocket landings) [6, 7], matrix completion (recommendation systems) [8–10], compressed sensing (network routing) [11, 12], and more. We show that for prototypical problems in domains such as photonic design and quantum control, one can leverage the sparse-QCQP structure to find fundamental limits for large-scale devices, and offer the possibility of identifying designs near global optimality. We develop a general theory for connecting these ideas in nanophotonics, quantum control, and beyond, and offer a new, convex-optimization-based direction for physical design.

In the 1990’s it was recognized that a key dividing line between “easy” and “hard” optimization problems was not linearity versus nonlinearity, but rather convexity versus nonconvexity [13]. Convex optimization problems, with convex objective functions and convex constraint sets, share a remarkable property: all local optima are global optima [14]. Convex optimization problems can be solved efficiently (in polynomial time) for global optima, e.g., by now-standard interior-point methods [14]. Original applications of convex optimization primarily arose in operations research, but over the past two decades, a surprising number of optimization problems have been shown to be transformable to convex, or nearly convex, formulations. In addition to the three applications mentioned above, further examples include ptychography [15, 16], in which wide-field-of-view, high-resolution images are formed from low-resolution samples, and phase retrieval [17, 18], in which one infers phase values from intensity measurements. By contrast, quantum and classical wave dynamics create interference patterns and oscillatory objective landscapes that are clearly nonconvex.

Confronted by the nonconvexity of physical design, two approaches are typically taken. One is to compute gradients of the objective function with respect to the designable degrees of freedom and “ascend” or “descend” using the gradient. A particular breakthrough in the efficiency of such algorithms came from the “adjoint variable” technique [19–21] (or “backpropagation” [22]), which forms the basis of approaches known as “inverse design” [23–25] and “topology optimization” [26–28] in photonics, and “GRAPE” and “Krotov” in quantum control [29–33]. Such inverse-design techniques have been used across linear, nonlinear [34, 35], and even chaotic [36] physical systems. However, as gradient-based techniques, they may get stuck in low-quality local extrema, and they offer no insight into global bounds (or, “fundamental limits”).

Alternatively, one can use techniques intended for global optimization; early interest in evolutionary algorithms has largely been supplanted by modern research in neural networks. Yet neural networks typically excel in scenarios where modeling is difficult and an extraordinary amount of data is available (such as image recognition and large language models). In physical design, data is expensive to generate (full differential-equation simulations), we have exact models (the differential equations themselves), and learning across architectures, material platforms, and frequency ranges has proven difficult. There have been a number of pioneering efforts in applying machine learning to physical design [37, 38, 39, 40], but it is highly unclear whether they can generally out-perform gradient-based inverse design once all computational costs associated with training are included.

A complementary approach to bottom-up, iterative optimization has been a recent surge of interest in fundamental limits, particularly in optics and photonics [41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57]. Conventionally, bounds such as the Yablonovitch enhancement limit in electromagnetism [58], or the Mandelstamm–Tamm bounds in quantum control [59], arise from identifying singular constraints in physical systems (density of states and energy–time uncertainty, for the two examples). Recently, an alternative approach was proposed in which computational bounds could be found from an infinite set of constraints implied by integral [54, 60, 61] or differential [62] [5] equations. The differential-equation-based approaches requires a transformation to real-valued variables and a relaxation of the design problem (cf. SM), while the matrices in the integral QCQPs are dense, due to their integral-equation origins, leading to two issues: First, solving their semidefinite relaxations for bounds requires O(N4)O(N^4) computational time, for NN degrees of freedom, which quickly becomes prohibitive and restricts analysis to few-degree-of-freedom systems. Second, the ranks of the solutions of the semidefinite relaxations are unbounded; as we describe in depth below, this means that the solutions of the semidefinite programs may have little-to-no correlation with physically meaningful structures, let alone optimal designs.

The approach we describe here is a new, joint formulation of physical design and its fundamental limits. Starting with a generic specification of a physical design problem with differential-equation constraints, we describe general techniques for transformation to a sparse QCQP optimization problem. We show that the new problem is mathematically equivalent to the original, yet with a structure more similar to that of pytchography, trajectory optimization, or matrix completion, instead of conventional physical design. The “dual” [14] of our sparse-QCQP problem is a (convex) semidefinite program (SDP), whose solution always represents a fundamental limit across the design space of interest. Moreover, the sparse nature of the differential operators leads to bounds on the rank of the solution of the SDP, which often must be small (e.g., independent of the diameter of a metasurface). A rank-one solution would represent the globally optimal design across the design space; low-rank solutions can potentially be regularized towards rank-one solutions. We give an example of exactly such an approach, leading to a plausibly globally optimal nanophotonic structure for a prototype problem on which “inverse design” struggles to overcome moderate-quality local optima. Our formulation enables the identification of bounds for optimal design with linear differential equations, and offers a new approach to circumvent the oscillatory landscapes that plague the design of wave-based systems.

Reformulating Physical Design

The prototypical design problem has a physical field ψ\psi (electromagnetic, quantum, etc.), designable degrees of freedom χ\chi (a susceptibility, a control-Hamiltonian amplitude, etc.), and a differential equation linking the two. We consider differential equations that are linear in the field variable. We denote by ξ\xi a vector-field excitation (which can be zero for an eigenproblem), representing an incoming wave or initial condition. The goal is to maximize (or minimize) some objective f(ψ)f(\psi) that is a function of the field variable. Then the design problem can be written:

max.⁡χ,ψf(ψ)s.t.L(χ)ψ−ξ=0,(1)\begin{aligned} \underset{\chi,\psi}{\operatorname{max.}} \quad& f(\psi) \\ \text{s.t.} \quad& \mathcal{L}(\chi)\psi-\xi=0, \tag*{(1)} \end{aligned}

where L\mathcal{L} represents the linear differential operator. We include χ\chi as an argument to L\mathcal{L} to emphasize the dependence of L\mathcal{L} on the design variables. In nanophotonics, where one might seek an optimal susceptibility pattern χ(x)\chi(x) in space to harness electromagnetic waves of frequency ω\omega, the differential operator is L=∇×∇×−[1+χ(x)]ω2\mathcal{L}=\nabla\times\nabla\times-[1+\chi(x)]\omega^2. In quantum control, one might seek an optimal pulse sequence χ(t)\chi(t) representing the time-dependent amplitude of a control Hamiltonian, Hc(t)H_c(t), relative to a background Hamiltonian, H0(t)H_0(t), in the Schrodinger operator, L=iddt−[H0(t)+χ(t)Hc(t)]\mathcal{L}=i\frac{d}{dt}-[H_0(t)+\chi(t)H_c(t)]. And similarly for elastic waves, with the Christoffel equation, and many other linear differential equations of physics. To simplify the exposition and clarify the complexity analysis, we will assume any sufficiently high-resolution numerical discretization into NN spatial/temporal/polarization/Hilbert-space/etc. degrees of freedom, in which case the variables ψ\psi and χ\chi are N×1N\times1 vectors and L\mathcal{L} is an N×NN\times N matrix (with suitable boundary conditions encoded). The task of scientists and engineers in disciplines from aerodynamic wing design to nanophotonics to quantum information theory is to solve optimization problems with forms similar to Eq. (1).

Physical design problems as QCQPs

Equation (1) is computationally prohibitive to solve for a global optimum because the differential-equation constraint is nonconvex in the variables ψ\psi and χ\chi. (It is “bilinear” in the pair of variables ψ\psi and χ\chi, but that is of little help in searching for global optima.) In this section, we show how to convert the differential-equation constraints to quadratic constraints, ultimately leading to the sparse-QCQP formulation of the design problem.

We consider the prototypical case in which there is a binary choice for the design variable over each designable DOF, denoted χ1\chi_1 and χ2\chi_2, such as, for example, designing a pattern of air holes in silicon, or a sequence of on/off pulses in quantum control. We further assume, for simplicity, that our design space has the full NN degrees of freedom shared by the response fields. Typically the number of degrees of freedom will be smaller than NN; for example, perfectly matched layers are not part of the designable region. The constraints associated with nondesignable regions are straightforward and described in detail in the SM, and do not change the analysis below. Our approach generalizes to different numbers of degrees of freedom as well as to multilevel design problems, as we discuss in the SM, but again these assumptions will clarify the key logic and analysis. It is simple to enumerate the design space: there are NN degrees of freedom, each of which can take one of two values, such that there are 2N2^N possible designs. The 2N2^N possible designs each have fields ψ\psi that must satisfy the NN differential-equation constraints of Eq. (1).

The crucial insight is as follows: at each spatial/temporal point ii in the design space, either L(χ1)ψ−ξ∣i=0\left.\mathrm{L}(\chi_1)\psi-\xi\right|_i=0 or L(χ2)ψ−ξ∣i=0\left.\mathrm{L}(\chi_2)\psi-\xi\right|_i=0. (The “∣i\left.\right|_i” symbol should be interpreted, for example, as selecting a single row of a finite-difference matrix, or as integrating against a single basis function in a finite element discretization.) Consider the scalar-field case, for which each expression L(χ1,2)ψ−ξ∣i\left.\mathrm{L}(\chi_{1,2})\psi-\xi\right|_i is a scalar expression. Then, enforcing a logical OR condition between two scalar values is exactly equivalent to forming a single constraint in which the two scalar expressions are multiplied together; in other words, enforcing (a==0)(a==0) OR (b==0)(b==0) is equivalent to enforcing ab==0ab==0. For the general vector-field case, the vector OR condition can be replaced by pairwise inner-product constraints. Each of these inner products is of the form:

[L(χ1)ψ−ξ]†Di[L(χ2)ψ−ξ]=0,(2)\left[\mathrm{L}(\chi_1)\psi-\xi\right]^\dagger D_i\left[\mathrm{L}(\chi_2)\psi-\xi\right]=0, \tag*{(2)}

where DiD_i is the matrix that encodes the evaluation of the two terms in square brackets associated with a particular susceptibility degree of freedom and †\dagger represents the adjoint (conjugate transpose) operation. For example, in a finite-difference scheme, DiD_i is a block-diagonal matrix (or any linear combination thereof) whose only nonzero elements occur at point ii in space/time, with nonzero off-diagonal elements only in polarization/Hilbert space. Enforcing Eq. (2) over all independent block-diagonal DiD_i matrices is equivalent to enforcing the logical-OR condition at all points in space/time, as intuitively justified above and rigorously proven in the SM. The number of independent constraints of the form of Eq. (2) scales linearly with NN, as one intuitively expects for NN degrees of freedom.

Clearly the constraints of Eq. (2) are necessarily satisfied by any solution of the original design problem, Eq. (1). Perhaps surprisingly, the constraints of Eq. (2) are also sufficient conditions for the design problem. Hence we can discard the original differential equation constraints, and specify a new, equivalent design problem:

max⁡ψ.f(ψ)s.t.[L(χ1)ψ−ξ]†Di[L(χ2)ψ−ξ]=0∀i.(3)\begin{aligned} \max_{\psi.}\quad& f(\psi)\\ \text{s.t.}\quad& \left[\mathrm{L}(\chi_1)\psi-\xi\right]^\dagger D_i\left[\mathrm{L}(\chi_2)\psi-\xi\right]=0\quad\forall i. \tag*{(3)} \end{aligned}

To see why the constraints of Eq. (3) are sufficient conditions, consider an optimal solution ψ\psi of Eq. (3). From ψ\psi, one can check every constraint ii to determine at each space/time point whether χ1\chi_1 or χ2\chi_2 is the optimal design variable at that point. The resulting pair of ψ\psi and χ\chi will then necessarily satisfy the constraint of Eq. (1), implying that any solution of Eq. (3) is a viable solution of Eq. (1). As the optimal solutions of each problem are within the other’s feasible set, and the objectives are the same, the optimal solutions must coincide. Hence, the two design problems have equivalent optima.

What is the intuition behind the quadratic constraints of Eq. (3)? They turn out to have a simple, general physical interpretation. Each constraint in Eq. (3) represents a complex-valued conservation law at each point in space/time of the designable domain (cf. SM for a derivation). In electromagnetism, they represent local conservation of real and reactive power flow. In quantum control, they represent local conservation of complex probability. And similarly for other physical systems. A close analog arises in circuit design. When one wants to find the steady-state response of a complex configuration of resistors, capacitors, and inductors, the first choice typically is not solving circuit differential equations. Instead, one solves Kirchhoff’s current and voltage laws, two conservation laws for every node of the system. The constraints of Eq. (3) are akin to generalized Kirchhoff’s laws for any linear-differential-equation-based design problem.

The design problem of Eq. (3) has a different mathematical structure from Eq. (1). First, in Eq. (3), the design variable χ\chi is no longer a degree of freedom. Instead, the 2N2^N possible design configurations are encoded in the O(N)O(N) quadratic constraints of Eq. (3). Now, the only degrees of freedom are in the field variable ψ\psi, and the constraints are all quadratic forms in ψ\psi. Objective functions f(ψ)f(\psi) of interest, such as power flow or momentum transfer in electromagnetism or state transfer, fidelity, and related objectives in quantum control, will also be quadratic (or linear) forms of ψ\psi. Hence, our new design problem is a quadratically constrained quadratic program, or QCQP.

Figure 1 schematically illustrates the change in viewpoint brought on by the transformation to a QCQP. We consider as an example the Helmholtz equation, in which wave speed can take values 1 (background) or 1/2 (patterned material), which corresponds to susceptibility values of χ2=1\chi_2 = 1 and χ1=3\chi_1 = 3, respectively. The domains depicted in Fig. 1 are 5 wavelengths in size (with half-wavelength perfectly matched layers surrounding them). Figure 1(a) shows the specification of a structure in space, which prescribes the precise form of the corresponding linear operator. From the structure-specific operator, one can compute the fields. This is a powerful simulation tool, but it inhibits optimization approaches beyond gradient descent (local structural perturbations). Figure 1(b) shows the QCQP perspective, in which quadratic constraints are formed that must be satisfied by all possible designs. Optimizing over fields that satisfy these constraints, for example via semidefinite-programming techniques, can lead to discovery of optimal designs.

Schematic comparison of the usual differential-equation approach and the QCQP approach

Figure 1. (a) The usual writing of a differential equation specifies different operator values at different space/time points according to the design variable (e.g. material susceptibility) χ\chi. One can specify a structure (top right, a material with χ=3\chi= 3 and approximately half-wavelength thickness, for a finite-difference discretization of the Helmholtz equation) and compute the corresponding field response (bottom right). (b) Our approach identifies quadratic constraints satisfied by all possible designs. Any field that satisfies these constraints (e.g. top right) will imply a corresponding design (bottom right, χ=3\chi= 3) that produces the field. If the field optimizes an objective of interest, then the corresponding structure will be an optimal design.

Many sparse QCQPs are nearly convex

The next question is whether the QCQP of Eq. (3) offers mathematical advantages over the original problem. QCQPs are generally NP hard [63, 64], just as the original problem is. (If this were not true, Eq. (3) would prove that P = NP.) Yet QCQPs arise across many areas of science and engineering, and there is well-developed machinery for exploiting their specific mathematical structure [65, 66, 67, 68] [15, 17]. Geometrically, a set of quadratic constraints represents the intersection points of hyperboloids and ellipsoids; direct optimization over such intersections requires combinatorial algorithms. However, one can “lift” the problem to a higher-dimensional space, where the quadratic constraints in the original variables become linear (and therefore convex) constraints in a new matrix variable. This process introduces two additional constraints: a (convex) positive-semidefinite matrix constraint, and a nonconvex constraint on the rank of the new matrix. In this new, higher-dimensional setting, the objective and all constraints are convex, except for the rank constraint. In essence, all of the nonconvexity of the problem is isolated into the single rank constraint. This offers two exciting possibilities. First, one can simply drop the rank constraint, leaving a convex problem whose efficiently computable solution will always represent a bound, or fundamental limit, on the problem of interest. Second, the sparsity of differential operators can in some cases provably lead to low-rank solutions of this relaxed, convex problem, suggesting that many physical design problems may be “nearly convex” in this high-dimensional space. Then one may be able to introduce a rank-penalizing regularization that leads to high-quality, high-performance optimal designs that are superior to those found by typical gradient-descent-based techniques. In this section we first introduce the general “lifting” procedure, then we describe our proposed convexity-related approach to fundamental limits and novel designs.

The QCQP of Eq. (3) can be expressed generally as:

max⁡ψψ†Aψ+Re⁡[α†ψ]such thatψ†Biψ+Re⁡[βi†ψ]+ci=0,(4)\begin{aligned} \max_{\psi}\quad& \psi^\dagger A\psi+ \operatorname{Re}\left[\alpha^\dagger\psi\right] \\ \text{such that}\quad& \psi^\dagger B_i\psi+ \operatorname{Re}\left[\beta_i^\dagger\psi\right] + c_i = 0, \tag*{(4)} \end{aligned}

where ii iterates over all constraints (space/time/polarization/etc.), AA and α\alpha are defined by the objective of interest, and equations are kept real-valued by separating the real and imaginary parts of the constraints of Eq. (3). “Lifting” is now well-known and well-understood (cf. Ref. [67] is one review); we include here a brief summary. The objective and each constraint of Eq. (4) are scalars, and one can trivially take the matrix trace of each. A trace is invariant under cyclic permutations; for example, Tr⁡(ψ†Aψ)=Tr⁡(Aψψ†)\operatorname{Tr}(\psi^\dagger A\psi) = \operatorname{Tr}(A\psi\psi^\dagger). If we denote a new matrix variable X=ψψ†X = \psi\psi^\dagger, the quadratic form ψ†Aψ\psi^\dagger A\psi becomes a linear form, Tr⁡(AX)\operatorname{Tr}(AX), in the new, higher-dimensional matrix variable XX. The linear forms in the original equation are straightforward to handle with conventional methods [67], ultimately leading to modified matrices AA and BiB_i whose expressions are explicitly given in the SM. However, the entries of the matrix variable XX are not free to take on any values; because XX represents the outer product of a vector with itself, it must have rank 1 and be positive semidefinite. Following these steps, we can rewrite the QCQP of Eq. (3) and Eq. (4) as:

max⁡XTr⁡(AX)such thatTr⁡(BiX)=biX≥0rank⁡(X)=1.(5)\begin{aligned} \max_{X}\quad&\operatorname{Tr}(AX)\\ \text{such that}\quad&\operatorname{Tr}(B_iX)=b_i\\ &X\ge0\\ &\operatorname{rank}(X)=1. \tag*{(5)} \end{aligned}

The trace-based objective and constraints are linear in XX, while the positive-semidefinite requirement is a convex cone constraint. Whereas each differential-equation-based constraint of the original problem was nonconvex, our new, equivalent problem in Eq. (5) has a convex objective and many convex constraints; the only nonconvex part of the problem is the rank-one constraint.

The observation that the rank-1 constraint is the only nonconvex part of the problem offers insights into “how convex” the design problem is in the lifted, higher-dimensional space. If we just drop the rank-1 constraint, the resulting problem, a semidefinite program (SDP), is convex. The question, then, is how large of a penalty one pays by dropping the rank-1 constraint and solving the SDP. For the famous NP-hard “max-cut” problem, in which one seeks to identify the maximum number of edges in a graph partition, an SDP relaxation is guaranteed to have a solution that is within 12% of the global optimum [66]. For most examples of lifting there is no such known bound; instead, the rank of the solution of the SDP is used as a measure of how convex the problem is. For example, if the rank of the SDP solution is quite large, then the solutions of the SDP and the original QCQP may be wildly different. In that case, the rank-1 constraint is clearly important for finding the correct solution, and it is unclear if a convex problem can lead one close to the optimal solution. By contrast, if the rank of the convex problem is small, then one can imagine making slight tweaks to the problem (e.g. adding a regularization or penalty function) to find a rank-1 solution of a related convex problem, which may be a high-quality solution of the original problem. (We show a numerical example of this type below.) Hence, the rank of the relaxed problem, the SDP, is an indication of how nonconvex the design problem is.

Strikingly, in certain physical scenarios we can use the sparsity of differential operators to prove that the rank of the computed solution of the relaxed problem is “small”; in particular, that the rank of the solution is bounded above by a constant that is independent of the long dimension of the problem. Bounds on the solutions of SDPs are common in problems with sparse

matrices [69], which we use in tandem with the differential operators that comprise AA and BiB_i of Eq. (5). The matrix entries of the variable XX form a set of vertices, and the nonzero entries of the objective and data matrices, AA and BiB_i, comprise edges of an undirected graph on those vertices. If the graph is chordal, then the size of the largest clique is known to be a bound on the maximum rank of a solution of the SDP [69]. (A brief review of the relevant graph-theoretic terms is provided in the SM.) If the graph is not chordal, then a bound can be found from any chordal extension of the graph. As we show in the SM, for any linear-differential-equation-based physical design problem that has one “long” dimension (e.g. waveguides, metasurfaces with translational or rotational symmetry, quantum control problems with time as the long dimension), the clique number is bounded above by a problem-size-independent constant. These physical design problems are provably “close” to convex optimization problems.

A convex optimization paradigm for physical design

In this section, we formulate two convex-optimization-related approaches to the design problem of Eq. (5). First, we define the SDP discussed above, with the rank-1 constraint dropped from the problem, which leads to bounds on any design problem of interest. Our second approach is to augment the SDP with a penalty term (typically convex) that encourages very-low-rank or even rank-1 solutions to the semidefinite program. This offers a new approach to designing physical structures, which comes with the possibility of avoiding many low-quality local optima.

Our first formulation simply drops the rank-1 constraint from Eq. (5), leaving the SDP:

max⁡XTr⁡(AX)such thatTr⁡(BiX)=biX≥0.(6)\begin{aligned} \max_{X}\quad&\operatorname{Tr}(AX)\\ \text{such that}\quad&\operatorname{Tr}(B_iX)=b_i\\ &X\ge0. \tag*{(6)} \end{aligned}

Equation (6) is a relaxation of the original physical design problem, and as a convex optimization problem, its global optima can be found efficiently via interior-point methods [14]. A key feature of the solution is that it will always represent an upper (lower) bound to the objective to be maximized (minimized). This results directly from the dropping of the rank-one constraint; alternatively, it is known that Eq. (6) is equivalent to the dual problem of Eq. (5), and dual-problem solutions always bound their “primal” counterparts. A key feature of Eq. (6) is that it can be decomposed into smaller, coupled sub-problems when the matrices AA and BiB_i are sparse. From Eq. (3), one can see that the sparsity of the matrices BiB_i is determined primarily by LiL_i, the differential operator, which is typically (e.g. in the case of the Laplacian) quite sparse. Fig. 2 demonstrates the sparsity patterns of the product L†L\mathbf{L}^{\dagger}\mathbf{L} that arises in Eq. (6), for the differential operators of electromagnetism and quantum mechanics. Significant dimensionality reduction requires a strong form of sparsity: not only many zero entries, but also chordal sparsity. The chordal completion of the L†L\mathbf{L}^{\dagger}\mathbf{L} operator is depicted in green in Fig. 2(b); the sparsity of this matrix determines the extent to which the SDP can be compressed (losslessly). Moreover, a sparse chordal completion leads to small maximal clique sizes, as depicted in Fig. 2(c), in stark contrast to SDPs formed from dense matrices. These maximal clique sizes are bounded above by a constant unrelated to the long dimension of the problem, suggesting that the SDP solutions may be informative for many design problems, which we support with numerical evidence in the next section.

Chordal decomposition and clique sizes for differential-equation-based design problems

Figure 2. (a) Differential equations on any domain (black grid) have a sparsity pattern that can be represented in an undirected graph (vertices 0–8). The chordal completion of that graph can be decomposed into “cliques,” smaller domains on which the problem can be defined. (b) The rank of the corresponding SDP, a measure of the nonconvexity of the design problem, is bounded above by the largest clique size. For dense matrices (as arise in integral equations), this is simply proportional to the size of the problem (red). By contrast, the sparsity of differential operators leads to maximum clique sizes that are bounded above by a constant unrelated to the “long” dimension of a physical-design problem. (C) Chordal completions of the sparsity patterns arising in various differential-equation-based design problems in electromagnetism and quantum information theory.

The second approach is to augment the semidefinite program of Eq. (6) to promote solution matrices with ranks close to or equal to one. While the rank operator itself is a nonconvex quantity, there are well-known proxy quantities that promote low rank, such as the matrix trace, which is known to be the best convex lower bound on rank for matrices with constrained singular values [70]. In feasibility problems, as occur, for example, in ptychographic imaging, one replaces the rank-1 constraint with an objective that promotes low rank [15]. For design problems, in which there is already an objective of interest, we can add a regularizer, i.e., a penalty for high-rank solutions, to the original objective. If we denote by R(X)\mathcal{R}(\mathbf{X}) a functional proxy for the rank of a matrix X\mathbf{X}, then we can modify Eq. (6) to form the augmented program,

max⁡XTr⁡(AX)−γR(X)such thatTr⁡(BiX)=biX≥0,(7)\begin{aligned} \max_{\mathbf{X}}\quad& \operatorname{Tr}(\mathbf{A}\mathbf{X})-\gamma\mathcal{R}(\mathbf{X})\\ \text{such that}\quad& \operatorname{Tr}(\mathbf{B}_i\mathbf{X})=b_i\\ & \mathbf{X}\geq0, \tag*{(7)} \end{aligned}

where γ\gamma can be adjusted to balance the original objective with the goal of a low-rank solution. The key idea is simple: if Eq. (7) has a rank-one solution (thanks to the regularization), then one has found the global optimum of a QCQP that is not exactly equivalent to the original QCQP of Eq. (5), but is similar to it. (The smaller γ\gamma is, the more similar the two problems are.) Intuitively, the global optimum of a slightly modified problem is likely to be a high-quality solution of the original problem, an idea that has been supported in previous numerical experiments across optimization theory, ptychography, and optimal power flow [66, 67, 68, 71] [6, 15], and is further supported by our results in the next section.

Equations (5–7) are key results of this paper. Equation (5) is the culmination of an exact transformation of a wide range of physical design problems, with objectives subject to differential-equation constraints, into sparse QCQPs. This connection to a common mathematical structure leads to Eqs. (6,7), the first of which is a convex problem that is guaranteed to identify bounds for the problem of interest, and the second of which offers a new approach to physical design, with the possibility for circumventing low-quality local optima. In the next two sections, we perform numerical experiments that demonstrate the power of these transformations.

Large-scale computational bounds

In this section, we demonstrate the utility of our sparse-QCQP-based SDP, of Eq. (6), for enabling computational bounds of large-scale systems for which such analysis is impossible with the current state-of-the-art methods. “Metasurfaces,” in which one patterns a wavelength-scale-thickness material to achieve high-performance optics functionality in compact form factors, offer a compelling example [72, 73, 74, 75, 76] [1, 2]. A metalens is a metasurface that focuses light to a single focal spot, and one typically wants a maximally efficient metalens with a diameter significantly larger than the free-space optical wavelength. In Figure 3, we consider a two-dimensional metasurface with diameter dd, thickness tt, refractive index n=2n = \sqrt{2}, and numerical aperture NA=0.9\mathrm{NA} = 0.9, and pose a fundamental question: what is the maximum possible efficiency any designable pattern could achieve? To answer this question, we formulate the Maxwell-constrained design problem of Eq. (1), transform the problem to the sparse QCQP of Eq. (5), and relax the problem to the SDP of Eq. (6). We exploit the sparsity of the differential operators using the clique-decomposition technique outlined in Fig. 2, with the open-source software package SparseCoLO [77], to dramatically reduce the size of the SDP and enable computation of large-scale bounds. Figure 3(b,c) show bounds on the field intensities as a function of metalens diameter. One can see that the maximum field intensity depends sensitively on the metasurface thickness, and is well below the “unitary bound” arising from imposing unitarity constraints on the scattering matrix (cf. SM). A natural question is whether these bounds are achievable, and we include in Figure 3(b) four notable data points (black markers): designs taken from the first singular vectors of the SDP solutions can achieve real performance levels almost exactly coinciding with the bounds themselves; the designs found by this SDP procedure are shown in the blue inset patterns.

Metalens designs and computational bounds

Figure 3. (a) Metalenses use nanophotonic patterning to focus incoming light. As a function of the diameter dd and thickness tt of the metalens, bounds on the maximal focal-point field intensity can be computed, shown in (b), using the SDP of Eq. (6). If the solution is low rank, as for the red curve, the solution of the SDP can be used to find designs (field intensity in black markers, structure in insets) that nearly achieve the global bound. (c) Conservation-law bounds can be much smaller than simpler approaches, such as unitarity. (d) The differential form of the Maxwell equations in the SDP leads to much linear-in-diameter scaling of computation times, enabling bounds for diameters up to 100 wavelengths.

Crucially, the sparsity enables computation at very large scale sizes. Whereas integral-equation formulations of QCQP bounds, as in Refs. [54, 60], require computational times that scale with the fourth power of the metasurface diameter, the differential-equation-based bounds scale linearly, enabling bounds for devices with diameters up to 100 free-space wavelengths in size.

A new approach to design

Having shown the success of the SDP approach to large-scale bounds, we now turn to the question of whether our lifted-QCQP framework can lead to a new design approach altogether. The idea is to use the regularized form of the lifted QCQP, in Eq. (7), to promote a rank-one solution of the lifted problem, which will be a global solution of a closely related QCQP. To test this approach, we consider a canonical example that showcases the difficulty of physical design in the presence of wave-interference effects: a multilayer nanophotonic film, with waves scattering back and forth between the many possible layers. We consider a maximum-reflection problem as shown in Figure 4, with a design region of multiple (in this case, four) free-space wavelengths, to achieve perfect reflection (reflection magnitude 1) with a specific reflection phase (arbitrarily chosen to be −0.3π-0.3\pi). We consider a slightly lossy material (with refractive index n=2.3+0.03in = 2.3 + 0.03i, with a loss tangent typical of lossy materials in the visible); otherwise, any random collection of enough scatterers could generate perfect reflection (as in white paint). First, we run 100 full optimizations of “inverse design” [23, 26]; we use a typical implementation of inverse design, with the widths of the films as the degrees of freedom, and adjoint-based simulations to speed up the gradient calculations. We use a standard quasi-Newton “interior-point” algorithm of Matlab, with default convergence criteria, and we start with about half of the region as air and half as the material, with 80 layers whose widths are randomly chosen between 0 and 100 nm. (With significantly fewer than 80 layers, the optimizations tend to fall into even more low-quality local optima, while going well above 80 imposes a significant computational burden. The choice of 80 optimizes the tradeoffs between these competing effects.) Results from the 100 optimization runs are shown in Figure 4(b), with the bulk of the optimizations converging to designs with reflectivity between 40–50%, and the very best single design achieving only 88% reflectivity. Ten designs—eight random, alongside the two best—are shown on the left-hand side of Figure 4(b), showing the many different locally optimal designs that are discovered. Clearly one can see that gradient-based algorithms are prone to converging to local optima, especially for a problem with significant wave reflections.

Schematic, inverse designs, lifted-QCQP optimization, and optimization landscape

Figure 4. (a) Schematic of a simple design problem with significant wave-interference effects: achieving large reflection, with a specific phase, from a multilayer stack of a slightly lossy material and an air background. (b) Inverse designs using interior-point methods to use adjoint-based gradient information can easily be trapped in local optima; the bulk of the optimization runs converge to 40–50% locally optimal efficiencies, while the best run, out of 100, finds a design with 88% reflectivity. (c,d) A single, iterative optimization using the augmented-SDP of Eq. (7) leads to a design (design widths in SM) that achieves 96.9% efficiency, far outperforming even the best of the 100 inverse-design runs.

To tackle this problem with an augmented SDP, per Eq. (7), we adapted an algorithm developed in Ref. [78] for QCQPs that arise in optimal power flow applications. The rank of a matrix can be written as a summation of step functions applied to the singular values of the matrix; in Ref. [78], they use a smooth approximation for the step function to construct the rank-penalization function R(X)R(X). This function is well-suited for a majorization–minimization (MM) algorithm that is tailored to concave objectives subject to a convex constraint set. The MM algorithm applied as in Ref. [78] iteratively solves semidefinite programs with rank-penalized objectives until a locally optimal rank-one solution is found, at which point a hyperparameter can be tweaked if one wants a certificate of global optimality.

hyperparameter can be tweaked if one wants a certificate of global optimality. We find the latter step unnecessary, with a single (iterative) local optimum repeatedly showing quite good performance. Running the algorithm on the lossy-material high-reflection optimization discussed above leads to the result is shown in Figure 4(c): a design that achieves 96.9% reflectivity (and the correct phase), in a single optimization run, without any fine-grained hyperparameter tuning. One can see the difference between this approach and the inverse design approach in Figure 4(d), where the 100 initial reflectivities and locally optimal inverse-design reflectivities are shown in gray and orange, respectively, and the single lifted-QCQP-based optimization is shown in the blue marker. Clearly, the lifted-QCQP approach leads to a better design, with a more robust design process. One cannot directly compare the number of simulations used in each approach, as the lifted-QCQP optimization does not do any “simulations” at each iteration, but the typical inverse-design optimization required 21 seconds on a 2021 Macbook Pro, for a total of 35 minutes for the 100 optimization runs, with a maximum reflectivity of 88%. The lifted-QCQP optimization took 5 minutes on the same computer, leading to a design with 96.9% reflectivity. (The reported time is the full runtime, with all subroutines and iterations included.) Moreover, the design discovered in the lifted-QCQP approach appears to be a quite plausible global optimum for this problem. Having seen the design, one can explain the physics of its operation: the spacings between consecutive films are nearly exactly half a wavelength, to create constructive interference in the reflected wave. Moreover, the films show a thickness gradation, which is sensible given the lossiness of the material: the first layers are likely to interact with many scattered waves, and should be thin to avoid material losses, while the rear layers simply need to reflect the waves at any cost and can be thicker as a result. (The thicker first layer likely sets the correct phase.) Hence this result shows not only very good performance, but is suggestive of discovering a near-globally-optimal design, as anticipated in the theoretical derivations of Sec. I C.

Discussion and Conclusion

In this paper, we have connected design problems subject to the dynamics of the linear differential equations of physics to modern convex optimization theory. By rewriting these design problems as conservation laws defined by differential operators, we identify a unique structure pervasive across physical design problems: they can be transformed to sparse QCQPs. Sparse QCQPs can be lifted to higher dimensions, where their SDP relaxations offer a general framework for large-scale computational bounds. Tantalizingly, regularizing the SDP can lead to efficient techniques for identify designs that may often approach the global optima, as we demonstrated for an electromagnetic design problem subject to significant amounts of speckle and wave-interference effects.

Many areas of science and engineering, including optimal power flow [68, 71], ptychography [15, 16], VLSI design and Ising problems [79], and more, have benefited from connections to semidefinite programming going back two decades [67]. It had seemed that wave-physics and related physical design problems simply had unfavorable mathematical structure, where such techniques would not work, but our approach shows that even wave-based design problems can fit into this paradigm. One concern might be the significant computational cost of standard SDP solvers—they have polynomial run-times, but the polynomial is typically 3.5 or 4 (i.e., runtime scales as N3.5N^{3.5} or N4N^4 for NN degrees of freedom), which prevents the application of SDPs to large-scale optimization problems [67]. Auspiciously, there has been significant recent progress in computational algorithms for semidefinite programming [80, 81, 82, 83] [16]; in one recent work [16], SDPs with 10710^7 designable degrees of freedom, corresponding to 101410^{14} matrix variables, were solved.

Moreover, whereas we used the chordal sparsity in tandem with clique decompositions that are possible when one dimension of the problem is significantly larger than any others, newer SDP techniques such as those of [16] can exploit broader sparsity characteristics, beyond just chordal sparsity. These improvements may be readily adaptable to our physical-design SDPs.

Looking forward, there is ample opportunity to apply this technique broadly across many applications in photonics, quantum control, elasticity, and more. In addition to the scalability improvements enabled by the differential-equation formulation, discussed above, another feature of our approach is that it can work seamlessly with the many open-source and commercial differential-equation solvers in widespread use. As an example, in the SM, we show that one can create an SDP directly from the governing matrix equations created by Comsol [84] and successfully identify the correct bounds. This suggests the possibility for our approach to become widely adopted across common differential-equation solvers.

An interesting contrast between our approach versus “inverse design” and deep-learning approaches is that the latter are “structure-blind”: aside from changes in the oracle functions to be called, the algorithms are not meaningfully modified for different design problems (linear, nonlinear, chaotic, etc.). Our approach specifically applies to physical design problems with bilinear structure in the field and geometric degrees of freedom (which are quite widespread), and cannot be generically applied to any problem. This is consistent with the “no free lunch” theorem [85]: there cannot be a single optimization method that is superior to others on all optimization problems. Our results suggest that a bespoke approach, with algorithms tailored to the underlying mathematical structure of the design problem of interest, may lead to a suite of design approaches that are superior to the structure-blind algorithms used today.

Acknowledgments

We thank Javad Lavaei and Somayeh Sojoudi for helpful discussions regarding sparse-QCQP formulations of optimal power flow. This work was supported by the Army Research Office under Grant No. W911NF-19-1-0279 and by the Air Force Office of Scientific Research under Grant No. FA9550-22-1-0393.

Supplementary Materials: Many Physical Design Problems are Sparse QCQPs

Shai Gertler; Zeyu Kuang; Colin Christie; Owen D. Miller

Detailed Constraint-Formulation Methodology

In this section, we provide further details on the form of the quadratic constraints introduced in the main text. We start with the differential equation

L(χ)ψ−ξ=0.(8)\mathsf{L}(\chi)\psi-\xi=0. \tag*{(8)}

We will assume a discretization for which there are NN designable points in space/time, there are MM non-designable points in space/time (e.g. PML regions, background materials, etc.), and that there are PP vector (polarization, Hilbert-space, etc.) degrees of freedom at each point in space/time. Then ψ\psi and ξ\xi both have sizes (N+M)P×1(N+M)P \times1, and L\mathsf{L} is a matrix of size (N+M)P×(N+M)P(N+M)P \times(N+M)P. We will take the typical case in which the control field χ\chi can be controlled at each designable space/time point, but does not have independent levers of control along the polarization/Hilbert/etc. axis. (For example, we are assuming one cannot independently control the material properties of each polarization at a given point in space in a nanophotonics problem. Such control in fact slightly reduces the size of the ultimate QCQPs, and slightly simplifies the analysis below.)

First, let us tackle what happens at a designable point in the domain. If we denote this point ii, then

(L(χ1,2)ψ−ξ)∣i(9)\left.(\mathsf{L}(\chi_{1,2})\psi-\xi)\right|_i \tag*{(9)}

is a P×1P \times1 vector for each of χ1\chi_1 and χ2\chi_2. We want to enforce the condition that

either (L(χ1)ψ−ξ)∣i=0 or (L(χ2)ψ−ξ)∣i=0,(10)\text{either }\left.(\mathsf{L}(\chi_1)\psi-\xi)\right|_i=0\text{ or }\left.(\mathsf{L}(\chi_2)\psi-\xi)\right|_i=0, \tag*{(10)}

where the zeros are the right-hand sides are the zero vectors. Consider two vectors aa and bb, both of size P×1P \times1, for which we want to enforce the condition that either one of the vectors is the zero vector. How can we do that? The key is to enforce

aj∗bk=0,∀j,k,(11)a_j^*b_k=0,\qquad\forall j,k, \tag*{(11)}

i.e., to force each pairwise inner product to be zero. This expression says that for each j,kj,k, one of the two entries must be zero. (Or both, but that is typically forbidden by the form of L(χ)\mathsf{L}(\chi). ) The only way for this condition to be met for all jj and kk is for all of the entries of one of the vectors to be zero. This can be proven by contradiction. Suppose both vectors are nonzero—that is, each have at least one element that is not zero—and that they satisfy Eq. (4). Then choose jj and kk to be the indices of nonzero elements in each vector. Their product is not zero, contradicting the requirement that Eq. (4) be satisfied. Thus we see that Eq. (4) requires (at least) one of the vectors to be zero, which is exactly the either–or condition that we desire.

We can alternatively write the condition of Eq. (4) in matrix form,

a†Djkb=0,∀j,k,(12)a^\dagger\mathsf{D}_{jk}b=0,\qquad\forall j,k, \tag*{(12)}

where Djk\mathsf{D}_{jk} is a P×PP \times P matrix with all zeros except a single entry of 1 in its j,kj,k element. Now let us return to the differential equations of above. We can just directly substitute (L(χ1)ψ−ξ)∣i\left.(\mathsf{L}(\chi_1)\psi-\xi)\right|_i for aa, and similarly but with χ2\chi_2 for bb, to get

(L(χ1)ψ−ξ)†∣iDjk(L(χ2)ψ−ξ)∣i=0.(13)\left.(\mathsf{L}(\chi_1)\psi-\xi)^\dagger\right|_i\mathsf{D}_{jk}\left.(\mathsf{L}(\chi_2)\psi-\xi)\right|_i=0. \tag*{(13)}

Finally, we clean up the notation a bit. In Eq. (6), ii is an index for the space/time point, while jj and kk are indices in the polarization/Hilbert space. We can wrap all of these into a single index ii that iterates over all space/time points and all polarization/Hilbert-space combinations; we can also enlarge D\mathsf{D} to be a fully (N+M)P×(N+M)P(N+M)P \times(N+M)P matrix (instead of smaller P×PP \times P matrices iterated NN times), now just with all entries of the larger matrix being zero except at single 11 at the iith entry. Then we can drop the evaluation of the vectors at ii (since multiplication by the entire D\mathsf{D} matrix effectively does this already), and we can write Eq. (6) in exactly the same form as expressed in the main text,

[L(χ1)ψ−ξ]†Di[L(χ2)ψ−ξ]=0.(14)[\mathsf{L}(\chi_1)\psi-\xi]^\dagger\mathsf{D}_i[\mathsf{L}(\chi_2)\psi-\xi]=0. \tag*{(14)}

Next, we tackle the non-designable points in the design space. At each of those points, there are not two possibilities for χ\chi, but instead only a single one—whatever the background material is at that point in the domain. Hence, we enforce MPMP linear constraints of the form

[L(χ)ψ−ξ]∣i=0.(15)\left.[\mathsf{L}(\chi)\psi-\xi]\right|_i=0. \tag*{(15)}

However, once the problem is lifted and relaxed in a higher-dimensional space, it is not clear that these constraints will be binding, and indeed it has been found quite useful for some QCQPs to add seemingly redundant constraints to their formulation; those constraints are not redundant in the lifted, relaxed space [1]. We find it helpful to add MP2MP^{2} quadratic forms exactly equivalent to Eq. (7) at each nondesignable point, except that now both terms have χi\chi_i in them:

[L(χi)ψ−ξ]†Di[L(χi)ψ−ξ]=0.(16)\left[\mathcal{L}(\chi_i)\psi-\xi\right]^{\dagger}D_i\left[\mathcal{L}(\chi_i)\psi-\xi\right]=0. \tag*{(16)}

The constraints of Eqs. (7–(16) form all of the constraints of the system. In total, there are (N+M)P2(N+M)P^{2} quadratic constraints, and MPMP linear constraints.

What if one has multilevel level controls? If there were three possible control-field values, χ1\chi_1, χ2\chi_2, and χ3\chi_3, then the natural analog of the approach above is to multiply each of the three expressions, L(χi)ψ−ξ\mathcal{L}(\chi_i)\psi-\xi, together, to form a single constraint, which would then be a third-order polynomial in ψ\psi. More generally, for NN possible control-field values, one would form NNth-order polynomial constraints by this approach. It is well-known that optimization problems with polynomial objectives and polynomial constraints are a subclass of QCQPs—cf. Sec. 2.1 of Ref. [2]. The key idea is the extra variables can be introduced to reduce the order of the problem, at the expense of additional constraints. For example, if a constraint is y3=0y^{3}=0, one equivalently enforce xy=0xy=0 and x=y2x=y^{2}; in this example, two second-order (at most) constraints are equivalent to the single third-order constraint.

Interpreting the quadratic constraints as conservation laws

In this section, we justify our statement that a constraint of the form

[L(χ1)ψ−ξ]†Di[L(χ2)ψ−ξ]=0(17)\left[\mathcal{L}(\chi_1)\psi-\xi\right]^{\dagger}D_i\left[\mathcal{L}(\chi_2)\psi-\xi\right]=0 \tag*{(17)}

represents a conservation law. To do so, we first go back to the continuous representation, in which L\mathcal{L} is an operator and ψ\psi is a vector field, and rewrite Eq. (17) as an overlap integral. The matrix DiD_i in Eq. (17) has a single nonzero entry; its purpose is to isolate a single space/time point and specific polarizations (Hilbert-space indices) for the two equations. A similar isolation of specific space/time/polarization/etc. locations can be achieved in continuous space by taking an inner product with a function viv_i that encodes the desired localization. Hence we can write

⟨L(χ1)ψ−ξ,L(χ2)ψ−ξ⟩vi=0,(18)\left\langle\mathcal{L}(\chi_1)\psi-\xi,\mathcal{L}(\chi_2)\psi-\xi\right\rangle_{v_i}=0, \tag*{(18)}

where ⟨x,y⟩v=∫x†vy\langle x,y\rangle_{v}=\int x^{\dagger}v y, and †\dagger denotes the adjoint operator. To simplify notation below, we will assume χ2\chi_2 is always zero, and rewrite χ1\chi_1 as χc\chi_c, as the “background” control field can always be shifted to make this true, such that the quadratic constraint is:

⟨L(χc)ψ−ξ,L(0)ψ−ξ⟩vi=0.(19)\left\langle\mathcal{L}(\chi_c)\psi-\xi,\mathcal{L}(0)\psi-\xi\right\rangle_{v_i}=0. \tag*{(19)}

In the following subsections, we use the explicit forms of L(χ)\mathcal{L}(\chi) in electromagnetism and quantum control to show that Eq. (19) can be interpreted as a conservation law.

Electromagnetic design

We consider Maxwell’s equation describing a monochromatic field at frequency ω\omega in a nonmagnetic material (i.e., the relative permeability is μr=1\mu_r=1 everywhere in space). The electric field E(x)\mathbf{E}(\mathbf{x}) can be written as

[∇×∇×−(1+χ(x))ω2]E(x)=iωJ(x).(20)\left[\nabla\times\nabla\times-(1+\chi(\mathbf{x}))\omega^{2}\right]\mathbf{E}(\mathbf{x})=i\omega\mathbf{J}(\mathbf{x}). \tag*{(20)}

where J(x)\mathbf{J}(\mathbf{x}) are source currents, χ\chi is the (designable) susceptibility, and we use dimensionless units where the vacuum permittivity and permeability are both 1. In line with the discussion above we take χ\chi to be allowed two values, 0 or χc\chi_c. Then,

L(χc)=∇×∇×−(1+χc)ω2.(21)\mathcal{L}(\chi_c)=\nabla\times\nabla\times-(1+\chi_c)\omega^{2}. \tag*{(21)}

To simplify our notation, we will define a background-L\mathcal{L} operator,

L0=∇×∇×−ω2,(22)\mathcal{L}_0=\nabla\times\nabla\times-\omega^{2}, \tag*{(22)}

so that L(χc)=L0−χcω2\mathbb{L}(\chi_c)=\mathbb{L}_0-\chi_c\omega^2. Then Eq. (19) can be written:

⟨L0E−iωJ,L0E−ω2χcE−iωJ⟩vi=0.(23)\left\langle\mathbb{L}_0\mathbf{E}-i\omega\mathbf{J},\mathbb{L}_0\mathbf{E}-\omega^2\chi_c\mathbf{E}-i\omega\mathbf{J}\right\rangle_{v_i}=0. \tag*{(23)}

Multiplying by a factor χc−1/ω2\chi_c^{-1}/\omega^2 and rearranging leaves us with the constraint:

⟨(L0E−iωJ),χc−1ω2(L0E−iωJ)⟩vi−⟨L0E,E⟩vi−iω⟨J,E⟩vi=0,i=1,2,3…(24)\left\langle\left(\mathbb{L}_0\mathbf{E}-i\omega\mathbf{J}\right),\frac{\chi_c^{-1}}{\omega^2}\left(\mathbb{L}_0\mathbf{E}-i\omega\mathbf{J}\right)\right\rangle_{v_i}-\left\langle\mathbb{L}_0\mathbf{E},\mathbf{E}\right\rangle_{v_i}-i\omega\left\langle\mathbf{J},\mathbf{E}\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(24)}

To see the equivalence of this form to a power conservation law, we introduce the “polarization density”

P=χE=1ω2(∇×∇×−ω2)E−iωJ.(25)\mathbf{P}=\chi\mathbf{E}=\frac{1}{\omega^2}\left(\nabla\times\nabla\times-\omega^2\right)\mathbf{E}-i\omega\mathbf{J}. \tag*{(25)}

Using this definition in the constraint we have derived in Eq. (24) we have

ω2⟨P,χc−1P⟩vi−⟨∇×∇×E,E⟩vi+ω2⟨E,E⟩vi−iω⟨J,E⟩vi=0,i=1,2,3…(26)\omega^2\left\langle\mathbf{P},\chi_c^{-1}\mathbf{P}\right\rangle_{v_i}-\left\langle\nabla\times\nabla\times\mathbf{E},\mathbf{E}\right\rangle_{v_i}+\omega^2\left\langle\mathbf{E},\mathbf{E}\right\rangle_{v_i}-i\omega\left\langle\mathbf{J},\mathbf{E}\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(26)}

We can further simplify the second term; using Maxwell’s equation ∇×E=iωH\nabla\times\mathbf{E}=i\omega\mathbf{H} and the vector identity A⋅(∇×B)=B⋅(∇×A)−∇⋅(A×B)\mathbf{A}\cdot(\nabla\times\mathbf{B})=\mathbf{B}\cdot(\nabla\times\mathbf{A})-\nabla\cdot(\mathbf{A}\times\mathbf{B}), we have

⟨∇×∇×E,E⟩=−iω⟨∇×H,E⟩=−iω⟨H,∇×E⟩+iω∮dV ∇⋅(E×H∗)=ω2⟨H,H⟩+iω∮dA (E×H∗)⋅n.(27)\begin{aligned} \left\langle\nabla\times\nabla\times\mathbf{E},\mathbf{E}\right\rangle &=-i\omega\left\langle\nabla\times\mathbf{H},\mathbf{E}\right\rangle\\ &=-i\omega\left\langle\mathbf{H},\nabla\times\mathbf{E}\right\rangle+i\omega\oint dV\,\nabla\cdot(\mathbf{E}\times\mathbf{H}^{*})\\ &=\omega^2\left\langle\mathbf{H},\mathbf{H}\right\rangle+i\omega\oint dA\,(\mathbf{E}\times\mathbf{H}^{*})\cdot\mathbf{n}. \tag*{(27)} \end{aligned}

where in the last step we used the divergence theorem to express the second term as a surface integral. Next, we turn to the first term in Eq. (26); at points where χ(x)=χc\chi(x)=\chi_c we know that E=χc−1P\mathbf{E}=\chi_c^{-1}\mathbf{P}. This is not true in regions where χ(x)=0\chi(x)=0, however, in these regions P=0\mathbf{P}=0. Hence, we can rewrite the inner product as ⟨P,χc−1P⟩=⟨P,E⟩\left\langle\mathbf{P},\chi_c^{-1}\mathbf{P}\right\rangle=\left\langle\mathbf{P},\mathbf{E}\right\rangle. All together, this leaves us with

iω⟨P,E⟩vi+iω⟨E,E⟩vi−iω⟨H,H⟩vi+∮dA (E×H∗)⋅n+⟨J,E⟩vi=0,i=1,2,3…(28)i\omega\left\langle\mathbf{P},\mathbf{E}\right\rangle_{v_i}+i\omega\left\langle\mathbf{E},\mathbf{E}\right\rangle_{v_i}-i\omega\left\langle\mathbf{H},\mathbf{H}\right\rangle_{v_i}+\oint dA\,(\mathbf{E}\times\mathbf{H}^{*})\cdot\mathbf{n}+\left\langle\mathbf{J},\mathbf{E}\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(28)}

which is precisely the complex Poynting theorem for the case of non-magnetic material [3].

Six-vector notation

We can write a general six-vector form for Maxwell’s equations; denoting the fields ψ(x)=(E H)T\boldsymbol{\psi}(x)=(\mathbf{E}\ \mathbf{H})^{T} and the current sources ξ(x)=(J K)T\boldsymbol{\xi}(x)=(\mathbf{J}\ \mathbf{K})^{T}, we have

\begin{pmatrix}0&\nabla\times\\-\nabla\times&0\end{pmatrix}\boldsymbol{\psi}+i\omega\boldsymbol{\psi}+i\omega\chi\boldsymbol{\psi}=\boldsymbol{\xi}, \tag*{(29)}\end{pmatrix}

where χ\chi is the material susceptibility tensor, which can have both electric and magnetic (and magnetoelectric) components. We assume the susceptibility tensor can take one of two values at each point in space χ(x)∈{0,χc}\chi(x)\in\{0,\chi_c\}, and we can define the operator

L0=(0∇×−∇×0)+iωI,(30)\mathbb{L}_0=\begin{pmatrix}0&\nabla\times\\-\nabla\times&0\end{pmatrix}+i\omega\mathbb{I}, \tag*{(30)}

such that we have the constraint

⟨(L0ψ−ξ),χc−1iω(L0ψ−ξ)⟩vi+⟨L0ψ,ψ⟩vi−⟨ξ,ψ⟩vi=0,i=1,2,3…(31)\left\langle\left(\mathbb{L}_0\boldsymbol{\psi}-\boldsymbol{\xi}\right),\frac{\chi_c^{-1}}{i\omega}\left(\mathbb{L}_0\boldsymbol{\psi}-\boldsymbol{\xi}\right)\right\rangle_{v_i}+\left\langle\mathbb{L}_0\boldsymbol{\psi},\boldsymbol{\psi}\right\rangle_{v_i}-\left\langle\boldsymbol{\xi},\boldsymbol{\psi}\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(31)}

Defining a “polarization field”

ϕ=χψ=iω(L0ψ−ξ),(32)\boldsymbol{\phi}=\chi\boldsymbol{\psi}=\frac{i}{\omega}\left(\mathbb{L}_0\boldsymbol{\psi}-\boldsymbol{\xi}\right), \tag*{(32)}

we have

−iω⟨ϕ,χc−1ϕ⟩vi+⟨(0∇×−∇×0)ψ,ψ⟩vi−iω⟨ψ,ψ⟩vi−⟨ξ,ψ⟩vi=0,i=1,2,3…(33)-\mathrm{i}\omega\langle\phi,\chi_c^{-1}\phi\rangle_{v_i}+\left\langle\begin{pmatrix} 0 & \nabla\times\\ -\nabla\times& 0 \end{pmatrix}\psi,\psi\right\rangle_{v_i}-\mathrm{i}\omega\langle\psi,\psi\rangle_{v_i}-\langle\xi,\psi\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(33)}

As we saw earlier, in regions where χ=χc\chi=\chi_c we have χc−1ϕ=ψ\chi_c^{-1}\phi=\psi, and where χ=0\chi=0 the polarization vanishes (ϕ=0\phi=0), such that we can rewrite the first term

−iω⟨ϕ,ψ⟩vi+⟨(0∇×−∇×0)ψ,ψ⟩vi−iω⟨ψ,ψ⟩vi−⟨ξ,ψ⟩vi=0,i=1,2,3…(34)-\mathrm{i}\omega\langle\phi,\psi\rangle_{v_i}+\left\langle\begin{pmatrix} 0 & \nabla\times\\ -\nabla\times& 0 \end{pmatrix}\psi,\psi\right\rangle_{v_i}-\mathrm{i}\omega\langle\psi,\psi\rangle_{v_i}-\langle\xi,\psi\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(34)}

Taking the real part of Eq. (34), we have a statement of the real Poynting’s theorem [4]

Im⁡[ω⟨ϕ,ψ⟩vi]+Re⁡[⟨(0∇×−∇×0)ψ,ψ⟩vi]−Re⁡[iω⟨ψ,ψ⟩vi]−Re⁡[⟨ξ,ψ⟩vi]=0,i=1,2,3…(35)\operatorname{Im}\left[\omega\langle\phi,\psi\rangle_{v_i}\right]+\operatorname{Re}\left[\left\langle\begin{pmatrix} 0 & \nabla\times\\ -\nabla\times& 0 \end{pmatrix}\psi,\psi\right\rangle_{v_i}\right]-\operatorname{Re}\left[\mathrm{i}\omega\langle\psi,\psi\rangle_{v_i}\right]-\operatorname{Re}\left[\langle\xi,\psi\rangle_{v_i}\right]=0,\quad i=1,2,3\ldots \tag*{(35)}

We can follow a similar procedure to obtain the imaginary part of Poynting’s theorem. Interestingly, it does not arise simply from taking the imaginary part of Eq. (34).

Quantum control

In this subsection we show that our quadratic-constraint formulation of quantum control problems also represents conservation laws. We start with a Hamiltonian of the form

H(t)=H0(t)+χ(t)Hc(t),(36)H(t)=H_0(t)+\chi(t)H_c(t), \tag*{(36)}

where H0H_0 is the non-controllable part of the Hamiltonian, Hc(t)H_c(t) is the controllable part, and χ(t)\chi(t) is the control trajectory to be designed. The Schrodinger equation describes the temporal dynamics of the time-evolution operator U(t,t0)U(t,t_0) (for some initial time t0t_0), given by

iℏddtU(t,t0)=H(t)U(t,t0).(37)\mathrm{i}\hbar\frac{d}{dt}U(t,t_0)=H(t)U(t,t_0). \tag*{(37)}

In this case, rather than source term, we have an initial condition at time t=t0t=t_0. Using Eqs. (36) and (37), we have

[iddt−H0(t)]U(t,t0)−χ(t)Hc(t)U(t,t0)=0.(38)\left[\mathrm{i}\frac{d}{dt}-H_0(t)\right]U(t,t_0)-\chi(t)H_c(t)U(t,t_0)=0. \tag*{(38)}

where we have set ℏ=1\hbar=1. We assume the control parameter can take one of two values χ(t)∈{0,χc}\chi(t)\in\{0,\chi_c\}, and denoting the operator

L0=iddt−H0,(39)\mathbb{L}_0=\mathrm{i}\frac{d}{dt}-H_0, \tag*{(39)}

we have the constraint:

⟨L0U(t,t0),L0U(t,t0)−χcHcU(t,t0)⟩=0.(40)\langle\mathbb{L}_0U(t,t_0),\mathbb{L}_0U(t,t_0)-\chi_cH_cU(t,t_0)\rangle=0. \tag*{(40)}

Multiplying by Hc−1/χcH_c^{-1}/\chi_c and rearranging leaves us with the constraint:

⟨L0U(t,t0),Hc−1χcL0U(t,t0)⟩−⟨L0U(t,t0),U(t,t0)⟩=0.(41)\left\langle\mathbb{L}_0U(t,t_0),\frac{H_c^{-1}}{\chi_c}\mathbb{L}_0U(t,t_0)\right\rangle-\langle\mathbb{L}_0U(t,t_0),U(t,t_0)\rangle=0. \tag*{(41)}

Inserting the expression for L0\mathbb{L}_0 into the term on the right-hand side and rearranging gives

⟨ddtU(t,t0),U(t,t0)⟩=i⟨L0U(t,t0),Hc−1χcL0U(t,t0)⟩+i⟨U(t,t0),H0†U(t,t0)⟩.(42)\left\langle\frac{d}{dt}U(t,t_0),U(t,t_0)\right\rangle=\mathrm{i}\left\langle\mathbb{L}_0U(t,t_0),\frac{H_c^{-1}}{\chi_c}\mathbb{L}_0U(t,t_0)\right\rangle+\mathrm{i}\left\langle U(t,t_0),H_0^\dagger U(t,t_0)\right\rangle. \tag*{(42)}

Taking the real part of this equation leaves us with:

ddt⟨U(t,t0),U(t,t0)⟩=(43)\frac{d}{dt}\langle U(t,t_0),U(t,t_0)\rangle= \tag*{(43)}
−2⟨L0U(t,t0),Im⁡[Hc−1χc]L0U(t,t0)⟩+2⟨U(t,t0),Im⁡[H0]U(t,t0)⟩,(44)-2\left\langle L_0U(t,t_0),\operatorname{Im}\left[\frac{H_c^{-1}}{\chi_c}\right]L_0U(t,t_0)\right\rangle+2\langle U(t,t_0),\operatorname{Im}[H_0]U(t,t_0)\rangle, \tag*{(44)}

where “Im” denotes the anti-Hermitian part of the operator, and we have used the fact that Im⁡[H0†]=−Im⁡[H0]\operatorname{Im}\left[H_0^\dagger\right]=-\operatorname{Im}[H_0]. In the case of real-valued control parameter and Hermitian operators, i.e., Im⁡[Hc−1/χc]=Im⁡[H0]=0\operatorname{Im}\left[H_c^{-1}/\chi_c\right]=\operatorname{Im}[H_0]=0, we have

ddt⟨U(t,t0),U(t,t0)⟩=0,(45)\frac{d}{dt}\langle U(t,t_0),U(t,t_0)\rangle=0, \tag*{(45)}

which represents conservation of probability in a Hermitian (closed) system. In a non-Hermitian system, the term on the right-hand side would simply give the probability loss due to the non-Hermiticity. Taking the imaginary part of Eq. (42) leads to a “reactive” probability conservation, in analogy with reactive power conservation in electromagnetism.

Forming the SDP by lifting the QCQP

In this section we provide the explicit transformations from the QCQP form of the problem to the SDP relaxation. This procedure is well-known, cf. Ref. [5], but we also include the formulation here, for reproducibility. We start by writing the QCQP:

maximize⁡ψ∈Cnψ†Aψ+Re⁡(β†ψ)subject to[L(χ1)ψ−ξ]†Di[L(χ2)ψ−ξ]=0,for all i∈Id,[L(χi)ψ−ξ]i=0,for all i∈IPML,(L(χi)ψ−ξ)†Di(L(χi)ψ−ξ)=0,for all i∈IPML.(46)\begin{aligned} \underset{\psi\in\mathbb{C}^{n}}{\operatorname{maximize}}\quad&\psi^\dagger A\psi+\operatorname{Re}(\beta^\dagger\psi)\\ \text{subject to}\quad&[\mathcal{L}(\chi_1)\psi-\xi]^\dagger D_i[\mathcal{L}(\chi_2)\psi-\xi]=0,\quad\text{for all }i\in I_d,\\ &[\mathcal{L}(\chi_i)\psi-\xi]_i=0,\quad\text{for all }i\in I_{\mathrm{PML}},\\ &(\mathcal{L}(\chi_i)\psi-\xi)^\dagger D_i(\mathcal{L}(\chi_i)\psi-\xi)=0,\quad\text{for all }i\in I_{\mathrm{PML}}. \tag*{(46)} \end{aligned}

where IdI_d is the set of indices in the designable domain, IPMLI_{\mathrm{PML}} is the set of indices in the PML, and Cn\mathbb{C}^{n} refers to the set of nn-dimensional complex-valued vectors. Before any transformations, we can compactify our notation:

maximize⁡ψ∈Cnψ†Aψ+Re⁡(β†ψ)subject toψ†Biψ+Re⁡(vi†ψ)=γi,for all i∈Iquad,Re⁡[ui†(L(χi)ψ)]=δi,for all i∈Ilin.(47)\begin{aligned} \underset{\psi\in\mathbb{C}^{n}}{\operatorname{maximize}}\quad&\psi^\dagger A\psi+\operatorname{Re}(\beta^\dagger\psi)\\ \text{subject to}\quad&\psi^\dagger B_i\psi+\operatorname{Re}(v_i^\dagger\psi)=\gamma_i,\quad\text{for all }i\in I_{\mathrm{quad}},\\ &\operatorname{Re}\left[u_i^\dagger(\mathcal{L}(\chi_i)\psi)\right]=\delta_i,\quad\text{for all }i\in I_{\mathrm{lin}}. \tag*{(47)} \end{aligned}

To arrive at Eq. (47), we use four steps. First, we combine the quadratic constraints of Eq. (46) into a single form, differentiated only by index ii, in the now larger set IquadI_{\mathrm{quad}}. Second, we form the linear constraints by multiplying over a basis set of vectors uiu_i. Third, we define δi=Re⁡(ui†ξ)\delta_i=\operatorname{Re}\left(u_i^\dagger\xi\right). Finally, we take the real parts of the quadratic and linear constraint equations of Eq. (46), and we account for the imaginary parts by allowing for DiD_i and uiu_i to take unit entries or their complex counterparts (i.e., multiplied by the imaginary unit).

The first step to simplifying Eq. (47) is to homogenize the problem, which means to transform the linear terms in the QCQP to quadratic terms, so that all terms in Eq. (46) are either quadratic or scalar. We can do this by introducing a new slack variable ss into the objective and constraints, multiplying the linear terms. This slack variable must have absolute value 1, but it can be positive or negative; a negative one value would be compensated in ψ\psi by multiplying by −1-1. With this new slack variable, the problem can be written

maximize⁡ψ∈Cn, ∣s∣=1(ψs)†(Aβ2β†20)(ψs)subject to(ψs)†(Bivi2vi†20)(ψs)=γi,for all i∈Iquad,(ψs)†(0ui†L(χi)2ui†L(χi)20)(ψs)=δi,for all i∈Ilin.(48)\begin{aligned} \underset{\psi\in\mathbb{C}^{n},\,|s|=1}{\operatorname{maximize}}\quad& \begin{pmatrix}\psi\\s\end{pmatrix}^{\dagger} \begin{pmatrix}A&\frac{\beta}{2}\\\frac{\beta^\dagger}{2}&0\end{pmatrix} \begin{pmatrix}\psi\\s\end{pmatrix}\\ \text{subject to}\quad& \begin{pmatrix}\psi\\s\end{pmatrix}^{\dagger} \begin{pmatrix}B_i&\frac{v_i}{2}\\\frac{v_i^\dagger}{2}&0\end{pmatrix} \begin{pmatrix}\psi\\s\end{pmatrix}=\gamma_i,\quad\text{for all }i\in I_{\mathrm{quad}},\\ & \begin{pmatrix}\psi\\s\end{pmatrix}^{\dagger} \begin{pmatrix}0&\frac{u_i^\dagger\mathcal{L}(\chi_i)}{2}\\\frac{u_i^\dagger\mathcal{L}(\chi_i)}{2}&0\end{pmatrix} \begin{pmatrix}\psi\\s\end{pmatrix}=\delta_i,\quad\text{for all }i\in I_{\mathrm{lin}}. \tag*{(48)} \end{aligned}

in which all of the expressions are either quadratic in the combined variable (ψ s)T(\psi\ s)^{T}, or scalar values. We can again make the notation more compact, and write this problem as a homogenized, complex-valued QCQP:

maximize⁡xx†A0xsubject tox†Aix=aifor all i.(49)\begin{aligned} \underset{x}{\operatorname{maximize}}\quad&x^{\dagger}A_{0}x\\ \text{subject to}\quad&x^{\dagger}A_{i}x=a_{i}\quad\text{for all }i. \tag*{(49)} \end{aligned}

To then convert this to a complex-valued SDP, we simply take the trace of each expression, which does not modify any values, then use the invariance of trace under cyclic permutations to form the product xx†xx^{\dagger}, which we define to be a new positive semidefinite, rank-one matrix XX. The equivalent problem for this matrix variable is

maximize⁡XTr⁡(A0X)subject toTr⁡(AiX)=aifor all i,X≥0,rank⁡X=1.(50)\begin{aligned} \underset{X}{\operatorname{maximize}}\quad&\operatorname{Tr}(A_{0}X)\\ \text{subject to}\quad&\operatorname{Tr}(A_{i}X)=a_{i}\quad\text{for all }i,\\ &X\geq0,\\ &\operatorname{rank}X=1. \tag*{(50)} \end{aligned}

We can relax this problem by dropping the rank-one constraint, leaving the standard-form (complex-valued) SDP:

maximize⁡XTr⁡(A0X)subject toTr⁡(AiX)=aifor all i,X≥0.(51)\begin{aligned} \underset{X}{\operatorname{maximize}}\quad&\operatorname{Tr}(A_{0}X)\\ \text{subject to}\quad&\operatorname{Tr}(A_{i}X)=a_{i}\quad\text{for all }i,\\ &X\geq0. \tag*{(51)} \end{aligned}

In this form, the problem can be solved in any SDP solver. (If the solver does not accept complex-valued matrices, it is simple to double all dimensions and separate the real and imaginary parts of the vectors and matrices.)

Graph Theory for Semidefinite Programming

Graphs distill real-world relations into abstract lines and vertices, for social networks in sociology, genetic networks in biology, communication networks in computer science, lattice structures in physics, and molecular chains in chemistry. Complex dynamics can simplify when occurring on graphs with special structure. In particular, chordal graphs represent a class of connections where many hard problems can be easily solved, including graph coloring, clique finding, and matrix factorization [6]. In this section, we review basics of graphs and chordal graphs, as well as theorems that foreground chordal graphs in sparse semidefinite programming.

A graph comprises a set of vertices V={v1,v2,…,vn}V=\{v_{1},v_{2},\ldots,v_{n}\} and their connecting edges E⊆V×VE\subseteq V\times V. The vertices and edges uniquely define the graph: G(V,E)G(V,E). We consider undirectional graph whose edges are unordered pairs, denoted by curly brackets such as {vi,vj}\{v_{i},v_{j}\}. If a series of edges leads one vertex back to itself, then these edges form a cycle. Two vertices viv_{i} and vjv_{j} are adjacent if there is an edge between them, i.e., if {vi,vj}∈E\{v_{i},v_{j}\}\in E. Vertices that are all adjacent to each other form a clique. A clique can expand upon admitting new vertices that are adjacent to all its existing members. If no such new vertices exist, the clique is then called a maximal clique of the graph.

Many large problems can be simplified if their graph is a chordal. A chordal graph is a graph in which every cycle of length four and greater has a chord (an edge between nonconsecutive vertices of the cycle). In other words, if you trace a cycle of four (or more) edges without finding a shortcut, then the graph is not a chordal graph. Any graph can be made chordal by adding extra edges. In the extreme case, supplying every possible edges guarantees a chordal graph, but then there can be no problem-size reduction. The art is to add as few edges as possible to make a graph chordal. This procedure is called chordal completion, often implemented via heuristic algorithms [7].

Sparsity in matrices map to specific graph representations of the matrix data. Zeros in a symmetric matrix XX are missing edges in the corresponding undirected graph G(V,E)G(V,E): {vi,vj}∉E⟺Xij=Xji=0\{v_{i},v_{j}\}\notin E\Longleftrightarrow X_{ij}=X_{ji}=0. Two groups of symmetric matrices XX are of particular interest in sparse semidefinite programming. The first are matrices that are positive semidefinite and sparse, with sparsity pattern given by the graph G(V,E)G(V,E):

S+n(E,0)={X∈S+n∣Xij=Xji=0 if (i,j)∉E},(52)\mathbb{S}_{+}^{n}(E,0)=\{X\in\mathbb{S}_{+}^{n}\mid X_{ij}=X_{ji}=0\text{ if }(i,j)\notin E\}, \tag*{(52)}

where S+n\mathbb{S}_{+}^{n} (without argument) refers to the set of positive definite symmetric matrices. The second group consists of matrices that are not necessarily positive semidefinite or sparse but can be “completed” into positive semidefinite matrices. To motivate this, consider an inner product Tr⁡(AX)\operatorname{Tr}(A X) between the symmetric matrix XX and a sparse symmetric matrix AA whose sparsity is given by the graph G(V,E)G(V,E). The inner product multiplies matrices element-wise, so only the elements in XX that correspond to the edges in the graph G(V,E)G(V,E) are involved in the computation of the inner product. If the rest of the elements in X\mathbb{X} can be altered to turn X\mathbb{X} into a positive semidefinite matrix, say M\mathbb{M}, then we say X\mathbb{X} belongs to a group of completable partial symmetric matrices:

S+n(E,?)={X∈Sn∣∃M≥0, Mij=Xij ∀(i,j)∈E}(53)\mathbb{S}_{+}^{n}(E,?) = \{\mathbb{X} \in\mathbb{S}^{n} \mid\exists\mathbb{M} \ge0,\ \mathbb{M}_{ij} = \mathbb{X}_{ij}\ \forall(i,j) \in E\} \tag*{(53)}

The two matrix spaces, S+n(E,0)\mathbb{S}_{+}^{n}(E,0) and S+n(E,?)\mathbb{S}_{+}^{n}(E,?), are both convex cones and, in fact, are duals of each other [6]. Together, they constitute the basic matrix spaces in sparse semidefinite programming.

Crucially, if the graph G(E,V)G(E,V) is a chordal graph, both types of matrices above can be decomposed into smaller matrices defined on the maximal cliques of the graph, {C1,C2,…,Cl}\{C_1,C_2,\ldots,C_l\}. Aiding this decomposition is a projection matrix TlT_l that projects a matrix X\mathbb{X} into its principle submatrix Xl=TlXTlT\mathbb{X}_l = T_l\mathbb{X}T_l^{\mathsf{T}}, and reads (Tl)ij=1(T_l)_{ij}=1 if Cl(i)=jC_l(i)=j and zero otherwise, where Cl(i)C_l(i) is the ii-th vertex in ClC_l. If the matrix X\mathbb{X} is positive semidefinite completable, i.e., X∈S+n(E,?)\mathbb{X} \in\mathbb{S}_{+}^{n}(E,?), then all the submatrices Xl\mathbb{X}_l are all positive semidefinite, as dictated by Grone’s theorem [8]:

X∈S+n(E,?)⟺Xl=TlXTlT∈S+∣Cl∣(54)\mathbb{X} \in\mathbb{S}_{+}^{n}(E,?) \Longleftrightarrow\mathbb{X}_l = T_l\mathbb{X}T_l^{\mathsf{T}} \in\mathbb{S}_{+}^{|C_l|} \tag*{(54)}

If the matrix X\mathbb{X} is sparse positive semidefinite, i.e., X∈S+n(E,0)\mathbb{X} \in\mathbb{S}_{+}^{n}(E,0), then all the submatrices Xl\mathbb{X}_l are positive semidefinite and uniquely expand the matrix X\mathbb{X}, as dictated by Agler’s theorem [9]:

X∈S+n(E,0)⟺X=∑l=1pTlTXlTl, Xl∈S+∣Cl∣(55)\mathbb{X} \in\mathbb{S}_{+}^{n}(E,0) \Longleftrightarrow\mathbb{X} = \sum_{l=1}^{p} T_l^{\mathsf{T}}\mathbb{X}_lT_l,\ \mathbb{X}_l \in\mathbb{S}_{+}^{|C_l|} \tag*{(55)}

Agler’s theorem in Eq. (55) allows one to decompose sparse semidefinite programs in their dual forms, where the matrix variable X\mathbb{X} directly inherits the sparsity of the problem; Grone’s theorem in Eq. (54) allows one to decompose sparse semidefinite programs in their primal forms, where the the matrix variable X\mathbb{X} does not inherit the sparsity but is multiplied by matrices that do. We discuss this second scenario in the next section.

Fast Semidefinite Programming on Chordal Graphs

Semidefinite programs are challenging to solve for large-dimensional problems, unless there is sparsity to be leveraged. Sparsity mainly accelerates two operations in the semidefinite programming in Eq. (51): multiplying matrix X\mathbb{X} by matrix AiA_i, and verifying the semidefinite constraint, X≥0\mathbb{X} \ge0, is satisfied. These two operations are the numerical bottleneck for most semidefinite programming algorithms [5, 10], both costing at least O(n3)O(n^3) per iteration for an nn-dimensional problem. To accelerate these two operations, one needs to consider the aggregate sparsity pattern of the semidefinite program in Eq. (51), which are the places where all the objective and constraint matrices, AiA_i, are zero. The aggregate sparsity pattern is given by the sparsity pattern of the LTL\mathsf{L}^{\mathsf{T}}\mathsf{L} matrix in the QCQP in Eq. (46), which is shown as the black and red squares in Fig. 1(b) in the main text for a number scenarios. Most sparsity can accelerate matrix-matrix multiplications by multiplying only the nonzero entries. On the other hand, only a special type of aggregated sparsity based on chordal graphs can accelerate the verification of the semidefinite constraint, which we explain below.

The major bottleneck of large-scale semidefinite programming is the verification of its semidefinite constraint, which is resolvable if the underlying sparsity pattern corresponds to a chordal graph [6]. There is a unique mapping between sparsity pattern of symmetric matrices and undirected graphs: an nonzero (i,j)(i,j) entry of the former maps to a edge between the ii and jj vertices of the latter. (See Section IV for a quick review on graph theories.) A chordal graph, in particular, is a graph where all cycles of four or more vertices have a chord. As shown in the Fig. 1(a) of the main text, the sparsity pattern of the LTL\mathsf{L}^{\mathsf{T}}\mathsf{L} operator in our photonic problem does not necessarily correspond to a chordal graph but it can be made into one by adding extra chords (the green lines in Fig. 1(a)). Chordal graph is desirable because it allows one to distribute certain complex operations into different “cliques”, a set of vertices in the graph that are all connected to each other (as in Fig. 1(a)). In particular, if the aggregate sparsity of the semidefinite program in Eq. (51) can be completed into a chordal graph, then Grone’s theorem in Eq. (54) shows its semidefinite constraint X⪰0\mathbb{X} \succeq0 can be replaced by “smaller” semidefinite constraints on each of its cliques: X[Ij,Ij]⪰0\mathbb{X}[I_j,I_j] \succeq0, where IjI_j denoting the indices for the jjth clique. The optimization problem of Eq. (51) becomes

maximize⁡X∈SnTr⁡(A0X)subject toTr⁡(AiX)=ai,for i=1,2,…,m,X[Ij,Ij]⪰0,for j=1,2,…,p,(56)\begin{aligned} \underset{\mathbb{X}\in\mathbb{S}^{n}}{\operatorname{maximize}}\quad&\operatorname{Tr}(A_0\mathbb{X})\\ \text{subject to}\quad&\operatorname{Tr}(A_i\mathbb{X})=a_i,\quad\text{for }i=1,2,\ldots,m,\\ &\mathbb{X}[I_j,I_j]\succeq0,\quad\text{for }j=1,2,\ldots,p, \tag*{(56)} \end{aligned}

where pp to denotes the total number of cliques in the chordal graph. The only difference between the decomposed semidefinite program and the original semidefinite program is the semidefinite constraints are now applied to smaller cliques. As the semidefinite constraint is the main computational bottleneck that increases as O(n3)O(n^3) with the matrix size nn, breaking a large X\mathbb{X} into many smaller ones in Eq. (56) allows us to significantly accelerate the SDP computations.

Implementation of the Majorization-Minimization Algorithm

To obtain a rank-1 solution to the QCQP, a proxy function R(X)\mathcal{R}(\mathbf{X}) for rank is incorporated into the objective as a penalty term to be minimized:

maximize⁡XTr⁡(AX)−γR(X)subject to⁡Tr⁡(BiX)=bi,for i=1,2,…,m,X≥0.(57)\begin{aligned} \underset{\mathbf{X}}{\operatorname{maximize}}\quad& \operatorname{Tr}(\mathbf{A}\mathbf{X})-\gamma\mathcal{R}(\mathbf{X})\\ \operatorname{subject\ to}\quad& \operatorname{Tr}(\mathbf{B}_i\mathbf{X})=b_i,\quad\text{for }i=1,2,\ldots,m,\\ & \mathbf{X}\ge0. \tag*{(57)} \end{aligned}

We successfully generated rank-1 solutions to Eq. (57), following the methods introduced by Liu, Sun, and Tsang in Ref. [11], producing designs from the modified-SDP formulation. Here we summarize the key steps of Ref. [11] that we implemented.

The first step is to find an approximate representation of the rank. One way to write the rank is to count the number of nonzero singular values, which is given by

rank⁡(X)=∑iH(σi(X))(58)\operatorname{rank}(\mathbf{X})=\sum_i H(\sigma_i(\mathbf{X})) \tag*{(58)}

where σi(X)\sigma_i(\mathbf{X}) is the ithi^{\text{th}} singular value of X\mathbf{X} and H(x)H(x) is the Heaviside step function, equal to 1 if x>0x>0 and 0 if x=0x=0 for x≥0.x\ge0.H(x)$ is non-differentiable and therefore cannot be used in gradient-based optimization, but it can be approximated by the smooth, differentiable function

θ(x,ε)=1−e−x/ε(59)\theta(x,\varepsilon)=1-e^{-x/\varepsilon} \tag*{(59)}

with ε>0\varepsilon>0, noting that lim⁡ε→0θ(x,ε)=H(x)\lim_{\varepsilon\to0}\theta(x,\varepsilon)=H(x). Defining

Θ(X,ε)=∑iθ(σi(X),ε)(60)\Theta(\mathbf{X},\varepsilon)=\sum_i\theta(\sigma_i(\mathbf{X}),\varepsilon) \tag*{(60)}

the goal is to solve Eq. (57) with R(X)=Θ(X,ε)\mathcal{R}(\mathbf{X})=\Theta(\mathbf{X},\varepsilon). The non-differentiability of the rank function has been removed, but Θ(X,ε)\Theta(\mathbf{X},\varepsilon) is still concave.

A concave function has a special property: it is bounded above everywhere by any tangent plane intersecting the function at one point. In other words, the value of the function at a given point (matrix), plus a term given by the inner product gradient of the function and the difference between the two points, will always be an upper bound to objective function itself. In this case the approximate rank function Θ\Theta has (elementwise) gradient

∇Θ(X,ε)=1εU(e−σ1(X)/εe−σ2(X)/ε⋱)U†(61)\nabla\Theta(\mathbf{X},\varepsilon)=\frac{1}{\varepsilon}\mathbf{U} \begin{pmatrix} e^{-\sigma_1(\mathbf{X})/\varepsilon} & & \\ & e^{-\sigma_2(\mathbf{X})/\varepsilon} & \\ & & \ddots \end{pmatrix} \mathbf{U}^{\dagger} \tag*{(61)}

where UΣU†\mathbf{U}\boldsymbol{\Sigma}\mathbf{U}^{\dagger} is the singular value decomposition of X\mathbf{X} (equivalent to its eigendecomposition, since X\mathbf{X} is positive semidefinite). Then, for any feasible matrix Xk\mathbf{X}_k obtained at the kthk^{\text{th}} iteration,

Θ(X,ε)≤Θ(Xk,ε)+⟨∇Θ(Xk,ε),X−Xk⟩(62)\Theta(\mathbf{X},\varepsilon)\le\Theta(\mathbf{X}_k,\varepsilon)+\langle\nabla\Theta(\mathbf{X}_k,\varepsilon),\mathbf{X}-\mathbf{X}_k\rangle \tag*{(62)}

The first term on the right-hand side of Eq. (62) is constant with respect to X\mathbf{X}, while the second term is linear. Hence minimizing the second term is a convex optimization problem, and will result in a minimization of Eq. (62), which is itself an upper bound on rank. We define the objective to minimize as R\mathcal{R}:

R(X)=⟨∇Θ(Xk,ε),X⟩(63)\mathcal{R}(\mathbf{X})=\langle\nabla\Theta(\mathbf{X}_k,\varepsilon),\mathbf{X}\rangle \tag*{(63)}

Thus by iteratively solving convex optimization problems, we can continuously push down an upper bound on the rank, and thereby the rank itself, ideally near 1. This is an example of a “majorization–minimization” algorithm [12]. To select an initial point for the optimization, we solve Eq. (57) with R(X)=Tr⁡(X)\mathcal{R}(\mathbf{X})=\operatorname{Tr}(\mathbf{X}). For positive-semidefinite matrices, the trace is a well-known proxy for rank(X)(\mathbf{X}). Additionally, since Θ(X,ε)\Theta(\mathbf{X},\varepsilon) becomes highly concave as ε→0\varepsilon\to0, which is liable to cause computational difficulty, we execute the MM algorithm iteratively over decreasing values of ε\varepsilon until convergence. Putting everything together, with convergence tolerances δ1,δ2,δ3\delta_1,\delta_2,\delta_3, we implement the following process:

  1. Define arbitrary initial γ\gamma.

  1. Solve Eq. (57) with R(X)=Tr⁡(X)\mathcal{R}(\mathbf{X})=\operatorname{Tr}(\mathbf{X}) to obtain an initial Xk\mathbf{X}_k.

  1. Define arbitrary initial ε\varepsilon.

  1. Solve Eq. (57) with R(X)=⟨∇Θ(Xk,ε),X⟩\mathcal{R}(\mathbf{X})=\langle\nabla\Theta(\mathbf{X}_k,\varepsilon),\mathbf{X}\rangle for the optimal solution X=Xk+1\mathbf{X}=\mathbf{X}_{k+1}. Repeat until ∥Xk+1−Xk∥F/∥Xk∥F<δ1\lVert\mathbf{X}_{k+1}-\mathbf{X}_k\rVert_F/\lVert\mathbf{X}_k\rVert_F<\delta_1.

  1. Define the output of Step 4 as Xl\mathbf{X}_l. Decrease ε\varepsilon by an arbitrary factor α\alpha and repeat Step 4. Repeat until ∥Xl+1−Xl∥F/∥Xl∥F<δ2\lVert\mathbf{X}_{l+1}-\mathbf{X}_l\rVert_F/\lVert\mathbf{X}_l\rVert_F<\delta_2.

  1. Repeat steps 2-5, increasing γ\gamma by an arbitrary factor β\beta, until σ1(X)/σ2(X)>δ3\sigma_1(\mathbf{X})/\sigma_2(\mathbf{X})>\delta_3.

We make simple (non-optimized) choices γ=10−7\gamma=10^{-7}, δ1=10−3\delta_1=10^{-3}, δ2=10−3\delta_2=10^{-3}, δ3=105\delta_3=10^5, ε=0.5\varepsilon=0.5, α=2\alpha=2, and β=1.5\beta=1.5.

Metalens bound calculation

Formulation of the target function

We consider a two-dimensional scattering problem for a TE-polarized electric field (such that it can be treated as a scalar electric field) and we seek to optimize the intensity of the field at a target point xtarx_{\mathrm{tar}}. We denote the field at the target point as Etar=E(xtar)E_{\mathrm{tar}}=E(x_{\mathrm{tar}}), and calculate a bound on the maximal value of the quantity ∣Etar∣2\lvert E_{\mathrm{tar}}\rvert^2, given a narrow design region of length dd in which each point in D\mathcal{D} can be vacuum or a material with susceptibility χ1\chi_1 (see Fig. 2(a) of the main text). We can express the field at the target point as

Etar=Ei(xtar)+Es(xtar),(64)E_{\mathrm{tar}}=E_i(x_{\mathrm{tar}})+E_s(x_{\mathrm{tar}}), \tag*{(64)}

where Ei(xtar)E_i(x_{\mathrm{tar}}) is the incident field at the target point, i.e., in the absence of material, and Es(xtar)E_s(x_{\mathrm{tar}}) is the scattered field at the target point. Note, that the background field solves the background-L\mathcal{L} operator, i.e., L0Ei=iωJ\mathcal{L}_0E_i=i\omega J. The target point is set at a distance ff from the design region, such that the numerical aperture (given by NA=sin⁡[arctan⁡[(d/2)/f]])\mathrm{NA}=\sin[\arctan[(d/2)/f]]) is set to NA=0.9\mathrm{NA}=0.9.

We can express the scattered field at the target point using a Green’s function

Es(xtar)=∫Γ0(xtar,x)P(x) dx,(65)E_s(x_{\mathrm{tar}})=\int\Gamma_0(x_{\mathrm{tar}},x)P(x)\,dx, \tag*{(65)}

where P(x)P(x) is the polarization currents in the design material, given by

P(x)=χ(x)E(x)=1ω2(L0E−iωJ(x))=1ω2(L0E−L0Ei).(66)P(x)=\chi(x)E(x)=\frac{1}{\omega^2}(\mathcal{L}_0E-i\omega J(x))=\frac{1}{\omega^2}(\mathcal{L}_0E-\mathcal{L}_0E_i). \tag*{(66)}

For clarity of notation, we will denote the integration as an operator Γtar=ω−2∫Γ0(xtar,x) dx\Gamma_{\mathrm{tar}}=\omega^{-2}\int\Gamma_0(x_{\mathrm{tar}},x)\,dx (numerically, this a row from the matrix representing the Greens’ function).

A natural way to proceed is to substitute Eqs. (65) and (66) into Eq. (64) and squaring:

∣Etar∣2=∣Ei(xtar)+Γtar(L0E−L0Ei)∣2(67)\lvert E_{\mathrm{tar}}\rvert^2=\lvert E_i(x_{\mathrm{tar}})+\Gamma_{\mathrm{tar}}(\mathcal{L}_0E-\mathcal{L}_0E_i)\rvert^2 \tag*{(67)}
=∣Ei(xtar)∣2+∣Γtar(L0E−L0Ei)∣2+2Re⁡[Ei∗(xtar)Γtar(L0E−L0Ei)].(68)=\lvert E_i(x_{\mathrm{tar}})\rvert^2+\lvert\Gamma_{\mathrm{tar}}(\mathcal{L}_0E-\mathcal{L}_0E_i)\rvert^2+2\operatorname{Re}\left[E_i^*(x_{\mathrm{tar}})\Gamma_{\mathrm{tar}}(\mathcal{L}_0E-\mathcal{L}_0E_i)\right]. \tag*{(68)}

However, in this case, the target function has a matrix of the form Γtar†Γtar\Gamma_{\mathrm{tar}}^\dagger\Gamma_{\mathrm{tar}}, which is not sparse, and we will not be able to exploit the sparse structure of the problem in the optimization.

An alternative formulation of the target function, which preserves sparsity, is given by

∣Etar∣=max⁡θRe⁡[Etareiθ],(69)\lvert E_{\mathrm{tar}}\rvert=\max_{\theta}\operatorname{Re}\left[E_{\mathrm{tar}}e^{i\theta}\right], \tag*{(69)}

where θ\theta is an auxiliary angle. After the optimization procedure, we can square the result to obtain ∣Etar∣2\lvert E_{\mathrm{tar}}\rvert^2. Explicitly, we have

∣Etar∣=max⁡θRe⁡[Ei(xtar)eiθ+Γtar(xtar,x)(L0E−L0Ei)eiθ],(70)\lvert E_{\mathrm{tar}}\rvert=\max_{\theta}\operatorname{Re}\left[E_i(x_{\mathrm{tar}})e^{i\theta}+\Gamma_{\mathrm{tar}}(x_{\mathrm{tar}},x)(\mathcal{L}_0E-\mathcal{L}_0E_i)e^{i\theta}\right], \tag*{(70)}

which is linear in the term Γtar\Gamma_{\mathrm{tar}} and preserves the sparse nature of the problem. Together with Eq. (24), this forms the QCQP to be solved.

Fig. 1 shows the results of the optimization process for different values of θ\theta, from which the maximum can be selected. While this approach requires multiple optimizations (sweeping over different values of θ\theta), the speed-up provided by the sparseness of this form is significantly faster compared to non-sparse formulations, and enables the optimization over large domains (see Fig. 2(d) in the main text).

Optimization results for the field intensity focused by a metalens of different lengths

Figure 1 (PDF p. 23). Optimization results for the field intensity focused by a metalens of different lengths (dd), using an auxiliary angle θ\theta (see Eq. (69)).

Scattered-field formulation

The target function in Eq. (70), as well as the constraints from Eq. (24) are quadratic form in the total field (EE). Alternatively, the QCQP can be written where the quadratic form is of the scattered field EsE_s (given by Es=E−EiE_s=E-E_i). Using Eqs. (65) and (66) we can rewrite the target function in terms of EsE_s:

∣Etar∣2=∣Ei(xtar)+ΓtarL0Es∣2.(71)\lvert E_{\mathrm{tar}}\rvert^2=\left\lvert E_i(x_{\mathrm{tar}})+\Gamma_{\mathrm{tar}}\mathcal{L}_0E_s\right\rvert^2 . \tag*{(71)}

Similarly, we can express the constraints from Eq. (24) in terms of scattered field:

⟨(L0(Ei+Es)−iωJ),χc−1ω2(L0(Ei+Es)−iωJ)⟩vi(72)\left\langle\left(\mathcal{L}_0(E_i+E_s)-i\omega J\right),\frac{\chi_c^{-1}}{\omega^2}\left(\mathcal{L}_0(E_i+E_s)-i\omega J\right)\right\rangle_{v_i} \tag*{(72)}
−⟨L0(Ei+Es),(Ei+Es)⟩vi−iω⟨J,(Ei+Es)⟩vi=0,i=1,2,3…(73)-\left\langle\mathcal{L}_0(E_i+E_s),(E_i+E_s)\right\rangle_{v_i}-i\omega\left\langle J,(E_i+E_s)\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(73)}

Using iωJ=L0Eii\omega J=\mathcal{L}_0E_i and rearranging, we are left with:

⟨L0Es,χc−1ω2L0Es⟩vi−⟨L0Es,Es⟩vi−⟨L0Es,Ei⟩vi=0,i=1,2,3…(74)\left\langle\mathcal{L}_0E_s,\frac{\chi_c^{-1}}{\omega^2}\mathcal{L}_0E_s\right\rangle_{v_i}-\left\langle\mathcal{L}_0E_s,E_s\right\rangle_{v_i}-\left\langle\mathcal{L}_0E_s,E_i\right\rangle_{v_i}=0,\quad i=1,2,3\ldots \tag*{(74)}

Together, the target function (Eq. (71)) and the constraints (Eq. (74)) form a QCQP in the scattered field EsE_s.

Unitary bound

In this section, we derive a bound for the efficiency of a metalens of length dd based on the unitarity of the scattering matrix describing the system. In the most general case, we can write the field at the target point using Green’s functions:

Etar=∫0dΓzzEE(xt,x)ξxE(x) dx+∫0dΓzyEH(xt,x)ξyH(x) dx,(75)E_{\mathrm{tar}}=\int_{0}^{d}\Gamma_{zz}^{EE}(x_t,x)\xi_x^E(x)\,\mathrm{d}x+\int_{0}^{d}\Gamma_{zy}^{EH}(x_t,x)\xi_y^H(x)\,\mathrm{d}x, \tag*{(75)}

where ΓzzEE\Gamma_{zz}^{EE} and ΓzyEH\Gamma_{zy}^{EH} are the electric and magnetic Green’s functions, respectively, and ξzE\xi_z^E and ξyH\xi_y^H represent electric and magnetic current sources, respectively. After discretizing the domain, we have the matrix form:

Etar=(ΓzzEE ΓzyEH)⏟Γ(ξzEξyH)⏟ξh,(76)E_{\mathrm{tar}} = \underbrace{\left(\Gamma_{zz}^{EE}\ \Gamma_{zy}^{EH}\right)}_{\Gamma} \underbrace{\begin{pmatrix}\xi_z^E\\ \xi_y^H\end{pmatrix}}_{\xi}h, \tag*{(76)}

where hh is the discretization step size, and squaring the field at the target point, leaves us with:

∣Etar∣2=ξ†Γ†Γξh2.(77)\left|E_{\mathrm{tar}}\right|^2 = \xi^\dagger\Gamma^\dagger\Gamma\xi h^2. \tag*{(77)}

Assuming the incident field is a plane wave with amplitude 1, we can normalize the current distributions:

ξ†ξh=∫∣n×E∣2 dx+∫∣n×H∣2 dx=2d.(78)\xi^\dagger\xi h = \int|n \times E|^2\,dx + \int|n \times H|^2\,dx = 2d. \tag*{(78)}

We can now write the intensity maximization problem:

max⁡ξ†Γ†Γξh2s.t.ξ†ξ=2dh(79)\begin{aligned} \max\quad&\xi^\dagger\Gamma^\dagger\Gamma\xi h^2\\ \mathrm{s.t.}\quad&\xi^\dagger\xi= \frac{2d}{h} \tag*{(79)} \end{aligned}

In order to solve the equation above, we define a normalized current ζ=ξh/(2d)\zeta= \xi\sqrt{h/(2d)}, such that the problem can be rewritten in the following form:

max⁡ζ†(2dΓ†Γh)ζs.t.ζ†ζ=1(80)\begin{aligned} \max\quad&\zeta^\dagger(2d\Gamma^\dagger\Gamma h)\zeta\\ \mathrm{s.t.}\quad&\zeta^\dagger\zeta= 1 \tag*{(80)} \end{aligned}

The optimization problem is now in the form of a Rayleigh quotient, where the maximum of the target function is given by the largest eigenvalue of 2dΓ†Γh2d\Gamma^\dagger\Gamma h. The results of this bound calculation are shown in Fig. 2(c) of the main text.

Compatibility with FEM solvers

The formulation we present here utilizes the differential form of the physical equation, which is used in many commercially available solvers. These can be both finite difference (FDFD) solvers, as well as finite element (FEM) solvers. Here, we demonstrate how an FEM electromagnetic solver (COMSOL) can be used to calculate a bound in a simple photonic problem. We model a 2D system, with a geometry shown in Fig. 2(a). We set periodic boundary conditions for the top and bottom boundaries and simulate perfectly matched layers (PML) on the sides on the structure. Fig. 2 After setting current sources, we export the matrix and vector describing the linear system as constructed by the software. We choose the point that comprise a ‘design’ region (see Fig. 2(b) for an example) and calculate bounds for the maximal value of the target function

f(E)=∫Vdes∣E(x)∣2 dx,(81)f(E) = \int_{V_{\mathrm{des}}} |E(x)|^2\,dx, \tag*{(81)}

i.e., integrated field intensity over the entire design region VdesV_{\mathrm{des}}. In this example, the material has a refractive index of n=12n = \sqrt{12}, and the optical wavelength was set to λ=1.55μm\lambda= 1.55\mu\mathrm{m}. For comparison, we repeat the calculation with a finite-time frequency domain solver (FDFD). Fig. 2(c) shows the calculated bounds as a function of design region length. We see that the FDFD and FEM based bound calculations agree, showing a linear dependence of the target function with the design region length.

Ref. [13] is a delightful review of approaches to inverse design and performance bounds, especially techniques that had been developed by early 2021. Yet Ref. [13] goes significantly further, offering a unified, generalized mathematical framework for these approaches. Here we discuss the bound approach, newly developed in Ref. [13], that is close to the approach we propose in the main text.

COMSOL-generated mesh and calculated bounds

Figure 2 (PDF p. 25). (a) COMSOL-generated mesh, and a magnified view of the degrees of freedom being solved for. (b) Calculated bound as a function of design region length, using differential operators from FEM (red) and FDFD (blue) solvers. Simulation results of an unstructured dielectric (using both solvers) are shown for reference.

The starting point of Ref. [13] is a physical design problem written in the form

(A0+diag⁡(θ))z=b,(82)(A_0 + \operatorname{diag}(\theta))z = b, \tag*{(82)}

where A0A_0 is a design-independent differential operator (plus, possibly, the identity matrix scaled by background constants), diag⁡(θ)\operatorname{diag}(\theta) is a diagonal matrix whose diagonal elements are the designable degrees of freedom, zz is the field of interest, and bb comprises the sources.

The matrices and vectors in the physical design equation are all assumed to be real-valued. From this assumption, they derive “power inequalities” of the form

(A0z−b)TD(A0z−b)≤zTDz,(83)(A_0z-b)^\mathsf{T}D(A_0z-b) \leq z^\mathsf{T}Dz, \tag*{(83)}

which is equivalent to the power-conservation bounds of [14, 15], when all of the equations are real-valued.

Yet in nearly all cases of interest, the fields and design variables cannot be trivially assumed as real-valued. Complex values are of course built into quantum dynamics. In electromagnetism, open boundaries require complex-valued fields (e.g., through perfectly matched layers). Plasmonic structures require loss. Perhaps the one exception is the calculation of modes of closed, periodic systems (e.g. photonic crystals), for eigenstate properties. For any scattering problem with a source, however, the power from the source must be dissipated in either the material or into far-field radiation, with complex-valued fields as a result.

The formulation of Ref. [13] does not lead to a design QCQP when the fields are complex-valued. In order to transform the original, complex-valued physical design equation to a real-valued form of the type of Eq. (82), one must perform a standard doubling of the dimensions of the vectors and matrices, separating the real and imaginary parts of all variables involved. (See Ref. [16] for detailed descriptions of these steps.) This leads to a vector θ\theta of design variables that is twice as large as the number of degrees of freedom, and within which the first and second halves of the vector should be equal. Such a constraint is a pain to enforce, however (it possibly could be enforced by the methods of Ref. [17], and instead is dropped in [13, 16]. Hence, that approach leads to a relaxed QCQP that can be used for bounds, but not a QCQP formulation of the design problem, as proposed in the main text.

References

  1. [37]J. Peurifoy, Y. Shen, L. Jing, Y. Yang, F. Cano-Renteria, B. G. DeLacy, J. D. Joannopoulos, M. Tegmark, and M. Soljačić, Nanophotonic particle simulation and inverse design using artificial neural networks, Science advances 4, ea arXiv:ear4206 (2018).DOI
  2. [38]J. Jiang and J. A. Fan, Global optimization of dielectric metasurfaces using a physics-driven neural network, Nano letters 19, 5366 (2019).DOI
  3. [39]M. Raissi, P. Perdikaris, and G. E. Karniadakis, Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations, Journal of Computational physics 378, 686 (2019).DOI
  4. [40]Y. Kiarashinejad, S. Abdollahramezani, and A. Adibi, Deep learning approach based on dimensionality reduction for designing electromagnetic nanostructures, npj Computational Materials 6, 1 (2020).DOI
  5. [41]Z. Yu, A. Raman, and S. Fan, Fundamental limit of nanophotonic light trapping in solar cells, Proc. Natl. Acad. Sci. U. S. A. 107, 17491 (2010).DOI
  6. [42]O. D. Miller, A. G. Milleridis, M. T. H. Reid, C. W. Hsu, B. G. Delacy, J. D. Joannopoulos, M. Soljačić, and S. G. Johnson, Fundamental limits to optical response in absorptive systems, Optics Express 24, 3329 (2016).DOI
  7. [43]O. D. Miller, S. G. Johnson, and A. W. Rodriguez, Shape-independent limits to near-field radiative heat transfer, Physical Review Letters 115, 204302 (2015).DOI
  8. [44]J.-P. Hugonin, M. Besbes, and P. Ben-Abdallah, Fundamental limits for light absorption and scattering induced by cooperative electromagnetic interactions, Physical Review B 91, 180202(R) (2015).DOI
  9. [45]Miller, O. D., Ilic, O., Christensen, T., Reid, M. T. H., Atwater, H. A., Joannopoulos, J. D., Soljačić, M., & Johnson, S. G. (2017). Limits to the optical response of graphene and two-dimensional materials. Nano Letters, 17, 5408.
  10. [46]S. Sanders and A. Manjavacas, Analysis of the limits of the local density of photonic states near nanostructures, ACS Photonics 10.1021/acsphotonics.8b00225 (2018).DOI
  11. [47]H. Zhang, C. W. Hsu, and O. D. Miller, Scattering concentration bounds: Brightness theorems for waves, Optica 6, 1321 (2019), 1810.02727.DOI
  12. [48]H. Shim, L. Fan, S. G. Johnson, and O. D. Miller, Fundamental Limits to Near-Field Optical Response over Any Bandwidth, Phys. Rev. X 9, 11043 (2019).DOI
  13. [49]S. Molesky, P. Chao, W. Jin, and A. W. Rodriguez, Global T operator bounds on electromagnetic scattering: Upper bounds on far-field cross sections, Phys. Rev. Res. 2, 033172 (2020).DOI
  14. [50]Gustafsson, M., Schab, K., Jelinek, L., & Capek, M. (2020). Upper bounds on absorption and scattering. New Journal of Physics, 22, 073013.
  15. [51]R. Trivedi, G. Angeris, L. Su, S. Boyd, S. Fan, and J. Vuckovic, Fundamental bounds for scattering from absorptionless electromagnetic structures, arXiv Prepr. arXiv2003.00374 , 1 (2020), arXiv:2003.00374.DOI
  16. [52]S. Molesky, P. S. Venkataram, W. Jin, and A. W. Rodriguez, Fundamental limits to radiative heat transfer: Theory, Phys. Rev. B 101, 35408 (2020), arXiv:1907.03000.DOI
  17. [53]Z. Kuang and O. D. Miller, Computational bounds to light–matter interactions via local conservation laws, Physical Review Letters 125, 263607 (2020), arXiv:2008.13325.DOI
  18. [54]S. Molesky, P. Chao, and A. W. Rodriguez, Hierarchical mean-field t operator bounds on electromagnetic scattering: Upper bounds on near-field radiative purcell enhancement, Physical Review Research 2, 043398 (2020).DOI
  19. [55]F. Presutti and F. Monticone, Focusing on bandwidth: achromatic metalens limits, Optica 7, 624 (2020).arxiv.org/abs/2001.10899
  20. [56]S. Li and C. W. Hsu, Thickness bound for nonlocal wide-field-of-view metalenses, Light: Science & Applications 11, 338 (2022).DOI
  21. [57]Miller, D. A. (2023). Why optics needs thickness. Science, 379, 41.
  22. [58]Yablonovitch, E. (1982). Statistical ray optics. J. Opt. Soc. Am., 72, 899.
  23. [59]Mandelstam, L., & Tamm, I. (1945). The Uncertainty Relation Between Energy and Time in Non-relativistic Quantum Mechanics. J. Phys. USSR, 9, 249.
  24. [60]Z. Kuang and O. D. Miller, Computational bounds to light–matter interactions via local conservation laws, Physical Review Letters 125, 263607 (2020).DOI
  25. [61]H. Zhang, Z. Kuang, S. Puri, and O. D. Miller, Conservation-law-based global bounds to quantum optimal control, Physical Review Letters 127, 110506 (2021), arXiv:2105.06054 [quant-ph].DOI
  26. [62]G. Angeris, T. Diamandis, J. Vučković, and S. Boyd, Bounds on efficiency metrics in photonics, arXiv preprint arXiv:2204.05243 (2022).arXiv
  27. [63]Sahni, S. (1974). Computationally related problems. SIAM Journal on computing, 3, 262.
  28. [64]J. Park and S. Boyd, General heuristics for nonconvex quadratically constrained quadratic programming, arXiv preprint arXiv:1703.07870 (2017).arXiv
  29. [65]Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994). Linear matrix inequalities in system and control theory.
  30. [66]M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM) 42, 1115 (1995).DOI
  31. [67]Luo, Z.-Q., Ma, W.-K., So, M.-C., Ye, Y., & Zhang, S. (2010). Semidefinite relaxation of quadratically constrained quadratic optimization problems. IEEE Signal Process. Mag., 27, 20.
  32. [68]S. Sojoudi and J. Lavaei, Physics of power networks makes hard optimization problems easy to solve, in 2012 IEEE Power and Energy Society General Meeting (IEEE, 2012) pp. 1–8.DOI
  33. [69]Vandenberghe, L., Andersen, M. S., & al., . et . (2015). Chordal graphs and semidefinite optimization. Foundations and Trends® in Optimization, 1, 241.
  34. [71]Madani, R., Sojoudi, S., & Lavaei, J. (2014). Convex relaxation for optimal power flow problem: Mesh networks. IEEE Transactions on Power Systems, 30, 199.
  35. [72]Aieta, F., Kats, M. A., Genevet, P., & Capasso, F. (2015). Multi-wavelength achromatic metasurfaces by dispersive phase compensation. Science, 347, 1342.
  36. [73]A. Arbabi, Y. Horie, M. Bagheri, and A. Faraon, Dielectric metasurfaces for complete control of phase and polarization with subwavelength spatial resolution and high transmission, Nature nanotechnology 10, 937 (2015).DOI
  37. [74]O. Avayu, E. Almeida, Y. Prior, and T. Ellenbogen, Composite functional metasurfaces for multispectral achromatic optics, Nature communications 8, 14992 (2017).DOI
  38. [75]S. M. Kamali, E. Arbabi, A. Arbabi, and A. Faraon, A review of dielectric optical metasurfaces for wavefront control, Nanophotonics 7, 1041 (2018).arxiv.org/abs/1804.09802
  39. [76]Chung, H., & Miller, O. D. (2020). High-NA achromatic metalenses by inverse design. Optics Express, 28, 6945. 1905.09213
  40. [77]Kim, S., Kojima, M., Mevissen, M., & Yamashita, M. (2011). Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Mathematical Programming, 129, 33.
  41. [78]Liu, T., Sun, B., & Tsang, D. H. K. (2019). Rank-one solutions for SDP relaxation of QCQPs in power systems. IEEE Trans. Smart Grid, 10, 5.
  42. [79]Barahona, F., Grötschel, M., Jünger, M., & Reinelt, G. (1988). An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research, 36, 493.
  43. [80]S. Barahona and R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming 95, 329 (2003).DOI
  44. [81]Arora, S., & Kale, S. (2016). A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM (JACM), 63, 1.
  45. [82]N. Boumal, V. Voroninski, and A. Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs, Advances in Neural Information Processing Systems 29 (2016).arxiv.org/abs/1606.04970
  46. [83]Ding, L., Yurtsever, A., Cevher, V., Tropp, J. A., & Udell, M. (2021). An optimal-storage approach to semidefinite programming using approximate complementarity. SIAM Journal on Optimization, 31, 2695.
  47. [84]Comsol multiphysics. (n.d.). Comsol multiphysics.
  48. [85]Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1, 67.

Paper details

vlnc:W_d4detjmy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents