[0001] Consider the set $D_n\subset \{(,)\}^{2n}$ of all Dyck words of strings of balanced brackets or balanced parentheses of length $2n$. For example, for $n=5$, we have $\sigma=()()()()()$ is balanced, while $\tau=(()))(()()$ is not.
[0002] Thought of as basis vectors in a Hilbert space on $2n$ qubits $\{|(\rangle,|)\rangle\}^{\otimes 2n}$, an interesting highly entangled state is the uniform superposition of all such Dyck words. Indeed, from Sergey Bravyi's lecture on stoquastic Hamiltonians at the Israeli Institute of Advanced Studies, I learned that Salberger and Korepin proved for a fixed $n$ all such Dyck words can be generated with only two moves, each acting on three (adjacent) symbols:
$$l:(()\leftrightarrow ()(,\\ r:\:)()\leftrightarrow ()).$$
[0003] With some similarity to a CSWAP involution, such moves are referred to in the literature as Fredkin moves, and the chain of qubits as Fredkin spin chains. Again fixing $n$ and starting from a string such as $\sigma$, a random walk on the unweighted graph formed by such moves will eventually reach all such Dyck words. Accordingly, Salberger and Korepin write a three-local stoquastic Hamiltonian out of projectors $|l\rangle\langle l|$ and $|r\rangle\langle r$|. The appropriately normalized state $|D_n\rangle$ over all Dyck words of a fixed length is the unique ground state of the stoquastic Hamiltonian.
[0004] It may be natural to ask:
How can we efficiently prepare such a properly normalized state corresponding to the uniform distribution over all Dyck words on $2n$ qubits?
[0005] Determining the balancedness of a string of parentheses is often introduced early in the study of algorithms. For example, opening and closing parentheses correspond to pushing and popping items onto a stack; the string is balanced only if the stack never experiences underflow.
[0006] Also, famously the number of strings of balanced parentheses of length $2n$ is given by the $n$th Catalan number, which is:
$$C_n=\frac{1}{n+1}{2n\choose n},$$
while the central binomial coefficient is given by $2n\choose n$. So one approach may be to (1) initially prepare the uniform superposition over all $2n\choose n$ strings with the same number $n$ of open parentheses as closed parentheses, (2) evaluate in superposition and into a flag register if the strings so constructed are balanced or not, for example using the above stack underflow algorithm, and (3) post-select on the flag register indicating that the strings are balanced, with success probability $\frac{1}{n+1}$. But is there another simpler approach?
