pyqpanda_alg.QAOA.qaoa
¶
Module Contents¶
Classes¶
This class provides the quantum alternative operator ansatz algorithm optimizer. It assumes a polynomial problem |
Functions¶
|
Transfer binary variable \(x_n\) to pauli operator \(\frac{I-Z_n}{2}\) |
|
Transfer binary variable \(x_n\) to pauli operator \(\frac{I+Z_n}{2}\) |
|
Transfer polynomial function with binary variables \(f(x_0, \cdots, x_n)\) to |
Use INTERP heuristic strategy to guess the initial parameter of \(p+1\) layer QAOA |
|
|
Circuit of simulation diagonal Hamiltonian \(e^{-iH heta}\). |
- pyqpanda_alg.QAOA.qaoa.p_1(n)¶
Transfer binary variable \(x_n\) to pauli operator \(\frac{I-Z_n}{2}\)
- Parameters
n :
int
index of the variable, start with 0.
- Return
operator :
pq.PauliOperator
Pauli operator \(\frac{I-Z_n}{2}\)
- Examples
Transfer \(x_0\) into pauli operator \(\frac{I-Z_0}{2}\)
>>> from pyqpanda_alg.QAOA import qaoa >>> operator_0 = qaoa.p_1(0) >>> print(operator_0) { "" : 0.500000, "Z0" : -0.500000 }
- pyqpanda_alg.QAOA.qaoa.p_0(n)¶
Transfer binary variable \(x_n\) to pauli operator \(\frac{I+Z_n}{2}\)
- Parameters
n :
integer
index of the variable, start with 0.
- Return
operator :
pq.PauliOperator
Pauli operator \(\frac{I+Z_n}{2}\)
- Examples
Transfer \(x_0\) into pauli operator \(\frac{I+Z_0}{2}\)
>>> from pyqpanda_alg.QAOA import qaoa >>> operator_0 = qaoa.p_0(0) >>> print(operator_0) { "" : 0.500000, "Z0" : 0.500000 }
- pyqpanda_alg.QAOA.qaoa.problem_to_z_operator(problem, norm=False)¶
Transfer polynomial function with binary variables \(f(x_0, \cdots, x_n)\) to pauli operator \(f(\frac{I-Z_0}{2}, \cdots, \frac{I-Z_n}{2})\)
- Parameters
problem :
expression
in sympy- Return
hamiltonian :
list[tuple]
Pauli operators \(f(\frac{I-Z_n}{2})\) in list form.
- Examples
Transfer \(2 x_0 x_1 + 3 x_2 - 1\) into pauli operators
>>> import sympy as sp >>> from pyqpanda_alg.QAOA import qaoa >>> vars = sp.symbols('x0:3') >>> f = 2*vars[0]*vars[1] + 3*vars[2] - 1 >>> print(f) 2*x0*x1 + 3*x2 - 1 >>> hamiltonian = qaoa.problem_to_z_operator(f) >>> print(hamiltonian) { "" : 1.000000, "Z2" : -1.500000, "Z1" : -0.500000, "Z0" : -0.500000, "Z0 Z1" : 0.500000 }
- pyqpanda_alg.QAOA.qaoa.parameter_interpolate(pm)¶
Use INTERP heuristic strategy to guess the initial parameter of \(p+1\) layer QAOA from the optimal parameter found from \(p\) layer QAOA circuit.
- Parameters
pm :
array-like
Optimal parameters of \(p\) layer QAOA circuit, with length \(2 imes p\)
- Return
operator :
array-like
A guess for the initial parameter of \(p+1\) layer QAOA, with length \(2 imes (p+1)\)
- References
[1] ZHOU L, WANG S T, CHOI S, et. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices[J/OL]. Physical Review X, 2020, 10(2): 021067. :DOI: 10.1103/PhysRevX.10.021067.
- Examples
Transfer \(x_0\) into pauli operator \(\frac{I-Z_0}{2}\)
>>> import numpy as np >>> from pyqpanda_alg.QAOA import qaoa >>> initial_parameter = np.array([0.1, 0.2, 0.2, 0.1]) >>> new_parameter = qaoa.parameter_interpolate(initial_parameter) >>> print(new_parameter) [0.1 0.15 0.25 0.2 0.15 0.05]
- pyqpanda_alg.QAOA.qaoa.pauli_z_operator_to_circuit(operator, qlist, gamma=np.pi)¶
Circuit of simulation diagonal Hamiltonian \(e^{-iH heta}\).
- Parameters
operator :
list
Pauli Operator in list form. (By method operator.toHamiltonian(1))
qlist :
qubit list
gamma :
float
Value of theta in \(e^{-iH heta}\).
- Return
circuit :
pq.QCircuit
Circuit of simulation diagonal Hamiltonian \(e^{-iH heta}\).
constant :
float
Constant number in the hamiltonian.
- Example
Print a circuit of hamiltonian for problem \(f(\vec{x})=2x_0x_1 + 3x_2 - 1\) with \(\theta=0\)
import pyqpanda as pq import sympy as sp from pyqpanda_alg.QAOA import qaoa vars = sp.symbols('x0:3') f = 2*vars[0]*vars[1] + 3*vars[2] - 1 operator = qaoa.problem_to_z_operator(f).toHamiltonian(True) machine = pq.CPUQVM() machine.initQVM() qubits = machine.qAlloc_many(3) circuit = qaoa.pauli_z_operator_to_circuit(operator, qubits, 0)[0] print(circuit)
┌────────────┐ ┌─┐ q_0: |0>─┤RZ(0.000000)├ ───■── ────────────── ───■── ┤I├ ├────────────┤ ┌──┴─┐ ┌────────────┐ ┌──┴─┐ ├─┤ q_1: |0>─┤RZ(0.000000)├ ┤CNOT├ ┤RZ(0.000000)├ ┤CNOT├ ┤I├ ├────────────┤ ├─┬──┘ └────────────┘ └────┘ └─┘ q_2: |0>─┤RZ(0.000000)├ ┤I├─── ────────────── ────── ─── └────────────┘ └─┘
- class pyqpanda_alg.QAOA.qaoa.QAOA(problem, init_circuit=None, mixer_circuit=None, norm=False)¶
This class provides the quantum alternative operator ansatz algorithm optimizer. It assumes a polynomial problem consisting only of binary variables. The problem is then translated into an Ising Hamiltonian whose minimal eigen vector and corresponding eigenstate correspond to the optimal solution of the original optimization problem. The provided solver is then used to approximate the ground state of the Hamiltonian to find a good solution for the optimization problem.
- Parameters
problem :
expression
in sympy orpq.PauliOperator
A polynomial function with binary variables to be optimized. Support an expression in sympy. Next version will support an object from pypanda PauliOperator.
init_circuit :
function
,optional
The quantum circuit to create the initial state of QAOA algorithm. Default is Hadamard circuit to create an equal superposition state \(\ket{\psi} = 2^{-n/2}\sum_{i=0}^{2^n-1}\ket{i}\).
mixer_circuit :
function
,optional
The function which returns a mixer quantum circuit \(U_M(\beta)=\exp(-i\beta H_M)\). The function should accept two parameters (qubit list, array-like angles) as input, and return a quantum circuit as output. Default is X mixer circuit \(\exp(-i\beta \sum_i X_i)=RX(2\beta)^{\otimes n}\)
norm :
bool
- Attributes
energy_dict :
dict
The dict which stores the function value for solutions being sampled during the optimization.
problem_dimension :
integer
The problem dimension, and also the qubit number.
circuit iter :
integer
The number of times the quantum circuit being called during optimization.
- Methods
calculate_energy : Calculate the function value for one solution.
run_qaoa_circuit : Given parameters, run the qaoa circuit and get the theoretical probability distribution.
run : run the optimization process
- Reference
[1] FARHI E, GOLDSTONE J, GUTMANN S. A Quantum Approximate Optimization Algorithm[J/OL]. 2014[2022-03-09]. https://arxiv.org/abs/1411.4028v1. DOI:10.48550/arXiv.1411.4028.
[2] ZHOU L, WANG S T, CHOI S, et. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices[J/OL]. Physical Review X, 2020, 10(2): 021067. DOI:10.1103/PhysRevX.10.021067.
- calculate_energy(x)¶
Calculate the function value for one solution.
- Parameter
x :
array-like
one binary variables solution in vector form.
- Return
float
function value of the solution \(f(x)\).
- Example
Let \(f(\vec{x})=2x_0x_1 + 3x_2 - 1\), calculate \(f(1,0,0)\)
>>> import sympy as sp >>> from pyqpanda_alg.QAOA.qaoa import * >>> vars = sp.symbols('x0:3') >>> f = 2*vars[0]*vars[1] + 3*vars[2] - 1 >>> print(f) 2*x0*x1 + 3*x2 - 1 >>> qaoa_f = QAOA(f) >>> solution_1 = [1, 0, 0] >>> print(qaoa_f.calculate_energy(solution_1)) -1 >>> solution_2 = [0, 1, 1] >>> print(qaoa_f.calculate_energy(solution_2)) 2 >>> ham_f = 2 * p_1(0) * p_1(1) + 3 * p_1(2)- 1 >>> qaoa_ham = QAOA(ham_f) >>> print(qaoa_ham.calculate_energy(solution_1)) -1
- run_qaoa_circuit(gammas, betas, shots=-1)¶
Given parameters, run the qaoa circuit and get the theoretical probability distribution.
- Parameters
gammas :
array-like
Parameter gamma for QAOA phase circuit
betas :
array-like
Parameter beta for QAOA mixer circuit
shots :
integer
,optional
Times of running the same circuit. Must be positive integer or -1. If it is -1, the results are given as amplitudes of all state vectors, which can be viewed as running the circuit infinite times. Default is -1.
- Return
prob_result :
dict
Probability of each computational basis state. The keys are binary form of qubits where the first qubit sits at the right-most position and the items are the corresponding probability (if shots = -1) or frequency (if shots > 0).
- Example
Run a two-layer QAOA algorithm circuit of problem \(f(\vec{x})=2x_0x_1 + 3x_2 - 1\) with parameters \([0, 0, 0, 1, 1, 1]\)
import pyqpanda as pq import sympy as sp from pyqpanda_alg.QAOA.qaoa import * vars = sp.symbols('x0:3') f = 2*vars[0]*vars[1] + 3*vars[2] - 1 qaoa_f = QAOA(f) gammas = [0, 0] betas = [1, 1] qaoa_result = qaoa_f.run_qaoa_circuit(gammas, betas, -1) print(qaoa_result) qaoa_result = qaoa_f.run_qaoa_circuit(gammas, betas, 500) print(qaoa_result)
The codes above would give results like (with errors due to randomness):
{'000': 0.12500000000000008, '001': 0.12500000000000008, '010': 0.12500000000000008, '011': 0.12500000000000008, '100': 0.12500000000000008, '101': 0.12500000000000008, '110': 0.12500000000000008, '111': 0.12500000000000008} {'000': 0.132, '001': 0.134, '010': 0.112, '011': 0.136, '100': 0.094, '101': 0.13, '110': 0.122, '111': 0.14}
- run(layer=1, initial_para=None, shots=-1, loss_type=None, optimize_type=None, optimizer=None, optimizer_option=None, **loss_option)¶
Optimize the function by QAOA algorithm.
- Parameters
layer :
integer
,optional
Layers number of QAOA circuit. Default is 1. If optimize type is interp, then it represents the final layer of the optimization progress.
initial_para :
array-like
,optional
initial parameters of \(p\) layer QAOA circuit, with length \(2\times p\). If not given, a random distribution from \(U(0, \pi)\) of size \(2p\) is generated.
shots :
integer
,optional
Circuit measured times. If shots takes -1, then use theoretical probability (by state vector) instead. Default is -1
loss_type :
string
,optional
The loss function used by the optimizer. Should be one of
default
: Given a result, calculate the energy expectation.See Note
Energy expectation
Gibbs
: Given a result and argument temperature \(T\), calculate the Gibbs energy expectation.See Note
Gibbs energy
CVaR
: Given a result and argument \(\alpha\), calculate the CVaR loss function.See Note
CVaR loss functio
If not given, default by
default
.optimize_type :
string
,optional
The method to optimize the QAOA circuit. Should be one of
default
: Directly optimize the \(p\) layer QAOA circuit.interp
: Use interpolate method to train a big QAOA circuit.See Note
interp method
If not given, default by
default
.optimizer :
string
,optional
Type of solver. Should be one of
SPSA
: Seespsa.spsa_minimize
one of
Nelder-Mead
,Powell
,CG
,BFGS
,Newton-CG
,TNC
,COBYLA
,SLSQP
,
trust-constr
,dogleg
,trust-ncg
,trust-exact
,trust-krylov
. Seescipy.optimize.minimize
.If not given, default by
SLSQP
.optimizer_option :
dict
,optional
A dictionary of solver options. Accept the following generic options:
bounds :
List[tuple]
,optional
Bounds for the variables. Sequence of
(min, max)
pairs for each element in x. If specified, variables are clipped to fit inside the bounds after each iteration. None is used to specify no bound.options :
integer
Maximum number of iterations to perform. Depending on the method each iteration may use several function evaluations.
For TNC use maxfun instead of maxiter.
loss_option :
temperature :
float
,optional
parameter calculated in _loss_function_Gibbs. Default is 1. See Note
Gibbs energy
.alpha :
float
,optional
parameter calculated in _loss_function_cvar. Default is 1. See Note
Gibbs energy
.- Return
qaoa_result :
dict
dict of all possible solutions with corresponding probabilities. The elements are arranged in descending order of probability.
para_result :
array-like
Array of the optimized QAOA parameters.
loss_result :
float
Loss function value of the optimized QAOA parameters.
- Example
Run a two-layer QAOA algorithm circuit of problem \(f(\vec{x})=2x_0 + x_1 + 3x_2 - 1\) with parameters
[0, 0, 0, 1, 1, 1]
import sympy as sp from pyqpanda_alg.QAOA import qaoa vars = sp.symbols('x0:3') f = 2*vars[0]*vars[1] + 3*vars[2] - 1 qaoa_f = qaoa.QAOA(f) qaoa_result = qaoa_f.run(layer=3) sorted_result = sorted(qaoa_result[0].items(), key=lambda k:k[1], reverse=True)[:5] print(sorted_result[:5])
[('000', 0.6848946054168573), ('010', 0.1575526972909123), ('001', 0.15755269729091226), ('100', 7.957749518311524e-13), ('110', 1.8305953815081342e-13)]
- Notes
Energy expectation:
In traditional QAOA algorithm, the parameter is optimized by minimize the energy expectation
\(\bra{\psi(\gamma, \beta}H\ket{\psi(\gamma, \beta)}\)
If measure type is sample, it is calculated by
\(E=\frac{1}{N_{\rm{shots}}}\sum_{i=0}^{2^n-1} n_iE_i\).
If measure type is theoretical, it is calculated by
\(E=\sum_{i=0}^{2^n-1} p_iE_i\).
Gibbs energy:
Inspired by Ref[1]. Instead of the traditional energy expectation value, using the Gibbs function as the object function. The function is
\(f_G=-\ln \langle e^{-E/T}\rangle\)
Here \(T\) is the hyperparameter of temperature, as \(T\) decreases, the weight of the lower energy states in the loss function then becomes larger. When \(T=1\), it turns back to energy expectation function.
If measure type is sample, it is calculated by
\(G=-\log (\frac{1}{N_{\rm{shots}}}\sum_{i=0}^{2^n-1} n_i \exp(-E_i/T))\).
If measure type is theoretical, it is calculated by
\(G=-\log (\sum_{i=0}^{2^n-1} p_i \exp(-E_i/T))\).
CVaR loss function:
Inspired by Ref[3].Instead of the traditional energy expectation value, using the Conditional Value at Risk function as the object function. The function is
\(CVaR_\alpha(X) = \mathbb{E}[X|X\leq F_X^{-1}(alpha)]\)
Here \(\alpha\) is the confidence level. CVaR is the expected value of the lower α-tail of the distribution of X. \(\alpha=0\) corresponds to the minimum, and \(\alpha=1\) corresponds to the expectation value.
If measure type is sample, it is calculated by
\(E=\frac{1}{\alpha N}(\sum_{i=0}^{k} n_iE_i + (\alpha N - n_{k+1})E_{k+1}),\sum_{i=0}^k n_i < \alpha N\)
If measure type is theoretical, it is calculated by
\(E=\sum_{i=0}^{k} p_iE_i + (\alpha - p_{k+1})E_{k+1}, \sum_{i=0}^k p_i < \alpha\)
Interpolate method:
Inspired by Ref[2].
- Reference
[1] LI L, FAN M, CORAM M, et. Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search[J/OL]. Physical Review Research, 2020, 2(2): 023074. DOI:10.1103/PhysRevResearch.2.023074.
[2] ZHOU L, WANG S T, CHOI S, et. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices[J/OL]. Physical Review X, 2020, 10(2): 021067. DOI:10.1103/PhysRevX.10.021067.
[3] BARKOUTSOS P K, NANNICINI G, ROBERT A, et. Improving Variational Quantum Optimization using CVaR[J/OL]. Quantum, 2020, 4: 256. DOI:10.22331/q-2020-04-20-256.