miner-embedding

작성

Miner Embedding

docs

  • Binary Quadratic Model를 D-Wave의 양자 컴퓨터로 풀기 위해서 Miner Embedding이 필요함
    • Binary Quadratic Model: QUBO를 포함하는 더 추상적인 개념
  • Minder Embedding: QUBO 문제를 QPU Topology에 매핑을 하는 것
    • Topology는 계속 발전 되어가고 있고 $K_{4, 4}$를 사용하는 것도 옛날 거
  • 구현: Composed Sampler (DWaveSampler, Embedding Composite)을 합쳐서 구현되어있음
    ex) LeapHybridSampler (QUBO 문제만 넣으면 CPU, QPU를 사용해서 해줌)

Example

$$ E(S) = -s_0s_1 \newline s_i \in \{-1, +1\} $$

  • $E(S)$는 에너지 함수 (Objective Function이라고 보면됨)
  • $s_i$는 -1, 1만을 가짐 (ising 모델에선 -1, 1 | QUBO에선 0, 1)
    • 2개의 variable이 있고 qubit이 2개가 필요 그럼 간단하게 매핑이 가능 minor_embedding_simple_example

Chain

  • QPU topology는 완전 연결되어있지 않다.
    • ex) Pegasus topology에선 K_5 그래프가 존재하지 않는다.
  • 그래서 K_5를 만들기 위해선 2개의 Qubit을 하나의 Variable로 다뤄야한다.
    • 이렇게 묶여있는 Qubit의 집합을 Chain이라고 부른다. minor_embedding_chain_example
from dwave.system import DWaveSampler, EmbeddingComposite, FixedEmbeddingComposite

# EmbeddingComposite이게 알아서 Minor Embedding을 해줌
sampler = EmbeddingComposite(DWaveSampler())

# 수동으로 Minor Embedding을 해줌
# 4408, 2437 qubit을 하나로 묶음 (인접한 qubit을 하나로 묶을 수 있음)
sampler = FixedEmbeddingComposite(DWaveSampler(),
    embedding={0: [4408, 2437], 1: [4333], 2: [4348], 3: [2497], 4: [2512]})

Chain Strength

  • 2개의 Qubit를 묶기 위해선 다른 애들의 연결보다 강해야한다. (충분히 강한 연결을 하지 않으면 서로 상태가 달라질 수도 있다.)
    • chain_strength가 너무 클 때: 물리적인 문제가 존재, 문제에 집중하기 보단 묶는데 시스템이 집중하게 된다.
    • 그래서 너무 높지 않으면서 충분히 묶을 수 있는 강도를 사용해야한다.

자동 설정

  • 내부적으로 uniform_torque_compensation()를 사용해서 chain_strength를 지정
sampleset = sampler.sample(bqm, num_reads=1000)
print(sampleset.lowest())
# Result
#     0  1  2  3  4 energy num_oc. chain_.
# 0  -1 +1 +1 -1 -1   -3.0      69     0.0
# 1  +1 -1 -1 +1 -1   -3.0     115     0.0
# 2  +1 -1 -1 -1 +1   -3.0      95     0.0
# 3  +1 -1 +1 -1 -1   -3.0      84     0.0
# 4  -1 -1 -1 +1 +1   -3.0     116     0.0
# 5  -1 -1 +1 +1 -1   -3.0      99     0.0
# 6  -1 -1 +1 -1 +1   -3.0      91     0.0
# 7  +1 +1 -1 -1 -1   -3.0      71     0.0
# 8  -1 +1 -1 +1 -1   -3.0      98     0.0
# 9  -1 +1 -1 -1 +1   -3.0      95     0.0
# 10 +1 -1 -1 +1 -1   -3.0       1     0.2
# ['SPIN', 11 rows, 934 samples, 5 variables]


print(round(sampleset.info['embedding_context']['chain_strength'], 3))
# Result
# 2.828 // chain_strength가 2.828

수동 설정

  • chain_strength를 수동으로 지정 가능
  • ex) chain_strength를 1로 지정
    • 정답 발견횟수 (num_oc)가 100개에서 10개로 낮아짐 (90%는 chain이 끊어졌다.)
sampleset = sampler.sample(bqm, num_reads=1000, chain_strength=1)
print(sampleset.lowest())
# Result
#    0  1  2  3  4 energy num_oc. chain_.
# 0 -1 +1 +1 -1 -1   -3.0      12     0.0
# 1 +1 -1 -1 +1 -1   -3.0      13     0.0
# 2 +1 -1 -1 -1 +1   -3.0      13     0.0
# 3 +1 -1 +1 -1 -1   -3.0      16     0.0
# 4 -1 -1 -1 +1 +1   -3.0       6     0.0
# 5 -1 -1 +1 +1 -1   -3.0      10     0.0
# 6 -1 -1 +1 -1 +1   -3.0      17     0.0
# 7 +1 +1 -1 -1 -1   -3.0      17     0.0
# 8 -1 +1 -1 +1 -1   -3.0      10     0.0
# 9 -1 +1 -1 -1 +1   -3.0       7     0.0
# ['SPIN', 10 rows, 121 samples, 5 variables]