# 否定リテラル

:::{container} prog-cpp
他のQUBO/HUBOツールとは異なり、Hi-QUBO はバイナリ変数の否定リテラルをネイティブにサポートしています。 
:::

:::{container} prog-python
他のQUBO/HUBOツールとは異なり、pyQBPP はバイナリ変数の否定リテラルをネイティブにサポートしています。
:::

従来、バイナリ変数 $x$ の否定リテラル $\overline{x}$ は $1-x$ と表現されます。 これにより、多くの否定リテラルを含む項を展開する際に項数が爆発的に増加します。例えば、4つの否定リテラルを含む項は、定数項を含む16項に展開されます：

$$
\overline{x}_0 \cdot \overline{x}_1 \cdot \overline{x}_2 \cdot \overline{x}_3 =& (1-x_0)(1-x_1)(1-x_2)(1-x_3) 
\\=& 1 - x_0 - x_1 - x_2 - x_3 + x_0x_1 + x_0x_2 + x_0x_3 + x_1x_2 + x_1x_3 + x_2x_3
\\&- x_0x_1x_2 - x_0x_1x_3 
- x_0x_2x_3 - x_1x_2x_3 + x_0x_1x_2x_3.
$$

:::{container} prog-cpp
Hi-QUBOはこのような項を否定リテラルを展開せずに扱うことができます。
:::

:::{container} prog-python
pyQBPPはこのような項を否定リテラルを展開せずに扱うことができます。
:::

:::{container} prog-cpp
## Hi-QUBOでの否定リテラルの使用
Hi-QUBOでは `~` 演算子で否定リテラルを表現します。`~x` は `x` の否定リテラルを表します。 以下のプログラムは、Hi-QUBOが否定リテラルをどのように扱うかを示しています：

```{literalinclude} ../../programFiles/cppPrograms/advanced/negated-literals-program1.cpp
:language: cpp
:caption: negated-literals-program1.cpp
```
:::


:::{container} prog-python
## pyQBPPでの否定リテラルの使用
pyQBPPでは `~` 演算子で否定リテラルを表現します。`~x` は `x` の否定リテラルを表します。 以下のプログラムは、pyQBPPが否定リテラルをどのように扱うかを示しています：

```{literalinclude} ../../programFiles/pythonPrograms/advanced/negated-literals-program1.py
:language: python
:caption: negated-literals-program1.py
```
:::


このプログラムでは、式 `f` に以下が格納されます：

$$
f = \overline{x}_0 \cdot \overline{x}_1 \cdot \overline{x}_2 \cdot \overline{x}_3
$$
 
式 `g` は、従来のツールと同様に各 `~x[i]` を `1 - x[i]` で置換して得られた式です。このプログラムは以下の出力を生成します：

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: Hi-QUBOでの否定リテラルの使用1 -->
:end-before: <!-- end: Hi-QUBOでの否定リテラルの使用1 -->
```

:::{container} prog-cpp
Hi-QUBO に付属するソルバーは、否定リテラルを含むHUBO式を正リテラルに展開せずに直接受け付けます。 一方、従来のツールは $\overline{x}$ の代わりに $1-x$ を使用する必要があります。 そのため、多くの否定リテラルを含む項を持つHUBOモデルでは、Hi-QUBO は従来のツールより高い性能を発揮できます。
:::


:::{container} prog-python
pyQBPP に付属するソルバーは、否定リテラルを含むHUBO式を正リテラルに展開せずに直接受け付けます。 一方、従来のツールは $\overline{x}$ の代わりに $1-x$ を使用する必要があります。 そのため、多くの否定リテラルを含む項を持つHUBOモデルでは、pyQBPP は従来のツールより高い性能を発揮できます。
:::


## `simplify_as_binary()` と否定リテラル

1変数または2変数の項は項数爆発を起こさず、$\overline{x}$ を $1-x$ で置き換えることで項数が減少する場合があるため、`simplify_as_binary()` は1次または2次の項でのみ否定リテラルを展開します。3次以上の項では否定リテラルがそのまま保持されます。

以下の例は、このような置換が式のサイズを縮小できることを示しています：

$$
x+\overline{x} &= x+(1-x)=1,\\
x \cdot \overline{x} &= x \cdot (1-x) = x-x^2 = 0,\\
-x \cdot y + \overline{x} \cdot \overline{y} 
&= -x \cdot y + (1-x)(1-y) = 1-x-y.
$$
 
上記のプログラムは、変数の数に応じて以下のように動作します。 1変数の場合、`f` と `g` は同じ出力になります：

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: `simplify_as_binary()` と否定リテラル1 -->
:end-before: <!-- end: `simplify_as_binary()` と否定リテラル1 -->
```

2変数の場合:

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: `simplify_as_binary()` と否定リテラル2 -->
:end-before: <!-- end: `simplify_as_binary()` と否定リテラル2 -->
```

3変数以上の場合、`f` は否定リテラルを保持し、`g` は完全に展開されます：

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: `simplify_as_binary()` と否定リテラル3 -->
:end-before: <!-- end: `simplify_as_binary()` と否定リテラル3 -->
```

## `simplify_as_spin()` と否定リテラル
スピン変数（ $s \in \{-1, 1\}$ ）の場合、否定リテラル $\overline{s}$ は $-s$ に対応します。`simplify_as_spin()` 関数は、否定変数ごとに係数を反転することで、すべての否定リテラル $\overline{s}$ を $-s$ に置き換えます。

## `simplify()` と否定リテラル
`simplify()` 関数は変数の取る値について仮定を置かないため、否定リテラルの置換は行いません。

## `replace()` と否定リテラル
`replace()` 関数は `x` と `~x` を独立したキーとして扱います。 したがって、変数の値を固定するには、正リテラルと否定リテラルの両方を整合的に指定する必要があります。

以下のプログラムは、まず `x` を 1 に固定し、次に `~x` を 0 に固定します：

:::{container} prog-cpp
```{literalinclude} ../../programFiles/cppPrograms/advanced/negated-literals-program2.cpp
:language: cpp
:caption: negated-literals-program2.cpp
```
:::


:::{container} prog-python
```{literalinclude} ../../programFiles/pythonPrograms/advanced/negated-literals-program2.py
:language: python
:caption: negated-literals-program2.py
```
:::



このプログラムは以下の出力を生成します：

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: `replace()` と否定リテラル -->
:end-before: <!-- end: `replace()` と否定リテラル -->
```

## 否定リテラルを含む式の評価
否定リテラルを含む式を評価するには、各変数について正リテラルまたは否定リテラルのいずれか一方の値を指定すれば十分です。 両方を指定する場合、値は整合的でなければなりません（例：`{x, 0}` と `{~x, 1}`）。

以下のプログラムは、$x=0,~y=0,~z=0$ で式を評価します：

:::{container} prog-cpp
```{literalinclude} ../../programFiles/cppPrograms/advanced/negated-literals-program3.cpp
:language: cpp
:caption: negated-literals-program3.cpp
```
:::


:::{container} prog-python
```{literalinclude} ../../programFiles/pythonPrograms/advanced/negated-literals-program3.py
:language: python
:caption: negated-literals-program3.py
```
:::


このプログラムは以下の出力を生成します：

```{include} ../../programFiles/markDown/advanced/negated-literals-program.md
:start-after: <!-- begin: 否定リテラルを含む式の評価 -->
:end-before: <!-- end: 否定リテラルを含む式の評価 -->
```

`x` は正リテラルとして値 0 で指定し、`~y` と `~z` は否定リテラルとして値 1 で指定しています。 3つの変数はすべて実質的に 0 に設定され、$\overline{x} \cdot \overline{y} \cdot \overline{z}=1$ となります。