Kerberos¶
Kerberos divides the problem into subproblems and solves them using Tabu Search, Simulated Annealing and QPU Subproblem Sampling. These algorithms are executed in parallel and afterwards the best solutions are combined. This procedure is applied iteratively until the best solution is found or a termination criterion is met.
Compatible Backends¶
The Kerberos algorithm supports the following backends:
DWaveQpuBy default,Kerberosuses theDWaveQpubackend.
Initialization¶
The following section outlines the default configurations of Kerberos. You can also specify
other compatible backends for the algorithm. When backend=None is specified, the default backend
will be initialized automatically. In this case, if the backend requires a token, it will be taken
from the environment variables.
from luna_quantum.algorithms import Kerberos
from luna_quantum.solve.parameters.algorithms.base_params import (
Decomposer,
QuantumAnnealingParams,
SimulatedAnnealingBaseParams,
TabuKerberosParams
)
algorithm = Kerberos(
backend=None,
num_reads=100,
num_retries=0,
max_iter=100,
max_time=5,
convergence=3,
target=None,
rtol=1e-05,
atol=1e-08,
simulated_annealing_params=SimulatedAnnealingBaseParams(
num_reads=None,
num_sweeps=1000,
beta_range=None,
beta_schedule_type='geometric',
initial_states_generator='random'
),
quantum_annealing_params=QuantumAnnealingParams(
anneal_offsets=None,
anneal_schedule=None,
annealing_time=None,
auto_scale=None,
fast_anneal=False,
flux_biases=None,
flux_drift_compensation=True,
h_gain_schedule=None,
initial_state=None,
max_answers=None,
num_reads=1,
programming_thermalization=None,
readout_thermalization=None,
reduce_intersample_correlation=False,
reinitialize_state=None
),
tabu_kerberos_params=TabuKerberosParams(
num_reads=None,
tenure=None,
timeout=100,
initial_states_generator='random',
max_time=None
),
decomposer=Decomposer(
size=10,
min_gain=None,
rolling=True,
rolling_history=1.0,
silent_rewind=True,
traversal='energy'
)
)
Parameter Details
For a complete overview of available parameters and their usage, see the Kerberos API Reference.
Usage¶
from luna_quantum import LunaSolve
LunaSolve.authenticate("<YOUR_LUNA_API_KEY>")
# Define your model and algorithm
model = ...
algorithm = ...
solve_job = algorithm.run(model, name="my-solve-job")
API Reference¶
Bases: LunaAlgorithm[DWaveQpu]
Kerberos hybrid quantum-classical optimization solver.
Kerberos is a sophisticated hybrid solver that decomposes an optimization problem into subproblems and solves them using multiple techniques in parallel: Tabu Search, Simulated Annealing, and QPU (Quantum Processing Unit) sampling. It then combines the results and iteratively refines the solution.
This approach leverages both classical and quantum resources efficiently, making it effective for large and complex optimization problems beyond the capacity of pure quantum approaches.
Attributes:
| Name | Type | Description |
|---|---|---|
num_reads |
int
|
Number of output solutions to generate. Higher values provide better statistical coverage of the solution space but increase computational resources required. This parameter determines how many distinct solutions the algorithm will return after completion. Default is 100. |
num_retries |
int
|
Number of attempts to retry embedding the problem onto the quantum hardware if initial attempts fail. Useful for complex problems that may be challenging to map to the quantum processor's topology. Each retry attempts a different embedding strategy. Default is 0 (no retries). |
max_iter |
int | None
|
Maximum number of iterations for the solver. Each iteration involves running the three solvers (Tabu, SA, QPU) in parallel, combining their results, and refining the solution for the next iteration. Higher values allow more thorough exploration and refinement but increase runtime. Default is 100. |
max_time |
int
|
Maximum time in seconds for the solver to run. Provides a hard time limit regardless of convergence or iteration status. Once this time is reached, the solver returns the best solution found so far. Default is 5, which may need to be increased for large problems. |
convergence |
int
|
Number of consecutive iterations without improvement before declaring convergence. Higher values ensure more stable solutions by requiring consistent results across multiple iterations. Default is 3, which balances thoroughness with efficiency. |
target |
float | None
|
Target objective value that triggers termination if reached. Allows early stopping when a solution of sufficient quality is found. Default is None, which means the algorithm will run until other stopping criteria are met. |
rtol |
float
|
Relative tolerance for convergence detection. Used when comparing objective values between iterations to determine if significant improvement has occurred. Smaller values require more substantial improvements to continue. Default is DEFAULT_RTOL. |
atol |
float
|
Absolute tolerance for convergence detection. Used alongside rtol when comparing objective values to determine if the algorithm has converged. Smaller values enforce stricter convergence criteria. Default is DEFAULT_ATOL. |
quantum_annealing_params |
QuantumAnnealingParams
|
Nested configuration for quantum annealing parameters used by the QPU component of the hybrid solver. Controls aspects like annealing schedule, chain strength, and programming thermalization time. These parameters can significantly impact the quality of solutions found by the quantum component. Default is a QuantumAnnealingParams instance with default settings. |
tabu_kerberos_params |
TabuKerberosParams
|
Nested configuration for tabu search parameters used by the Tabu component of the hybrid solver. Controls aspects like tabu tenure, number of iterations, and neighborhood exploration strategy. The Tabu component helps the algorithm systematically explore promising regions while avoiding cycles. Default is a TabuKerberosParams instance with default settings. |
decomposer |
Decomposer
|
Decomposer: Breaks down problems into subproblems of manageable size Default is a Decomposer instance with default settings. |
backend
class-attribute
instance-attribute
¶
decomposer
class-attribute
instance-attribute
¶
decomposer: Decomposer = Field(default_factory=Decomposer)
model_config
class-attribute
instance-attribute
¶
quantum_annealing_params
class-attribute
instance-attribute
¶
quantum_annealing_params: QuantumAnnealingParams = Field(
default_factory=QuantumAnnealingParams
)
simulated_annealing_params
class-attribute
instance-attribute
¶
simulated_annealing_params: SimulatedAnnealingBaseParams = Field(
default_factory=SimulatedAnnealingBaseParams
)
tabu_kerberos_params
class-attribute
instance-attribute
¶
tabu_kerberos_params: TabuKerberosParams = Field(
default_factory=TabuKerberosParams
)
get_compatible_backends
classmethod
¶
get_default_backend
classmethod
¶
get_default_backend() -> DWaveQpu
Return the default backend implementation.
This property must be implemented by subclasses to provide the default backend instance to use when no specific backend is specified.
Returns:
| Type | Description |
|---|---|
IBackend
|
An instance of a class implementing the IBackend interface that serves as the default backend. |
run ¶
run(
model: Model | str,
name: str | None = None,
backend: BACKEND_TYPE | None = None,
client: LunaSolve | str | None = None,
*args: Any,
**kwargs: Any,
) -> SolveJob
Run the configured solver.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
model
|
Model or str
|
The model to be optimized or solved. It could be an Model instance or a string identifier representing the model id. |
required |
name
|
str | None
|
If provided, the name of the job. Defaults to None. |
None
|
backend
|
BACKEND_TYPE | None
|
Backend to use for the solver. If not provided, the default backend is used. |
None
|
client
|
LunaSolve or str
|
The client interface used to interact with the backend services. If not provided, a default client will be used. |
None
|
*args
|
Any
|
Additional arguments that will be passed to the solver or client. |
()
|
**kwargs
|
Any
|
Additional keyword parameters for configuration or customization. |
{}
|
Returns:
| Type | Description |
|---|---|
SolveJob
|
The job object containing the information about the solve process. |
Bases: BaseModel
Configuration for breaking down larger problems into subproblems for DWave QPUs.
Attributes:
| Name | Type | Description |
|---|---|---|
size |
int, default=10
|
Nominal number of variables in each subproblem. The actual subproblem can be
smaller depending on other parameters (e.g., |
min_gain |
Optional[float], default=None
|
Minimum required energy reduction threshold for including a variable in the subproblem. A variable is included only if flipping its value reduces the BQM energy by at least this amount. If None, no minimum gain is required. |
rolling |
bool, default=True
|
Controls variable selection strategy for successive calls on the same problem:
|
rolling_history |
float, default=1.0
|
Fraction of the problem size (range 0.0 to 1.0) that participates in the rolling selection. Once this fraction of variables has been processed, subproblem unrolling is reset. Min: 0.0, Max: 1.0 |
silent_rewind |
bool, default=True
|
Controls behavior when resetting/rewinding the subproblem generator:
|
traversal |
Literal["energy", "bfs", "pfs"], default="energy"
|
Algorithm used to select a subproblem of
|
Bases: BaseModel
Parameters for quantum annealing sampling on physical quantum processors (QPUs).
These parameters control the quantum annealing process on hardware devices like D-Wave quantum annealers, specifying how the annealing is performed, how many samples to collect, and various hardware-specific settings that affect solution quality and runtime.
Attributes:
| Name | Type | Description |
|---|---|---|
anneal_offsets |
list[float] | None
|
Per-qubit time offsets for the annealing path in normalized annealing time units. List of floats with length equal to the number of qubits. Default is None. |
anneal_schedule |
list[tuple[float, float]] | None
|
Custom schedule for the annealing process as a list of (time, s) pairs. Time is in normalized units [0, 1] and s is the annealing parameter [0, 1]. Default is None. |
annealing_time |
float | None
|
Duration of the annealing process in microseconds. Must be within the range supported by the QPU hardware. Default is None. |
auto_scale |
bool | None
|
Whether to automatically normalize the problem energy range to use the full range of h and J values supported by the hardware. Default is None. |
fast_anneal |
bool
|
Use accelerated annealing protocol for shorter annealing times. Default is False. |
flux_biases |
list[float] | None
|
Custom flux bias offsets for each qubit in units of Φ₀ (flux quantum). List length must equal the number of qubits. Default is None. |
flux_drift_compensation |
bool
|
Whether to compensate for drift in qubit flux over time using real-time calibration data. Default is True. |
h_gain_schedule |
list[tuple[float, float]] | None
|
Schedule for h-gain during annealing as a list of (time, gain) pairs. Time is in normalized units [0, 1]. Default is None. |
initial_state |
list[int] | None
|
Starting state for the annealing process. List of {-1, +1} values with length equal to the number of qubits. Default is None. |
max_answers |
int | None
|
Maximum number of unique answer states to return. Must be ≤ num_reads. Default is None. |
num_reads |
int
|
Number of annealing cycles to perform. Must be positive integer. Default is 1. |
programming_thermalization |
float | None
|
Wait time after programming the QPU in microseconds to allow the system to thermalize. Default is None. |
readout_thermalization |
float | None
|
Wait time after each anneal before reading results in microseconds. Default is None. |
reduce_intersample_correlation |
bool
|
Whether to add delay between samples to reduce correlation between consecutive measurements. Default is False. |
reinitialize_state |
bool | None
|
Whether to reset to a new initial state between reads to reduce correlation. Default is None. |
anneal_schedule
class-attribute
instance-attribute
¶
annealing_time
class-attribute
instance-attribute
¶
annealing_time: float | None = Field(default=None, gt=0)
h_gain_schedule
class-attribute
instance-attribute
¶
max_answers
class-attribute
instance-attribute
¶
max_answers: int | None = Field(default=None, ge=1)
programming_thermalization
class-attribute
instance-attribute
¶
programming_thermalization: float | None = Field(default=None, gt=0)
readout_thermalization
class-attribute
instance-attribute
¶
readout_thermalization: float | None = Field(default=None, gt=0)
Bases: BaseModel
Mixin class that provides parameters for TabuKerberos algorithm.
TabuKerberos implements a specialized version of TabuSearch with time-based constraints. This mixin provides the parameters needed to configure the tabu search component.
Attributes:
| Name | Type | Description |
|---|---|---|
num_reads |
Optional[int]
|
Number of reads. Each read is generated by one run of the tabu algorithm. Default is None, which matches the number of initial states or uses one if no initial states are provided. |
tenure |
Optional[int]
|
Tabu tenure, which is the length of the tabu list, or number of recently explored solutions kept in memory. Default is None (a quarter of the number of problem variables up to a maximum value of 20). |
timeout |
float
|
Maximum running time per read in milliseconds. Default is 100. |
initial_states_generator |
Literal['none', 'tile', 'random']
|
Defines the expansion of |
max_time |
float | None
|
Overall maximum duration in seconds for the entire tabu search algorithm. Default is None (run until convergence criteria are met). |
Bases: BaseModel
Parameters for the Simulated Annealing optimization algorithm.
This class extends the basic SimulatedAnnealing parameters with additional controls for more fine-grained customization of the annealing process, allowing advanced users to tune the algorithm for specific problem characteristics.
Simulated Annealing mimics the physical annealing process where a material is heated and then slowly cooled to remove defects. In optimization, this translates to initially accepting many non-improving moves (high temperature) and gradually becoming more selective (cooling) to converge to an optimum.
Attributes:
| Name | Type | Description |
|---|---|---|
num_reads |
Union[int, None]
|
Number of independent runs of the algorithm, each producing one solution sample. Multiple reads with different random starting points increase the chance of finding the global optimum. Default is None, which matches the number of initial states (or just one read if no initial states are provided). |
num_sweeps |
Union[int, None]
|
Number of iterations/sweeps per run, where each sweep updates all variables once. More sweeps allow more thorough exploration but increase runtime. Default is 1,000, suitable for small to medium problems. |
beta_range |
Union[List[float], Tuple[float, float], None]
|
The inverse temperature (β=1/T) schedule endpoints, specified as [start, end]. A wider range allows more exploration. Default is calculated based on the problem's energy scale to ensure appropriate acceptance probabilities. |
beta_schedule_type |
Literal['linear', 'geometric']
|
How beta values change between endpoints: - "linear": Equal steps (β₁, β₂, ...) - smoother transitions - "geometric": Multiplicative steps (β₁, r·β₁, r²·β₁, ...) - spends more time at lower temperatures for fine-tuning Default is "geometric", which often performs better for optimization problems. |
initial_states_generator |
Literal['none', 'tile', 'random']
|
How to handle cases with fewer initial states than num_reads: - "none": Raises error if insufficient initial states - "tile": Reuses provided states by cycling through them - "random": Generates additional random states as needed Default is "random", which maximizes exploration. |
beta_range
class-attribute
instance-attribute
¶
beta_schedule_type
class-attribute
instance-attribute
¶
beta_schedule_type: Literal['linear', 'geometric'] = 'geometric'