Czym dokładnie jest „losowe próbkowanie obwodu”?

Wiele osób sugerowało stosowanie „losowego próbkowania obwodów” w celu wykazania supremacji kwantowej. Ale jaka jest dokładna definicja problemu „losowego próbkowania obwodu”? Widziałem takie stwierdzenia, jak: „zadaniem jest pobranie losowego (wydajnego) obwodu kwantowego określonej postaci i wygenerowanie próbek z jego rozkładu wyjściowego”. Ale nie jest dla mnie jasne, co dokładnie oznaczają pojęcia „losowy (wydajny) obwód kwantowy”. Czy wiemy też coś o klasycznej złożoności obliczeniowej tego problemu?

$n$$2^n$

Większość z tych stanów jest wysoce splątana i wymagałaby stworzenia bardzo skomplikowanych obwodów (przy założeniu standardowego zestawu bramek z pojedynczymi obrotami kubitów i dwóch lub trzech bramek oplatających kubit).

$|0\rangle$

$n$

$n$$n$

$n$$n$

Szczegóły, jak dokładnie przejść do tworzenia obwodu losowego i czego szukać w wynikach, aby ogłosić sukces, zależą od propozycji (takiej jak Google). Nie jest jeszcze jasne, ile kubitów jest potrzebnych, zanim obecne superkomputery nie będą w stanie odtworzyć wyniku.