Indexing of a PostgreSQL bitstring (up to 20,000 bits each)
Famous problem in cheminformatics.  You will have a hard time coming up with an index that will beat a full-table scan for this purpose.  The most performant solutions keep the bitstrings outside of the database, where they don't have to deal with transactional overhead, and are optimized for efficient use of popcnt hardware support.

You can take some shortcuts, by for example keeping the bitstring data sorted by the number of on bits.  If the query says "find me things with each of these 45 different bits turned on" then you can quickly skip all the records with less than 45 bits turned on, as they can't possibly qualify.  The problem is that queries are usually sparser in bits than whole compounds are, so the number of records skipped by this manner is pretty small.  Another optimization is to use something like a genetic algorithm to select out certain bits as being more important than others (trained on the nature of the queries you run), and sorting on the population count of just those select bits rather than the entire bitstring.

Anyway, I don't think you will find what you want in an in-core PostgreSQL index, so be prepared to do some heavy hacking.  You might want to look to Indigo source code for some inspiration.  (Or maybe you can just use Indigo for your intended purpose directly)