Suppose I have an algorithm that prepares a state of $N$ qubits ($N$ variable); I was recently told that the algorithm is called efficient if the depth of the circuit is independent of $N$. However, they said that there is variability in how "efficient" is defined.
What is the definition of an "efficient" algorithm? Or are there many ways to define it?
As pointed out by @Martin Vesely, complexity theorists generally use an "efficient algorithm" for any algorithm with polynomial runtime. But this is in no way a universal use. [see wiki]. However, the complexity theory definition is most suitable to the context (of the problem).
Circuit depth and computational time (of the algorithm) are directly related. A poly-depth circuit implies a polynomial runtime and vice versa.
Some quantum states require constant depth circuits (w.r.t number of qubits), like preparing a uniform superposition state. Some require polynomial/logarithmic depth. Some go beyond polynomials, too.
A more rigorous definition (of efficient algorithm) requires an explicit mention of:
We get the above details by inspecting the context of the discussion. Like in this problem, you are concerned about the quantum model. And time is the resource of concern (this is taken as default if nothing is mentioned explicitly).
In complexity theory, we study the number of "steps" that an algorithm takes to answer a question of the form "is $x$ in the language $L$?". Complexity is defined with relation to the size of the input $x$. An algorithm is typically said to be "efficient" if it terminates in a number of steps polynomial in the input length $|x|$.
In classical complexity theory, there are two model of computation: Turing machines and boolean circuits. In Turing machines, the "step" is the transition function and its complexity is how many times the machine, with its tape initialized on $x$, uses its transition function before halting in an accepting or rejecting state. In boolean circuits, the "steps" are the logical gates of the circuit (e.g. OR, AND, NOT gates). You could also care about circuit depth. Since boolean circuits take a fixed-size input, we consider families of circuits $\{C_1,C_2,\dots\}$ (one for each input size). Typically, we want a family of circuit to be uniform, i.e. there exists a poly-time Turing machine that on input $1^n$ outputs the description of $C_n$.
In quantum computing, we are typically interested in unitary transformations in the form of quantum circuits. The definition of complexity is now quite similar to that of classical circuits with a family of quantum circuits $U_1,U_2,\dots$. In the quantum setting you might also need a number (which also depends on $|x|$) of auxiliary registers initialized in state $|0\rangle$. To decide if $x\in L$, the circuit $U_{|x|}$ is applied on initial state $| x\rangle| 0^{s(|x|)}\rangle$ and the qubits are measured to get the answer.
Other metrics that people care about include space complexity, which would correspond to circuit width in the case of quantum computing. In the definition I've given, circuit width is $|x|+s(|x|)$, so efficiency would be defined $s(\cdot)$ being a polynomial.
Some quantum algorithms (most famously Shor's) alternate classical and quantum subroutines. These algorithms don't directly fit in the definition above, but it theory noting prevents one from doing the classical part in the quantum circuit with some overhead in the complexity.
Just addition on preparing quantum states. For a general state, circuit depth is exponential as you can see from construction in this paper: Transformation of quantum states using uniformly controlled rotations. So, if your algorithm requires input of a general state and the state is prepared as part of the algorithm (i.e. it is not provided by other algorithm or sensor etc.), then it is not efficient. Of course, there are some special states which can prepared efficiently, e.g. a uniform superposition (on each qubit, Hadamard gate is applied, which implies constant depth regardless of number of qubits), GHZ states (linear increase in depth with number of qubits), W-states (see here) or Gaussian states (see here and here).
Once we have quantum memory (qRAM), we should be able to prepare any state efficiently, however, qRAM is for now far from completion. See here for more information on how qRAM should work.