Breadth First Search to find connected primes
There are 3 major performance problems you currently have:


the primes is currently a list and every time you do something in primes - this is O(n) average-time complexity (where n is the length of primes) - define primes as a set instead 
the visited is a list, same O(n) lookups - define it as a set instead
the del q[0] is also a O(n) operation - removing an element from the beginning of a list requires rearranging all following elements - use a collections.deque in place of a list for O(1) deletes from both ends (.popleft() for the left-end deletion)


Revised version (works for me in an instant for all the test inputs):

import math
from collections import deque


class Node:
    __slots__ = ['value', 'parent']

    def __init__(self, value, parent):
        self.value = value
        self.parent = parent

    def get_adjacent(self, primes):
        for i in powers_of_two:
            if self.value + i &lt; upper_limit and self.parent != self.value + i and self.value + i in primes:
                yield Node(i + self.value, self)
            if self.value - i &gt;= 2 and self.parent != self.value - i and self.value - i in primes:
                yield Node(self.value - i, self)


def sieve(n):
    numbers = list(range(0, n))
    for prime in numbers:
        if prime &lt; 2:
            continue
        elif prime &gt; n ** 0.5:
            break

        for i in range(prime ** 2, n, prime):
            numbers[i] = 0

    return {x for x in numbers if x &gt; 1}


def bfs(f, to, primes):
    f = Node(f, None)

    q = deque([f])
    visited = set([f.value])
    while q:
        if q[0].value == to:
            return q[0]
        else:
            for x in q[0].get_adjacent(primes):
                # print(q[0].value, x.value)
                if x.value not in visited:
                    # print("added", x.value)
                    visited.add(x.value)
                    q.append(x)
        q.popleft()


if __name__ == '__main__':
    upper_limit, p, q = [int(x) for x in input().split(' ')]

    m = int(math.ceil(math.log2(upper_limit))) if math.log2(upper_limit) % 1 != 0 else int(math.log2(upper_limit))
    powers_of_two = [2 ** i for i in range(m)]

    primes = sieve(upper_limit)

    x = bfs(p, q, primes)

    counter = 0
    while x is not None:
        print(x.value)
        x = x.parent
        counter += 1

    print("--------------------")
    print(counter)


You can also see some other changes:


removed the while True loop (from what I understand you just need a single run) 
using if __name__ == '__main__':
avoiding using globals and passing the primes set to the bfs() and get_adjacent() as an argument
using __slots__ for the Node class
used list unpacking for reading the input numbers
used upper_limit, p and q variables to increase readability (p and q variable names are used in the problem description)