Florian Richoux
email: florian@richoux.frjf@baffier.fr

Jean-François Baffier

Philippe Codognet
email: codognet@is.s.u-tokyo.ac.jp

Learning qubo Models for Quantum Annealing: A Constraint-based Approach

Keywords: Quantum Annealing, QUBO, Machine Learning, Constrained Optimization Problems, Constraint Satisfaction Problems

Quantum Annealing is an optimization process taking advantage of quantum tunneling to search for the global optimum of an optimization problem, although, being a heuristic method, there is no guarantee to find the global optimum. Optimization problems solved by a Quantum Annealer machine are modeled as Quadratic Unconstrained Binary Optimization (qubo) problems. Combinatorial optimization problems, where variables take discrete values and the optimization is under constraints, can also be modeled as qubo problems to benefit from Quantum Annealing power. However, defining quadratic penalty functions representing constraints within the qubo framework can be a complex task. In this paper, we propose a method to learn from data constraint representations as a combination of patterns we isolated in Q matrices modeling optimization problems and their constraint penalty functions. We actually model this learning problem as a combinatorial optimization problem itself. We propose two experimental protocols to illustrate the strengths of our method: its scalability, where correct pattern combinations learned over data from a small constraint instance scale to large instances of the same constraint, and its robustness, where correct pattern combinations can be learned over very scarce data, composed of about 10 training elements only.

Introduction

As Quantum Computing is getting more real with the effective development of quantum processors, one can distinguish two approaches: the gate-based paradigm, in which the main industrial players such as IBM, Google, Intel and many startup companies (IonQ, Rigetti, IQM, Pasqal, . . . ) have developed systems with up to a few hundreds of qubits, and the adiabatic computation paradigm, in which companies like D-Wave Systems have developed systems with thousands of qubits.

Quantum Annealing (QA) is an instance of adiabatic computation that is interesting in the current Noisy Intermediate-Scale Quantum (NISQ) era, and it has been applied in the field of combinatorial optimization. Indeed, combinatorial problems can be modeled as Quadratic Unconstrained Binary Optimization (qubo) as input language and solved by QA systems.

More complex Constrained Optimization and Constraint Satisfaction Problems, coming from the Constraint Programming or Operations Research domains, are now being tackled with qubo modeling and QA solving [START_REF] Codognet | Constraint solving by quantum annealing[END_REF], although the size of the current QA machines still prevent experiments on large instances. Nevertheless, an interesting issue which is appearing is the modeling of complex problems in the constraint-based approach, and, although it is easy to add penalties into the objective function to represent simple constraints appearing in the problem, it could be difficult to express in a qubo formulation the penalties corresponding to complex constraints as found in the Constraint Programming paradigm. Indeed, if some constraints are such as the one-hot or the permutation (two-way one-hot) constraints are easy to represent in qubo, as we illustrate in Section 3, this is not the case for more general constraints. Many classical combinatorial problems are usually modeled with integer variables and constraints over those integer variables. Thus, to transform those models into qubo, one has first to encode integer variables by binary variables (this is not difficult) and then to transform the constraints over integer values as penalties over binary variables, which may not be obvious at all. Therefore, an approach that would automatically create the qubo penalties corresponding to integer constraints would be valuable. We can do that by learning the qubo matrix representation corresponding to a constraint from the solution and non-solution candidates.

Learning constraints from data has been explored in different directions. Paulus et al [START_REF] Paulus | Comboptnet: Fit the right np-hard problem by learning integer programming constraints[END_REF] proposes to integrate a combinatorial optimization module directly into a neural network as a layer, learning both the constraints and their costs from data. Another approach is proposed by Kumar et al [START_REF] Kumar | Learning mixed-integer linear programs from contextual examples[END_REF], where the constraints and the objective function of Mixed-Integer Linear Programs are learned from data. However, unlike our work, these two papers deal with linear constraints only, and they both learn constraints on a fixed number of variables. In comparison, our method can handle linear and non-linear constraints, and it learns a constraint representation that is independent of the number of variables. This work is inspired from [START_REF] Richoux | Automatic error function learning with interpretable compositional networks[END_REF], where a method to learn error functions representing constraints is proposed. This paper describes a model, named Interpretable Compositional Network, to learn error functions as an interpretable composition of elementary operations, in such a way that the learned compositions are independent of the number of the target constraint. The main difference with this current paper is that error functions are not necessarily quadratic but must verify a structured property upon error values implying a hierarchy among non-solution candidates, which is not necessary in the present qubo setting.

Quantum Annealing and qubo

Quantum Annealing (QA) has been proposed as a concrete form of adiabatic computation more than two decades ago by Kadowaki et al. [START_REF] Kadowaki | Quantum annealing in the transverse Ising model[END_REF] and Farhi et al. [START_REF] Farhi | A quantum adiabatic evolution algorithm applied to random instances of an npcomplete problem[END_REF], and takes advantage of the physical phenomenon of quantum tunneling, allowing to traverse energy barriers in the energy landscape as long as they are not too large [START_REF] Tanaka | Quantum Spin Glasses, Annealing and Computation[END_REF][START_REF] Rajak | Quantum annealing: an overview[END_REF]. QA has gained momentum in the last decade with the development of special hardware based on QA, such as the quantum computers of D-Wave Systems [START_REF] Bunyk | Architectural considerations in the design of a superconducting quantum annealing processor[END_REF][START_REF] Mcgeoch | Practical annealing-based quantum computing[END_REF] and, more recently, the so-called "quantum-inspired" systems which are realized with classical (non-quantum) electronics by Fujitsu [START_REF] Aramon | Physics-inspired optimization for quadratic unconstrained problems using a digital annealer[END_REF], Hitachi [START_REF] Yamaoka | CMOS annealing machine: an in-memory computing accelerator to process combinatorial optimization problems[END_REF], Toshiba [START_REF] Goto | Combinatorial optimization by simulating adiabatic bifurcations in nonlinear hamiltonian systems[END_REF] or Fixstars Amplify [START_REF] Matsuda | Research and development of common software platform for ising machines[END_REF]. These systems are sometimes referred to as Ising Machines, as they can solve problems stated as Hamiltonians in the Ising model and are aimed to solve a large class of combinatorial problems [START_REF] Tanahashi | Application of ising machines and a software development for ising machines[END_REF][START_REF] Mohseni | Ising machines as hardware solvers of combinatorial optimization problems[END_REF], including industrial applications [START_REF] Yarkoni | Quantum annealing for industry applications: introduction and review[END_REF].

Interestingly, such a formulation is equivalent to the modeling in Quadratic Unconstrained Binary Optimization, a formalism whose roots go back to pseudobinary optimization in the late 60's and which has been proposed as a simple but powerful modeling language for combinatorial problems about 15 years ago [START_REF] Boros | Local search heuristics for quadratic unconstrained binary optimization (QUBO)[END_REF]. qubo is now seen as a general modeling language for a variety of combinatorial problems [START_REF] Kochenberger | The unconstrained binary quadratic programming problem: a survey[END_REF][START_REF] Glover | Quantum bridge analytics I: a tutorial on formulating and using QUBO models[END_REF]. For these reasons, qubo has become the standard input language for Ising machines.

Simply put, a qubo problem is given by a vector of n binary variables x 1 , • • • , x n and a quadratic expression over x 1 , • • • , x n that has to be minimized, which, without loss of generality, is of the form i≤j q ij x i x j . Therefore, a qubo problem is determined by a vector x of n binary decision variables and an upper triangular n × n square matrix Q with coefficients q ij . The qubo problem can thus be written: minimize y = x T Qx, where x T is the transpose of x.

Moreover, in order to use qubo to model Constrained Optimization Problems (cop) from the field of Operations Research, e.g., the well-known Traveling Salesman problem (TSP) or Quadratic Assignment Problem (QAP), one has to find a way to represent constraint expressions in qubo models. This can be done by using penalties and adding them in the objective function to minimize, that is, as quadratic expressions whose value is minimal when the constraint is satisfied. An easy way to formulate such a penalty is to create a quadratic expression which has value 0 if the constraint is satisfied and a positive value otherwise, representing somehow the degree of violation of the constraint.

Although this works fine for simple constraints, defining the penalties corresponding to complex constraints can, however, become complicated. This is the starting point of our work investigating an automatic manner to generate qubo penalties corresponding to complex constraints.

Motivating Example

Basic Example

Consider the problem of coloring the n nodes of a graph with k colors such that no adjacent nodes have the same color. The classical way to model such a problem in qubo is to consider, for each node i of the graph, k binary variables x ij , j ∈ {1, . . . , k} such that x ij = 1 if the node i has the color j, and

x ij = 0 otherwise.              
-1 2 2 0 0 0 0 0 0 0 -1 2 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 2 2 0 0 0 0 0 0 0 -1 2 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 -1 2 2 0 0 0 0 0 0 0 -1 2 0 0 0 0 0 0 0 0 -1

              Qc              
-1 1 1 1 0 0 1 0 0 0 -1 1 0 1 0 0 1 0 0 0 -1 0 0 1 0 0 1 0 0 0 -1 1 1 1 0 0 0 0 0 0 -1 1 0 1 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 -1 1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 -1

              Q ′ c
Fig. 1: qubo matrices corresponding to the penalties in Examples 1 and 2

Then, one has to devise an objective function that will be minimal when adjacent nodes have different colors. But the problem variables are also subject to the constraints that each node has only a single color, i.e., that k 1 x ij = 1. This is the well-known one-hot constraint: among k Boolean variables, exactly one has to be equal to 1 and others have to be equal to 0. It is classically used for the representation of integer variables with a domain of size n by n Boolean variables, although other encoding such as domain-wall or unary are possible [START_REF] Chancellor | Domain wall encoding of discrete variables for quantum annealing and QAOA[END_REF][START_REF] Codognet | Domain-wall / unary encoding in QUBO for permutation problems[END_REF].

Let us remark that

k j=1 x ij = 1 ⇐⇒ ( k j=1
x ij -1) 2 = 0, and by developing this expression, a quadratic penalty expression is obtained:

2 n i=1 j<j ′ x ij x ij ′ - n i=1 k j=1 x ij
This penalty has to be added to the qubo objective function of the original problem in order to enforce the original one-hot constraint of the initial problem.

Example 1 Consider a qubo model with 9 binary variables x ij , i ∈ {1, 2, 3}, j ∈ {1, 2, 3}, and an objective function f to minimize over x ij , subject to the three one-hot constraints:

3 j=1 x 1j = 1, 3 j=1 x 2j = 1, 3 j=1 x 3j = 1. The 9 × 9 qubo matrix Q can be decomposed as the sum Q = Q o + Q c , with
Q o being the 9 × 9 matrix corresponding to the objective function f , and Q c the 9 × 9 matrix corresponding to the three one-hot constraints. The Q c matrix representing the penalty is depicted in Figure 1.

The above transformation is straightforward, and the corresponding qubo penalty is easy to derive mathematically from the initial constraint (as is the qubo matrix), but this might not always the case.

More interestingly, we can see that the 9 × 9 matrix corresponding to the penalty part of the qubo model (i.e., the constraint part of the initial problem) shows a particular structure with 3×3 submatrix around the diagonal. Could the penalty part of the qubo matrix representing constraints coming from integer problems be seen as a combination of basic patterns such as submatrices? If so, could we learn automatically such matrix representation? We will see that the answer to both questions is "yes".

A More Complex Example

Let us consider now a slightly more complex example: permutation constraints. Many classical combinatorial optimization problems, such as the well-known Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP), or Constraint Satisfaction problems such as the N-queens and Magic Square puzzles are usually modeled with a vector of integer decision variables which are subject to the constraint that each feasible solution forms a permutation. In the Constraint Programming community, such a permutation constraint is a special case of the AllDifferent constraint, which has been the subject of large literature and various solving techniques [START_REF] Gent | Generalised arc consistency for the alldifferent constraint: An empirical survey[END_REF].

To enforce that n integer variables x i with values in {1, . . . , n} represent a permutation, we need to enforce that each value j ∈ {1, . . . , n} is assigned once and only once. When translated to qubo, with n binary variables x ij , j ∈ {1, . . . , n}, encoding an integer variable x i of the original problem formulation, this amounts to the so-called two-way one-hot constraints: 2 × n one-hot constraints with one set of n constraints corresponding to each of the n variables x i stating that it can have only one value k and one set of n constraints for each of the n values k stating that it can be assigned to only one variable x i .

These 2 × n one-hot constraints are as follows:

∀i ∈ {1, . . . , n}, n j=1

x ij = 1 ∀j ∈ {1, . . . , n},

n i=1 x ij = 1
Adding all corresponding penalty expressions together and simplifying the quadratic expression gives the following penalty for the permutation constraint:

n i=1 j<j ′ x ij x ij ′ + n j=1 i<i ′ x ij x i ′ j - n i=1 n j=1 x ij
Example 2 Consider a combinatorial problem on 3 integer variables x 1 , x 2 , x 3 , with values in {1, 2, 3} subject to a permutation constraint and an objective function f to minimize over x i .

If each original integer variable is encoded by 3 binary variables with one-hot encoding, the corresponding qubo model will have 9 binary variables x ij , i ∈ {1, 2, 3}, j ∈ {1, 2, 3}, and the 9 × 9 qubo matrix can be decomposed as the sum

Q ′ = Q ′ o +Q ′ c , with Q ′ o corresponding
to the translation of the objective function f to minimize over x ij , and Q ′ c corresponding to the permutation constraint. The Q ′ c matrix representing the penalty is depicted in Figure 1. This matrix is somewhat different from the one in Example 1, but a similar pattern of 3 × 3 submatrices around the diagonal can be observed, together with patterns on the lines.

Method Design

The main contribution of this paper is to propose a method to automatically learn from data a pattern composition representing a Q matrix, such that Q corresponds to a target constraint c. This method is directly inspired from the method proposed in [START_REF] Richoux | Automatic error function learning with interpretable compositional networks[END_REF], to learn error functions from data in an interpretable and scalable fashion. We call such a pattern composition a Q matrix representation. The data is the training set obtained from an instance of c, i.e., the constraint c over a fixed number of variables taking their values over domains of a fixed size.

Let's consider a constraint c and an instance ι of c. A candidate of ι is an assignment of all variables composing ι. A candidate is said to be positive if it satisfies c, and negative otherwise. We denote by S the set of all possible tuples (x, y), where x is a candidate of the constraint instance ι, and y ∈ {0, 1} describes if x is a positive or a negative candidate, such that

y = 1 if x is a positive candidate 0 if x is a negative candidate.
Giving some positive and negative candidates of instance ι of a constraint c, our goal is to learn a pattern composition representing a Q matrix corresponding to c, i.e., Q must verify the following property:

∀(x, y) ∈ S, x T Qx is minimal iff y = 1 (1)
Variables of discrete constraints take their value from a domain composed of integers. However, qubo problems are considering binary variables only. As written in the introduction, there are several ways to convert constraint variables into qubo variables: unary expansion, binary expansion, etc. In this work, we will only consider one-hot encoding: a constraint variable x i over a k-ary domain will be encoded by a k-dimensional binary vector, such that the j-th element x ij of this vector is set to true if and only if x i = j holds.

To represent a discrete constraint, Q can be composed of integers only. If we aim to represent a constraint over n variables x i taking their value in a k-ary domain, then, due to the one-hot encoding of the variables, Q is an upper triangular matrix of size nk × nk. Our method is based on learning a correct combination of submatrix patterns. The one-hot constraint is systematically added into this pattern combination.

Q being an upper triangular matrix, we consider two kinds of submatrices: k × k triangle submatrices containing the diagonal of Q and representing the properties of a variable x i , and k × k square submatrices representing properties between two variables x i and x j , with i ̸ = j.

Our method considers 14 square and 3 triangle submatrix patterns, depicted in Figure 2. Square submatrix patterns can be composed by summing their elements, however, we consider some square submatrix patterns to be mutually exclusive. Indeed, it would make not sense for instance to enforce both the properties x i = x j and x i ̸ = x j at the same time. Square patterns 12, 13, 14, and triangle pattern 3 take some parameters. It is important to keep in mind that submatrices and their patterns are on binary variables.

We can divide square submatrix patterns into 3 categories:

• Comparison patterns from Square 1 to 6, representing some comparison properties between x i and x j . For instance, x i ̸ = x j (Fig. 2a). • Position patterns from Square 7 to 11, encoding properties such that the values of the i-th and j-th variables x i and x j depend on their respective position i and j. For instance, favoring x i = i and x j = j (Fig. 2g). • Complex patterns for Square 12, 13 and 14. For instance, the repel property described in the next paragraph (Fig. 2l).

Due to the page limitation, we chose not to explain all patterns. Instead, we focus here on the less trivial ones. For Square pattern 14 (Fig. 2n) and triangle pattern 3 (Fig. 2q), b xi represents the coefficient of the variable x i in a linear combination b xi x i = a. Square patterns 12 (Fig. 2l) and 13 (Fig. 2m), respectively called repel and attract, take a parameter p. These patterns look like a diagonal magnetic field with an intense value p in its center (repel) or on its borders (attract), which decays towards the borders (repel) or the center (attract). This is illustrated in Figure 2 with p = 3. The intuitive idea behind these patterns is that variables x i and x j are repelling or attracting each others, until their values are separated by at least a distance p, such that |x i -x j | > p holds (repel), or until they are closed enough, below a k -p threshold, such that

|x i -x j | < k -p holds (attract).
Consider the function m determining if a candidate x is such that x T Qx is minimal or not:

m(x, Q) = 1 if x T Qx is minimal, 0 otherwise.
Learning a correct combination of submatrix patterns from a training set X ⊆ S is a machine learning problem, but it can also be tackled as a combinatorial problem. We modeled this as a Constrained Optimization Problem (cop) described in Table 1.

We have 14 binary variables to describe which square patterns are combined to give a global pattern for square submatrices, and one variable over a ternary domain indicating which pattern is selected for triangle submatrices. Thus, all square submatrices together will share the same pattern, as well as all triangle submatrices. Although our method still works if we decide to combine different patterns for each submatrix individually, this way of doing has the advantage of learning the Q matrix representation quicker. Moreover, it is motivated by the fact that natural constraints in Constraint Programming usually apply the same property over all variables in their scope (for instance, all variables must be assigned to a different value). If it is not the case, then the target constraint can certainly be decomposed into a series of smaller constraints. For instance, let's assume we work with the constraint c(x 1 , x 2 , x 3 ) := "x 1 + x 2 + x 3 = 5 such that x 1 < x 2 holds". Here, x 1 and x 2 have a property x 1 < x 2 that is not shared by x 3 . But the constraint c can be decomposed into two constraints

      1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1       (a) Square 1 xi ̸ = xj       0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0       (b) Square 2 xi = xj       0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0       (c) Square 3 xi ≤ xj       1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1       (d) Square 4 xi < xj       0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0       (e) Square 5 xi ≥ xj       1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1       (f) Square 6 xi > xj       0 0 0 -1 0 -1 -1 -1 -1 -1 0 0 0 -1 0 0 0 0 -1 0 0 0 0 -1 0       (g) Square 7 Favor xi = i       0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0       (h) Square 8 Avoid xi = i       -1 0 -1 0 -1 0 0 0 0 0 -1 0 -1 0 -1 0 0 0 0 0 -1 0 -1 0 -1       (i) Square 9 Favor xi, xj ̸ = {i, j}       1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1       (j) Square 10 Avoid xi, xj ̸ = {i, j}       0 0 0 1 0 1 1 1 -1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0       (k) Square 11 Swap xi, xj       3 2 1 0 0 2 3 2 1 0 1 2 3 2 1 0 1 2 3 2 0 0 1 2 3       (l) Square 12 Repel       0 0 1 2 3 0 0 0 1 2 1 0 0 0 1 2 1 0 0 0 3 2 1 0 0       (m) Square 13 Attract   2bx i bx j 2bx i bx j+1 2bx i bx j+2 2bx i+1 bx j 2bx i+1 bx j+1 2bx i+1 bx j+2 2bx i+2 bx j 2bx i+2 bx j+1 2bx i+2 bx j+2   (n) Square 14 Linear combination       0 0 0 0 0 0 0 0 0 0 0 0 0 0 0       (o) Triangle 1 Neutral       -1 0 0 0 0 -1 0 0 0 -1 0 0 -1 0 -1       (p) Triangle 2 Favor xi   -(2a-bx i )bx i 2bx i bx i+1 2bx i bx i+2 -(2a-bx i+1 )bx i+1 2bx i+1 bx i+2 -(2a-bx i+2 )bx i+2   (q) Triangle 3 Linear combination
Fig. 2: Submatrix patterns used in our method, with their property. Simple examples are displayed with k = 5; complex examples (n) and (q) with k = 3.

c 1 (x 1 , x 2 , x 3 ) := x 1 + x 2 + x 3 = 5 and c 2 (x 1 , x 2 ) := x 1 < x 2
, where all variables in their scope share the same properties.

Like expressed above, we forbid some square pattern combinations: We cannot have more than one square pattern from Square 1 to Square 6 in the combination, and couples of patterns Square 7 -Square 8, Square 9 -Square 10, and Square 12 -Square 13 are mutually exclusive. The 4 first constraints in Table 1 are here to forbid such combinations.

Table 1: cop model to learn Q from data X ⊆ S Variables v f 1 , . . . , v f 14 , v h One variable v f i for each possible square pattern i, a unique variable v h for the triangle pattern.

Domains D f i = {0, 1}, with 1 ≤ i ≤ 14 D h = {1, 2, 3} Constraints 6 i=1 v f i ≤ 1 v f 7 + v f 8 ≤ 1 v f 9 + v f 10 ≤ 1 v f 12 + v f 13 ≤ 1 (x,y)∈X |m(x, Q) -y| = 0
Objective function min 14 i=1 v f i , minimizing the number of (square) submatrix patterns in the composition.

The fifth constraint in our cop model makes sure the learned Q matrix representation can correctly handle all positive and negative candidates from the training set X.

One strength of this model is its independence regarding the size of the target constraint instance: whatever the size of the data, i.e., the number of variables in candidates or the size of the domains, our model will still be composed of 15 variables to express any pattern combinations describing any constraints. This makes our model scalable, allowing the learning of a Q matrix representation over a small instance of a constraint c that is valid for all instance sizes of the same constraint, as shown in Experiment 1.

Experiments

To show the versatility of our method, we tested it on five different constraints: AllDifferent, Ordered, LinearSum, NoOverlap1D, and Channel. Following the XCSP 3 -core specifications † [START_REF] Boussemart | XCSP3-core: A format for representing constraint satisfaction/optimization problems[END_REF], those global constraints belong to four major constraint families: Comparison (AllDifferent and Ordered), Counting/Summing (LinearSum), Packing/Scheduling (NoOverlap1D) and Connection (Channel). These constraints are also among the 25 most popular and common constraints [START_REF] Boussemart | XCSP3-core: A format for representing constraint satisfaction/optimization problems[END_REF]. We give a brief description of those five constraints below:

• AllDifferent ensures that variables must all be assigned to different values.

• Ordered ensures that an assignment of n variables (x 1 , . . . , x n ) must be ordered, given a total order. In this paper, we choose the total order ≤. Thus, for all indices i, j ∈ {1, n}, i < j implies x i ≤ x j . • LinearSum ensures that the equation x 1 + x 2 + . . . + x n = p holds, with the parameter p a given integer.

• NoOverlap1D considers variables as tasks, starting from a certain time (their value) and each with a given length p (their parameter). The constraint ensures that no tasks are overlapping, i.e., for all indices i, j ∈ {1, n} with n the number of variables, we have x i + p i ≤ x j or x j + p j ≤ x i . To have a simpler code, we have considered in our system that all tasks have the same length p. • Channel ensures that the i-th variable x i assigned to j with j ̸ = i implies that x j is assigned to i. In other words, Channel accepts all permutations of the vector (1, . . . , n) such that each variable has been swapped with another variable at most once.

Experimental protocols

We set up two different experimental protocols to show the scalability, the robustness, and more globally, the efficiency of our method. Like presented in Section 4, learning pattern compositions of Q matrices from data is handled as a combinatorial optimization problem. To model and solve this problem, we use the framework ghost [START_REF] Richoux | GHOST: A combinatorial optimization framework for real-time problems[END_REF] which runs a stochastic local search solver to solve problems. Due to this stochastic solving, all learning and testing have been done 100 times, but over the same pre-computed training sets, to not let the randomness of sampled sets impact the results in some way. Training and test sets that are too large to be complete have been pre-computed using Latin hypercube sampling to have a good diversity among drawn candidates. These sets have been generated such that they contain an equal number of positive and negative candidates. ghost's solver requires a timeout, such that it tries to improve the best solution found until it reaches the given timeout. We set it to 1 second. We did not fine-tune the solver parameters, running our experiments with their default values. In addition to our two experiments, we did 100 runs for each training set of Experiment 1 and 2 disabling the objective function, to see how fast our method can find a correct Q matrix representation. Indeed, without an objective function, ghost's solver does not take into account the timeout and halts as soon as it finds a solution satisfying all constraints in the cop model.

We have hold-out test sets of assignments from larger dimensions to evaluate the quality of our learned Q matrix representations. We did not re-run batches of experiments to keep the ones with the best results, as it should always be the case with such experimental protocols.

All experiments have been done on a computer with a Core i9 9900 CPU and 32 GB of RAM, running on Ubuntu 22.04.2. Programs have been compiled with GCC with the 03 optimization option. Our entire system, its C++ source code, and experimental setups are accessible on Zenodo § and GitHub.

Experiment 1: scalability One of the key-points of our method is that we can learn the pattern composition of a Q matrix from data about a small instance § https://doi.org/10.5281/zenodo.7800168 of a constraint c, i.e., over few variables and small domains, which gives us the blueprint to build Q matrices handling large instances of c.

In this experiment, we learn Q matrix representations upon complete training sets composed of all possible tuples (x, y), with x a candidate of the target constraint instance and y the binary value indicating if x is a solution of the constraint or not, as explained at the beginning of Section 4. These small, complete training sets are built considering constraint instances with 4 variables over domains of size 4, giving complete training sets with 256 candidates, except for the constraint NoOverlap1D for which such an instance size does not make sense.

The training set for NoOverlap1D takes into account 3 variables over domains of size 7 (and with a parameter p = 2 for the length of each task), leading to a training set with 7 3 = 343 candidates. The parameter p of the LinearSum constraint instance was fixed to 10, giving the constraint

4 i=1 x i = 10, with x i ∈ {1, . . . , 4}, 1 ≤ i ≤ 4.
To test both the scalability of our method, we test the learned matrix representations over significantly larger constraint instances, with 30 variables over domains of size 30. Indeed, a learned composition can be represented by a vector of 15 elements, one for each variable of our cop model, independently of the size of the Q matrix and the constraint instance it represents. Those test sets containing too many candidates (30 30 ≃ 2 × 10 44 ) to be fully tested or even fully generated, we build them in order to get exactly 10,000 build positive and 10,000 drawn negative candidates, giving 20,000 unique candidates. Once again, we need to make an exception for NoOverlap1D due to the nature of this constraint. Its test set is then composed of 10,000 built positive and 10,000 drawn negative candidates of a constraint instance with 20 variables and domains of 160 elements (with p = 6), giving a space of 160 20 ≃ 1.2 × 10 44 candidates. Q matrices built for these test sets are then of size 900 × 900, except for NoOver-lap1D which has a Q matrix of size 3200 × 3200, going to the limit of what current Quantum Annealing machines can handle nowadays. All test sets are pre-generated, i.e., sampled once and kept for all experiments.

Experiment 2: robustness In Experiment 1, we learn pattern compositions of Q matrices to represent constraint instances over complete training sets, i.e., composed of all possible candidates. However, providing such complete sets to learn Q matrix representations may not always be convenient. To test the robustness of our method, we learn Q matrix representations over training sets of constraint instances that are too large to be completely generated in a reasonable time: 12 variables over domains of 12 elements (12 12 ≃ 9 × 10 12 ). Instead, we sample 5 positive and 5 negative candidates only in such spaces, then we test the learned Q matrix representations on the same test sets than for Experiment 1. For NoOverlap1D, we sample 5 positive and 5 negative candidates of an instance with 8 variables over domains of 35 elements (and p = 3), leading to a space composed of 35 8 ≃ 2.2 × 10 12 candidates.

In addition, we also tested how restricted training sets can be until we observe significant efficiency drops. For this, we repeated this experimental protocol with

Experimental results

Table 2 shows the number of times, over 100 runs and for each target constraint, a Q matrix representation has been learned and corresponds to a correct Q matrix, i.e., satisfying the property of Equation 1 over tuples (x, y) of the constraint test set. This first line corresponds to the results of Experiment 1, demonstrating that our method perfectly scales, learning Q matrix representation over small training sets of about 300 candidates and successfully tested over 20,000 randomly drawn candidates from a huge candidate space of about 2×10 44 candidates. The second line is the results of Experiment 2. It shows that our method is able to learn correct Q matrix representations from very sparse data: here, we learn Q matrix representation from 5 positive and 5 negative candidates, randomly drawn from candidate spaces of about 9 × 10 12 candidates. All learned Q matrices shown themselves to be correct on test sets, except 3 times for NoOverlap1D. Indeed, for these 3 times, the solver has been trapped into some local optimum, finding a correct pattern composition for the training set but containing unnecessary patterns, that lead to incorrectly handled candidates in the NoOverlap1D test set. More specifically, almost all positive candidates from the NoOverlap1D test set were incorrectly handled and considered as negative candidates. Having false negatives is indeed more frequent than false positive because a positive candidate x p with any values of x T p Qx p above the expected minimal value will be considered to be a negative candidate, but mistaking a negative candidate x n as a positive one requires having x T n Qx n to be equals to the expected minimal value. Having a value x T n Qx n below the expected minimal value in the test set is unlikely because it would imply that all positive candidates would be considered as false negatives.

These three incorrectly learned Q matrix representations for NoOverlap1D is not a serious problem in practice: users can get around this problem either by considering more candidates in the training set, or setting a timeout longer than 1 second to let the solver more time to find an optimal solution, or finally in the worst case, running again the learning. Since learning a Q matrix representation only takes one second in our current setup, users can easily afford re-learning a Q matrix representation if the first learning outputs an incorrect one. Learned Q matrix for the Channel constraint In Experiment 2, we learned Q matrix representation from training sets composed of 5 positive and 5 negative candidates. We tested how many candidates were needed to correctly learn pattern compositions for our different constraints. Table 3 sums up these trials, showing the success rate over 100 runs of representation learning with training sets of size n, with n 2 positive and n 2 negative candidates. Unsurprisingly, we can see no correct representations can be learned with one positive and one negative candidate only. However, four balanced candidates is sufficient to perfectly learn the Q matrix representation of the constraints Ordered and LinearSum.

Figure 3 illustrates a Q matrix obtained with our method, for the Channel constraint with 4 variables over domains of size 4, and the patterns that are taking part of the learned combination. The one-hot constraint is not depicted as a pattern in this figure, but it is always implicitly added in the combination.

Conclusion

In this paper, we presented a method to learn a pattern composition representing the penalty part of a qubo matrix, which can be difficult to do manually for complex constraints. We showed that this can be done with a limited set of examples and, via two experimental protocols, that our method has excellent scalability and robustness properties.

The current limitations of our method is the incapacity to handle ancillary variables. Indeed, some constraints require additional binary variables that do not directly represent integer variables from the target constraint, but are necessary to model some interactions between integer variables. Adding automatically the right number of ancillary variables to handle constraints like Element or NValues would be a natural extension of our work.

A second limitation is the lack of input size-dependent patterns, such as the size of domains, for instance. Such patterns would be greatly helpful to model some constraints like Minimum, seeing their satisfaction depending on some fixed values, without having a combinatorial explosion of the number of patterns that could severely hurt the learning efficiency. However, defining such generic and input size-dependent patterns might be challenging.

Fig. 3 :

 3 Fig. 3: Q matrix for Channel and patterns in the learned composition.

Table 2 :

 2 Success rates over 100 runs on test sets. Timeout is fixed at 1s for each run.

	Experiment AllDifferent Ordered LinearSum NoOverlap1D Channel
	1	100	100	100	100	100
	2	100	100	100	97	100
	training sets composed of 2, 4, 6, 8, 10 and 12 candidates, each time with half
	positive and half negative candidates. Like test sets, these training sets are pre-
	generated.

Table 3 :

 3 Success rate over 100 runs on test sets, regarding the size of the incomplete training sets. Timeout is fixed at 1s for each run.

	Nb candidates AllDifferent Ordered LinearSum NoOverlap1D Channel
	12	100	100	100	92	100
	10	100	100	100	96	100
	8	37	100	100	97	100
	6	33	100	100	92	10
	4	27	100	100	39	10
	2	0

† see also http://xcsp.org/specifications


Charles Busch

playwright, actor, director, novelist, cabaret performer He

John L Gassner

is the author and star of over twentyfive plays including The Divine Sister, The Lady in Question, Red Scare on Sunset, The Tribute Artist, The Confession of Lily Dare and Vampire Lesbians of Sodom, one of the longest running plays in the history of Off-Broadway. His play The Tale of the Allergist's Wife ran for 777 performances on Broadway, won the Outer Circle Critics'

thought that was all so marvelous but in a certain sense ultimately, you don't need to have gay restaurants because every restaurant is sort of gay, or gay theater. Unfortunately, for something like with gay bookstores, gay bookstores were a really good meeting place for people and there was a flowering of gay fiction in the early '80s. I think now it's very difficult for gay books -it's difficult for any book, but particularly gay books, to find a place at Barnes & Noble or wherever bookstores are. We're back to serve one shelf.

CK: Yes, I think there's only one gay bookstore left in New York. But there are very few bookstores left. Charles Busch: There's no bookstores anyway, for anyone, yes. So I was used to this separation: gay people only go to gay bars and gay restaurants and all that. And it was interesting to me at The Limbo Lounge was that it seemed quite gay, but maybe not necessarily and they were kind of goth and kind of punk and sort of gay but maybe sort of straight. It was just so interesting because I wasn't used to it, I was used to being segregated. It amused me too, to overhear the conversations around me, you would have fit in perfectly because everyone had a little bit of an accent that they were faking. All these American kids were [accent] sort of talking with a slight accent. Where the hell are they from? Pittsburgh! It seemed that they were all artists speaking in this kind of way. It was very interesting, so I can't separate the performance from the venue : the whole thing fascinated me.

CK: If I understand correctly, what you're saying is all this atmosphere also had an impactor some impact -on the freedom [in writing and performing]. So do you think that the gentrification that followed afterwards, in the East Village and Manhattan in general during the '90s for example, had an impact on the theater? Charles Busch: Yes, everything in New York City is influenced by rent. And so gay neighborhoods are all about cheap rent and young people finding some neighborhood that hasn't been gentrified yet. And then gay people make it popular and then the rents go up and they move somewhere else. And now of course there's no place to go, except maybe Brooklyn, but even Brooklyn is gentrified too. Alphabet City, far East Village, had very cheap rent. No one lived there so artists could go and eventually it got gentrified and too expensive, but I guess some people still find some pretty crummy places to live there. But does gentrification change art? A neighborhood like Alphabet City or Greenwich Village, years before, were because artists need cheap rent, therefore wherever they go, it becomes attractive for richer people to come in and then the art leaves.

CK: Also if you have rent to pay, you may be more prone to making some compromises in your work so that you can meet the standards that will make you be able to pay rent. Charles Busch: I don't know if I agree with that. But often in a career, people start off much edgier and then they get seduced or their goal is more mainstream ultimately. But I don't think people change their art to fit the neighborhood.

CK: You've written two plays, Red Scare on Sunset and The Lady in Question, that were, of course, the perfect vehicle for you to embody this old Hollywood glamour. Red Scare on Sunset even borrows subject material from '40s anti-communist cinema, so is this where the political aspect of these plays comes from or was there a deliberate statement that you wanted to make? Charles Busch: I loved those movies, anti-nazi war movies, so The Lady in Question was really a hommage to Hollywood patriotism which tried to make certain political points here and there, but I'm not really a political writer.

CK: The political stakes were very clear.

Charles Busch: There were certain things at the time, I think President Reagan went to Bitburg Cemetery in Germany, so I made a little satyrical joke about that. I'm such a nonpolitical writer that when I tried to do these things, I'm such a lame brain! During that time that I wrote Lady in Question there was a lot of new-age philosophy, which was very big at the end of the '80s, about how we create everything, how we create our own reality so there was little bit of satyre in that with my character.

CK: This is a line that keeps returning when Kitty gets hung. Charles Busch: So we wanted to make a little bit of statement about what was going on at the day. However, Red Scare really did have a political point of view, which was rare for me. It's my most complex play and that came out of actually just a backstage conversation with my leading man during Lady in Question. There was a line where he's saying to me he's very pro-Stalin, because there was a brief period in the '40s where we were with Russia against Hitler. And I said, "Arnie, if we ever did the sequel, your character would be in terrible trouble just a few years later for being a communist sympathizer". That got me thinking about Red Scare and the McCarthy era which has always interested me. So I started thinking about it but I didn't really see much humor in making it about it a leftist person who's hounded out of their career. It didn't seem terribly amusing but I thought it would be interesting to flip it and make it this right-wing nightmare. What if everything that the right-right thought of Hollywood was totally true and this actress, to her horror, sees this conspiracy around her and everybody's involved? I thought there could be exaggerated fun in that as opposed to doing it from the leftist point of view. And also I thought -and it's certainly quite relevant today -I did think it was interesting that with gay people that both right and left -the extreme right and the extreme left -had trouble with the idea of homosexuality.

CK: Exactly.

Charles Busch: And both extreme sides would like to curtail personal freedoms and of course as we see today with -I hate using the word "woke" because it's used against us by the right -but there is this feeling of both extremes that don't want any conversation.

CK: It is well pointed-out in the play as well. Charles Busch: That was just interesting… Michael Feingold, who passed away recently, wrote for the Village Voice -Village Voice never was really helpful to me at all. In forty years, I only got two good reviews and one of them was Red Scare and he wrote so eloquently about it. His review helped me understand what I wrote: it was all there, but he articulated it. It was such a complex, intellectual review. I showed it to my aunt and she said, "Your play really has all that in it?". I said, "Yes, I think it does!". That was it really. One could say I'm a political writer just by… CK: Definition. Charles Busch: Yes, I shake things up by the gender complexity of what I do.

CK: Even Vampire Lesbians of Sodom has political elements in it if you think about it. Charles Busch: Sometimes it frustrated me a bit back in the day. I thought my plays are actually more interesting than I was given credit for because I was doing it in camp.

CK: You mean the press?

Charles Busch: The critics, yes.

CK: Because otherwise the public was crazy about, not only about Vampire Lesbians of Sodom, but that was a huge hit. Charles Busch: But I'm saying intellectually I sometimes felt that critics didn't give me much credit for being too intelligent. It was mostly, "Oh, he did 'Hooray for Hollywood', he loves old movies and he's really funny, and it's camp, but kind of brainless". Sometimes it frustrated me because if they would take the trouble to look, I'm smarter than you think. They couldn't get past the camp humor.

CK: And it's still the case for not only you but others : if you're categorized as camp, you're done. They don't have anything else to say other than that.

Charles Busch: It's easy to label you and the fact too that, I was presenting a glamorous image of drag. So much of our style, as drag performers, comes from who our "physical presence" is. Charles Ludlam who came just before me was a big influence on me. He had very masculine features and that was not pretty and therefore there was no element of illusion going on there; that was not what he was about, that was not what he was selling. When I first started doing drag in college, just the fact that I'm small and have regular features, in drag I could approximate what the lady that I was trying to be [looked like]. I could give the illusion of Norma Shearer or Garbo or these different people. That interested me. I was also interested in costume design. Therefore, my style of drag play had more of a kind of realism to it. The cast looked like what they were supposed to be, the set, the actors, everything looked like they would fit in to a 1940s movie. And then we could go off and exaggerate and do a bit more vulgar or bawdy. But we gave the illusion of the old movie.

CK: This is exactly what I was going to ask you. Charles Ludlam said once that in auditions he was always told that his playing was "too gay", so what he did was start writing roles for himself. Charles Busch: That's what inspired me: seeing him.

CK: You also wrote plays for yourself and the troupe. But what that your motive as well? To write roles that you wouldn't otherwise be given in, say, commercial theater?

Charles Busch: My dream was to be an actor, to be onstage. Trying to think back, there really never were roles that I dreamed of playing. I just wanted to be onstage but I never really was cast in anything. But I got into this very good university, the Northwestern, in the Theater Department, but again I was never cast in a play, I was just too -I guess -effeminate and androgynous. There really were, for the most part, no roles I wanted to play that I thought I was right for. There was no gay literature, there were no plays like Torch Song [Trilogy]. It was too soon for me to say, "Oh, I could play Arnold", and "I could play Prior", "I could play solo-show Buyer & Cellar, I could do that" but those hadn't been written yet. Boys in the Band, people were doing that... I first saw Ludlam, when I was in high school, because I grew up here and then I started seeing him regularly and it was like being awakened from slumber.

CK: It opened perspectives.

Charles Busch: Yes, to see that this guy was creating roles for himself and for his company according to his own esthetic, which I seemed to share, of classic film and opera and 19th century theater, all these things that I was fascinated by and that he was taking elements from. Men playing female characters: I'd never seen that before! All the options of creating your own theater. I grew up going to Broadway shows since I was 7 years old. But they were very traditional musicals and plays and then to see Ludlam... And then, to a lesser degree, there were other avant-garde companies too. But with Ludlam it was like, "This is who I am!". But there were other things too: The Performance Group, where it was somebody's vision that is so personal and has nothing to do with commercial theater. It was an awakening. I'd always written: I was writing full-length plays at 11 years old. I completely understand why it took me all the way to 19 years old to figure out that this is what I should be doing! But Ludlam's example made it clear that I am a writer and so I should write roles for myself.

CK: It made it legitimate. Charles Busch: Yes, but it made it a possibility.

CK: Yes, that what I'm saying.

Charles Busch: It turned me, at a very early age, away from the idea that theater has to be a commercial thing, that my goal must be to win a Tony award or my goal is to be on Broadway. Right away I started not thinking in those terms at all but just doing something kind of marvelous and giving myself wonderful opportunities to be onstage and live out fantasy roles and all that.

CK: Like other drag artists, you don't mention AIDS in any of you plays, even though you describe Mamacita's final days in Whores of Lost Atlantis.

Charles Busch: I mostly did period pieces. I don't think I ever did a contemporary play during the AIDS crisis. It could have, I guess, infiltrate in a period piece but I was so busy living it. I think my plays back then with Theatre Limbo were an escape for me as well as for the audience. That was our war, that was our World War II.

CK: I kept thinking about specifically Vampire Lesbians of Sodom that there were several elements that could -perhaps -point to AIDS, because these were vampires, the connection with blood and the myriad lovers each of them had. I've scrutinized the play but I'm still not sure. Charles Busch: We can always find something in anything, but it certainly was not my intention at all. That's an interesting question though. I don't think any of my plays could be an AIDS metaphor -it really would be stretching it. But I see where one could try to go down that path with Vampire Lesbians of Sodom but frankly, the blood aspect of vampirism never interested me at all. It was just more the idea of eternal life that amused me and the concept that these characters are actresses first, vampires second. Their career was all that mattered, with their competitiveness they would be like Bette Davis and Joan Crawford but instead of being 30 years, it's 2000 years. I was interested in the idea of stardom and actresses that go on to have long careers and have to keep evolving and changing their images to suit the times. If you look at someone like Joan Crawford who kept evolving from being sort of a "jazz baby" to the '30s tortured kind of shopgirl, to becoming stronger and more indomitable in funny horror movies as the last stop. I was always intrigued by it, so therefore, I could make them vampires, so they were always adjusting to the 17the century, 19th century, the 20th...so that was fun. The decade of AIDS seemed to really involve my life, my world from '82 to '95 approximately. It was so terrifying when we first would hear about it. There came a rumor, [low voice] "Did you hear that guy, that bartender, the handsome one, the real cute bartender with the Duplex, yeah somebody said he just like died, all of a sudden his body fell apart", and then, "Oh, did you hear, that publicist was very ill, did you hear he died?" and it kept getting closer and closer. Then it finally hit our company: our leading lady died, Meghan [Robinson] and Bobby Carey, our beautiful young man and our choreographer… it just became part of our lives. Any of my plays with our company I think became a great source of escape for the gay community at that time because they had something to laugh about. Suddenly the baths were closed, and just prior to AIDS there was such an S/M-backroomscene and now they were closing or it just wasn't very cool. Gay men were looking for just another outlet that was non-sexual and our plays, I think, offered an escape.

CK: And for all of you involved as well.

Charles Busch: And for us. These two hours onstage, we were, the audience and the actors, in a collective dream/escape.

CK: Have you got a thing about red? Charles Busch: [Laughs] Why?

CK: Because I see these flaming red walls and you also play these -almost always -redheads… Charles Busch: One of the first movies I saw was Gone with the Wind and Belle Watling, the bordello owner, with her red hair and Scarlet in a red velvet dress when she goes to Melanie's party… I think in Belle Watling's bordello there was a lot of red. I was very impressionable toward color as a kid and the movies that I saw that made such an impact on me often were colored films of the movie Gipsy -I remember the vivid colors. I was always attracted to Chinese red, the red in the movie Gigi, all that seemed so lush. I was fascinated as a kid by bordellos and brothels basically from movies but also seen in the paintings of [Toulouse-] Lautrec. I always wanted to live in a place that looked like a brothel [laughs]. It all seemed so glamorous and vivid -and now I do! [laughs] CK: Ah! That explains a few items! [laughs] It all makes sense now! Charles Busch: I keep adding more and more red -it's opulent and romantic and intense. I wouldn't care to live in an atmosphere that's very cool and earth-tones.

CK: Minimalist.

Charles Busch: Minimalist is not who I am at all. I always wanted to live in the Wizard of Oz, Professor Marvel's caravan. yeah. It'd be so beautiful, living in a caravan.

CK: So, you've done everything: you've written a lot of plays, you performed in most of them, you've played both feminine and -a very few times -masculine roles. Charles Busch: I don't fancy or care for them too much.

CK: But you've tried them.

Charles Busch: Tried -that'd be good for me.

CK: You've done three outrageous movies, you wrote a novel that -as I told you -I love, it's the funniest thing I've read in my life. Charles Busch: I have a new book coming out August 29th, it's my memoirs.

CK: This was actually my question: what are your current projects? What's in store for your audience?

Charles Busch: I have plenty of things happening. I thought I was moving towards semiretirement and I might be but until then I've got a lot of good things going on.

CK: Recently you seemed much more interested in cabaret and singing. Charles Busch: I dipped my foot into cabaret numerous times in my career, when I was just starting out, because where do you start, I hadn't yet become a playwright/drag legend -and I was a solo performer not in drag, like in Whores of Lost Atlantis. CK: Exactly. Charles Busch: I was dressed in neutral costume playing different characters. I'd gotten into cabaret because I wanted to be in the theater but how do you do a one-man show in the theater with no money? But I could book myself in some little cabaret down here [in the West Village] even though the piece I was doing wasn't really suitable for cabaret: there's no music or anything, it's not stand-up. But I did. I did that for a couple of years. Then I got into cabaret again in the early '90s when there was a lot of AIDS benefits and so I ended up doing a onenight cabaret review as an AIDS benefit and I really enjoyed it. I was fitting many costumes in my attempts to being so Josephine Baker and I kept changing clothes all the time. So, for about two years I was booking myself doing that and then about 12 years ago maybeoccasionally I would do one song with some fundraiser or something, and this fella Seth Rudetsky, who's a musical director, would interview people onstage and then you'd sing a song or two, as you were telling your story. So I did that a couple of times and his manager said, "I could book you on this gay cruise but they want a whole act and they want you in drag". And I hadn't done that for so many years and it was a lot of money, so I called a friend of mine, Tom Judson, who I've known for many years as a lot of fun and very good musician, accompanist and suggested we do it once. So we did it and we started getting other bookings and it was always a fun thing. This time the focus really was on singing which I'd never really quite done and the more we did it, the more the singing became the most important part of the show. I was in drag just because I assumed that my audience would want to see me in drag and there's something about cabaret that's feminine to me -you know, the lady at the mike: Judy Garland, Shirley Bassey, [Edith] Piaf -that's feminine and not masculine. I have to have some intellectual reason for being in drag: I'm playing a female character, I'm embodying a certain kind of lady from a movie and I never really could understand why I was in drag in my cabaret act because they're introducing me as Charles Busch but then I come out in drag and I'm telling stories about my life and I'm singing Stephen Sondheim and Michel Legrand. So why am I in drag? But OK, why not? Then about six years ago maybe, it seemed fake to me, it didn't seem right. So I thought, I'm going to try doing the show not in drag and I saw no difference at all. The look ended up evolving in the show. I would be wearing these androgynous suits I had made in green paisley with rhinestone buttons and a lot of eye make-up and it was kind of a non-binary look basically. That was really fun. I'm going to do two nights in April at 54 Below. I also have this new play that we'll do, I believe, in the fall, I haven't got the exact dates yet. It's a very ambitious part. I am so vacillated on it… I'm terrified of the whole thing.

CK: What is it about? Charles Busch: It's funny, it just doesn't sound funny! It's loosely based on the life of Ibsen's widow, Suzannah Ibsen. Oh, you're laughing already! It's about Ibsen's widow, a few weeks after his state funeral. She's very much like a heroine out of one of his plays and her whole system of illusions of her role as the keeper of the flame, and all is shattered by this woman who shows up, who she knew many years before and was the model for Nora in A Doll's House. Ibsen basically took her story and abandoned her in her time of need because of the scandal and now she has a diary that is going to be published and exposes Ibsen as a hypocrite. And my marriage has been a sterile, sexless marriage. The other big event is that Ibsen has had an illegitimate son who he never met and so in this play he returns. He's a sailor in his forties, he shows up and ends up seducing the widow, and he awakens her sexually in a way she's never known, so then I -the widow, Suzannah -she enlists his aid that he must break into the hotel room where this woman is staying and steal the diary and destroy it, for his father's legacy and for me. I'm really excited about it, it's one of my favorite things but it's just such a big part and I hope I have the stamina to memorize all those lines. So I thought a few weeks ago, what of this other part in the play, the stepmother -that's a marvelous role -could I be happy playing that part, the supporting role and get someone else to play the lead? I thought I'll make it a better part! There's a big stretch where she was offstage and I could put her act one or two scenes also.

CK: That's exactly what I was thinking.

Charles Busch: So I made it a better part and it makes a better play but what I do is so specific and I just don't think there's an actress who could do it. One of the things that I do, my gift, is that I evoke other actresses while I'm playing the role. I'm playing it very honestly and yet there are echoes of this actress and this actress and this actress… And nobody else can really do that. I wouldn't cast a drag actor in the part and a biological woman -they don't do that, that's not what they do and that part of the humor of the play would be missing. I'm trying to memorize it now, it's not until next October. I'm trying to see if I can do it. Then my book, my memoir, is coming out August 29th. And there's also this movie we're trying to get made.

CK: Will it be as outrageous as the other ones? Charles Busch: We have this movie that we made during Covid, called The Sixth Reel. It's a caper movie where Julie Halston and I are in crazy disguises and run around the Village and try to steal this old movie reel. It's zany, but it's not a spoof of a movie genre. This other movie that we wanted to get made was a play I wrote that was never performed and makes a better movie script than a play. It's called Visitors in the Dark and we never performed it. It takes place during the 1965 New York City blackout, in this neighborhood. I play a female character but it's not a parody, it's a naturalistic character. She's a flamboyant lady, she's a painter who lives hand to mouth in this crummy apartment on West 12th St and she totally believes that when she was a child, aliens from outer space visited her and they gave her the gift of drawing, they bathed her hands and from then on she was the girl who drew. She felt all her life that the promise was that they were going to return someday for her. So she has dreamed for 60 years and now she's convinced that the blackout is because they're comingthe visitors are coming -and they're going to land on the roof of her building. Her big dilemma is that the only one who has access to the roof garden is her sworn enemy, this retired French cabaret entertainer who lives up there and she somehow has to patch it up with her, even though they hate each other, so she can get access to the roof. I hope we can get it made! CK: You have a lot of things coming! Charles Busch: For somebody who thinks they're retired, I'm not so retired! I'm only happy when I'm being creative.

CK: Thank you for this most insightful and amusing conversation! Charles Busch: Thank you.

Busch received a special Drama Desk Award for career achievement as both performer and playwright and was given a star on the Playwrights Walk outside the Lucille Lortel Theatre. He is also the subject of the acclaimed documentary film The Lady in Question is Charles Busch.